mundial e per la matematica

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
timothy6
Messaggi: 18
Iscritto il: 12 set 2007, 21:03

mundial e per la matematica

Messaggio da timothy6 » 08 ott 2007, 22:34

I don'y know if it's translated correctly

Ci è $ n $ gente ed esiste $ 2^{n}-1 $ squadre di gioco del calcio. In ogni squadra di gioco del calcio dobbiamo scegliere il menager. MA: Se la squadra $ X $ è somma $ X = Y u Z $ allora che il menager X sono il menager almeno di uno del ritrovamento delle squadre Y, Z che cosa è il numero di selezioni possibili di menager.

Lo ho trovato sopra: http://www.mathhelpforum.com/math-help/ ... orics.html

Non so se lo ho tradotto correttamente

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 09 ott 2007, 14:32

Well, you don't mind, if I retranslate the problem for you, I guess.



Ci sono $ n $ persone e $ 2^n - 1 $ squadre. (*)

In ogni squadra dobbiamo scegliere un manager in modo tale che se la squadra $ X $ e' unione di due squadre $ Y $ e $ Z $, allora il manager di $ X $ e' manager di almeno una tra $ Y $ e $ Z $.

Trovare il numero di scelte possibili dei manager.

(*) [suppongo, distinte, non vuote e composte da persone prese tra le $ n $ date. NdT]

The problem is very nice, indeed. Thanks for posting it. M.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Avatar utente
3C273
Messaggi: 113
Iscritto il: 10 mag 2007, 17:38

Messaggio da 3C273 » 10 ott 2007, 11:25

Ci ho pensato piuttosto di fretta, e potrei dire una scemata assurda... comunque mi viene $ n! $. Se ha senso cerco di metter giù il ragionamento che per ora svolazza allegramente di qua e di là nella mia testa...

