Football and Combi

For discussing Olympiad Level Combinatorics problems
User avatar
Abdullah Al Tanzim
Posts: 20
Joined: Tue Apr 11, 2017 12:03 am
Location: Dhaka, Bangladesh.

Football and Combi

Unread post by Abdullah Al Tanzim » Thu Apr 12, 2018 2:32 pm

$23$ people, each with integral weight,decide to play football, separating into two teams of $11$ people and a referee.To keep things fair, the teams chosen must have the equal total weight.It turns out that no matter who is chosen to be the referee, this can always be done.Prove that the $23$ people must all have the same weight.
Everybody is a genius.... But if you judge a fish by its ability to climb a tree, it will spend its whole life believing that it is stupid - Albert Einstein

User avatar
samiul_samin
Posts: 1004
Joined: Sat Dec 09, 2017 1:32 pm

Re: Football and Combi

Unread post by samiul_samin » Fri Apr 13, 2018 9:54 pm

It is not possible if any of the referees is not same weighted.So,every referee has the same weight. There are 23 possible referees.So,it is proved that everyone has the same weight.(Short answer).

User avatar
Abdullah Al Tanzim
Posts: 20
Joined: Tue Apr 11, 2017 12:03 am
Location: Dhaka, Bangladesh.

Re: Football and Combi

Unread post by Abdullah Al Tanzim » Sat Apr 14, 2018 12:43 pm

samiul_samin wrote:
Fri Apr 13, 2018 9:54 pm
It is not possible if any of the referees is not same weighted.
why?
Everybody is a genius.... But if you judge a fish by its ability to climb a tree, it will spend its whole life believing that it is stupid - Albert Einstein

Golam Musabbir Joy
Posts: 11
Joined: Tue Jun 16, 2015 5:11 am
Location: Barisal, Bangladesh

Re: Football and Combi

Unread post by Golam Musabbir Joy » Sat May 19, 2018 8:33 pm

Let the weights of the peoples are $a_1,a_2, \dots a_{23} $ and $\sum a_i = S$. It is clear that $S - a_i$ is always even. So that $S $ and all $a_i $ nust have the same parity. It is also clear that if $a_i $ is a solution then $a_i + 1$ is also a solution. Let $b_1, b_2, \dots , b_{23} $ be one of the example where $S $ is least and all the $b_i $ is not equal.
If all the $b_i $ is even, then choose another sequence $c_i = \frac {b_i}{2}$ and if all the $b_i $ is odd , then choose another sequence $c_i = \frac {b_i - 1}{2} $ for $1 \leq i \leq $ which is also a solution and $S $ become lessen this time. So all the $b_i $ must be $0$ which implies all the $a_i $ is equal.

Post Reply