Outcome related combinatorics problem

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Outcome related combinatorics problem

G H J

Reveal topic tags

pigeonhole principle

L

G H BBookmark kLocked kLocked NReply

Source: All Russian 2025 10.7

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

209 posts

egxa

#1 h Apr 18, 2025, 5:12 PM

Y by

A competition consists of $25$ sports, each awarding one gold medal to a winner. $25$ athletes participate, each in all $25$ sports. There are also $25$ experts, each of whom must predict the number of gold medals each athlete will win. In each prediction, the medal counts must be non-negative integers summing to $25$ . An expert is called competent if they correctly guess the number of gold medals for at least one athlete. What is the maximum number $k$ such that the experts can make their predictions so that at least $k$ of them are guaranteed to be competent regardless of the outcome?

This post has been edited 1 time. Last edited by egxa, Apr 18, 2025, 5:21 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

8 posts

#2 h Apr 29, 2025, 10:46 AM

Y by

We claim that the maximum $k$ is equal to $24$ .
We correspond each athlete to a number from $1$ to $25$ .
Define Podium as the $n$ -tuple $(a_{1},a_{2},...,a_{25})$ where $a_{i}$ is the amount of medals won by athlete $i$ .
First notice that none of the experts can predict the $n$ -tuple $(1,1,...,1)$ because then if the podium is equal to $(25,0,0,...,0)$ then the most possible amount of judges predicting correctly is equal to $24$ . From the previous statement it follows that one of the judges predicts a $n$ -tuple which has a $0$ . So we proceed with the following algorithm. Pick one of the prediction $n$ -tuples and convert it with the following algorithm to a new $n$ -tuple: turn anything that isn't equal to $0$ to $0$ and then spread the 25 medals among the zero's.
Now if the podium $n$ -tuple is the same as this $n$ -tuple then at least one of the experts isn't competent and so maximum $k$ is equal to $24$ .
Now we will prove that no matter what the podium looks like we can achieve $k=24$ .
So we propose the following predictions: $(24,1,0,0,...,0),(24,0,1,0,0,...,0),(24,0,0,1,0,0,...0),...,(24,0,0,...,1),(1,1,...,1,1,1)$ .
Define the count of zeros of the podium as $C$ .
Now 3 cases might happen:
$C>2$ : then it's easy to notice that every expert except the last one is competent.
$C=2$ : an expert isn't competent if and only if both zeros are in the same place as the $1$ and $24$ . notice that no $2$ of the predictions have these 2 numbers in the same spot so worst case possible $24$ of the experts are competent.
$C=1$ : notice that the podium $n$ -tuple must have $23$ , $1$ 's and a single $2$ and a single $0$ . an expert isn't competent if and only if one of the following 2 cases occur:
First case: the $1$ in the prediction is in the same place as the $0$ of the podium.
Second case: the $24$ in the prediction is in the same place as the $0$ of the podium and the $1$ in the prediction is in the same place as the $2$ of the podium.
notice that the position of the $1$ differs among the predictions so for a fixed podium only one expert can be not competent because of the first case. The same applies for the second case as well. Since the union of the positions of $1$ and $24$ differs among the predictions there can't be 2 experts that are incompetent because of the second case. Also both cases can't make experts incompetent simultaneously since in case of both cases happening the $1$ and $24$ must basically switch places but in each of the first $24$ predictions $24$ is not in the first spot and all of the $1$ 's are in the first spot. So only one of these $24$ experts can be incompetent and the last expert is competent so at least $24$ of the experts are competent. $\blacksquare$

This post has been edited 5 times. Last edited by iliya8788, Apr 29, 2025, 12:11 PM

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a