I haven't thought so much about this problem, and it's possible that my answer is completely wrong... anyway I obtained $ n! $. If it is correct, I'll try to write down the explanation... :roll:
(D'accordo...) Ambasciat[b]rice[/b]: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 10 ott 2007, 13:11

Well, 3C, it is not much a foolproof confirmation, but I get the same result too. Ok, go on and post the solution, then.

@Timothy: whereas this Forum is mainly in Italian and it is specifically dedicated to Italian Maths competitions (and related world spinning around them), users from abroad and non-Italian speakers are of course very well welcome.

Anyone interested in Maths and Maths Olympiad knows (or, at least, should know) at least some bits of English, so it is fine to use English here in the Forum [well, if we do not overuse it, anyway].

You are not granted to receive an answer in the same language, but if you are more confortable with English, then fine. On the other hand, I guess that you know a little of Italian too, otherwise you would not be here anyway...
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

timothy6
Messaggi: 18
Iscritto il: 12 set 2007, 21:03

Messaggio da timothy6 » 10 ott 2007, 14:17

So any ideas so far? I know a bit itallian but i prefer english. I havent't noticed too many people speaking english on OliForum

Avatar utente
3C273
Messaggi: 113
Iscritto il: 10 mag 2007, 17:38

Messaggio da 3C273 » 10 ott 2007, 15:35

Let's start "upside-down"...
Let $ a $ be the manager of the team N which contains all the people. Let A be the team which contains only $ a $. It is easy to show that $ \forall $ team X, $ a\in X\Rightarrow a $ is the manager of X, because $ X=A\cup (X\backslash A) $. The manager $ a $ can be chosen among n people. Now let's split the teams in 2 groups, the teams which contain $ a $ and the teams which don't contain $ a $. We already know that $ a $ is the manager of all the teams which contain $ a $. For the others, let $ a' $ be the manager of the team N' which contains all the people but $ a $. Again, $ a' $ can be chosen among (n-1) people, and again the manager of all the teams which contain $ a' $ (and not $ a $) is fixed. Iterating, the managers can be chosen in n! ways.

Mmm... have I messed up too much?
(D'accordo...) Ambasciat[b]rice[/b]: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 10 ott 2007, 16:54

Hmm... well, just a little bit. The main ideas are there. I think you should prove that your construction does fulfill the hypothesis. It is quite trivial, but does not follow automatically from your proof.

I would have written down the thing like this: the key lemma is:

If $ a $ is the manager of $ A $, then for each $ B $, subset of $ A $ containing $ a $, $ a $ is the manager of $ B $ too.

Proof in 3C's post.

With the lemma, basically, you can show that the only way of assigning managers is:

- decide a complete ordering of the people
- appoint the person $ a $ as manager of team $ A $ iff $ a = \max A $ (max taken wrt the ordering).

Knowing this, it is quite obvious why the hypothesis will hold for any choice of $ Y $ and $ Z $. So, for each ordering, you can assign managers.

Conversely, given an assignement of managers, then it is easy to construct an ordering as suggested by 3C (the highest ranking person would be the manager of all the people, the second highest would be the manager of all the people but the highest, and so on...). One should prove this is indeed an ordering, but this is really straightforward.

Thus, possible orderings are in bijection with manager assignements, and we are done. []
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

berdah
Messaggi: 3
Iscritto il: 17 ott 2007, 18:18

Messaggio da berdah » 21 ott 2007, 12:02

I think n! is bad answer.
if n=3, we have 24 posibilities.

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 22 ott 2007, 11:34

Could you please show us a proof? Or at least point out where our solution is flawed? Thanks.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

berdah
Messaggi: 3
Iscritto il: 17 ott 2007, 18:18

Messaggio da berdah » 24 ott 2007, 19:09

we have $ 2^n-1 $ teams.
so in each we must choose a manager.
for n=3, we have 7 teams: 1,2,3,12,13,23,123
fisrst posibility: 1,2,3,12,13,23,123
second posibility: 1,2,3,12,13,23,123
third posibility: 1,2,3,12,13,23,123
go on, we have 24 posibilities

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 25 ott 2007, 16:02

berdah ha scritto:for n=3, we have 7 teams: 1,2,3,12,13,23,123
[...]
second posibility: 1,2,3,12,13,23,123
[...]we have 24 posibilities
We do not. Be careful: second possibility above does not verify the hypothesis. Take $ A = \{ 1, 2 \} $ and $ B = \{3\} $.

Then the manager of $ A \cup B $ is $ 2 $, that is neither $ A $'s manager ($ 1 $), nor $ B $'s ($ 3 $).
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

berdah
Messaggi: 3
Iscritto il: 17 ott 2007, 18:18

Messaggio da berdah » 27 ott 2007, 16:10

Marco ha scritto:
berdah ha scritto:for n=3, we have 7 teams: 1,2,3,12,13,23,123
[...]
second posibility: 1,2,3,12,13,23,123
[...]we have 24 posibilities
We do not. Be careful: second possibility above does not verify the hypothesis. Take $ A = \{ 1, 2 \} $ and $ B = \{3\} $.

Then the manager of $ A \cup B $ is $ 2 $, that is neither $ A $'s manager ($ 1 $), nor $ B $'s ($ 3 $).
I dont think so. idont understand good English.
I think that hypothese say that for some A and B, not for every.
Taking $ A = \{ 1, 2 \} $ and $ B = \{3\} $ we can find for example A=2 and b=13

Avatar utente
Marco
Site Admin
Messaggi: 1331
Iscritto il: 01 gen 1970, 01:00
Località: IMO '93

Messaggio da Marco » 30 ott 2007, 12:43

Well, the original source states (verbatim):
If team $ X $ is sum $ X = Y \cup Z $ then the menager $ X $ is the menager of at least one of teams $ Y,Z $
Find the number of possible selections of menager.
Indeed, from this wording, we cannot be sure whether this means for every possible choice of $ X, Y, Z $ such that blah, blah, blah..., or there exists a possible choice so and so...

Nevertheless, if we admitted the latter interpretation, then the hypothesis would be completely trivial and pointless: just take $ X $ the team with all the involved people, $ Y $ as the set with only $ X $'s manager, and $ Z $ all the others [or, even more trivially, $ X = Y = Z $].

This is why I guess that the original statement meant

whenever $ X,Y,Z $ are s.t. $ X = Y \cup Z $, then $ X $'s manager must be the manager of at least one of $ Y $ and $ Z $ as well.
[i:2epswnx1]già ambasciatore ufficiale di RM in Londra[/i:2epswnx1]
- - - - -
"Well, master, we're in a fix and no mistake."

Rispondi