mundial e per la matematica

[timothy6]

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

[Marco]

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.

[3C273]

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...

[Marco]

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...

[timothy6]

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

[3C273]

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?

[Marco]

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. []

[berdah]

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

[Marco]

Could you please show us a proof? Or at least point out where our solution is flawed? Thanks.

[berdah]

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

[Marco]

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 $).

[berdah]

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

[Marco]

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.