On a stormy night ten guests came to dinner party and left their shoes outside the room in order to keep the carpet clean. After the dinner there was a blackout, and the gusts leaving one by one, put on at random, any pair of shoes big enough for their feet. (Each pair of shoes stays together). Any guest who could not find a pair big enough spent the night there. What is the largest number of guests who might have had to spend the night there?
Problem
Source:
Tags: maximum, algebra, combinatorics
04.10.2019 13:28
Bump.......
04.10.2019 13:36
Is 5 the answer?
04.10.2019 13:45
Here is what I think.. Let the people be as $ P_1, P_2 .. P_10$ and their shoes be as $ S_1, S_2,... S_10$ Now person $P_i$ can were shoes $S_j$ where $j\geq i$ Now if $P_1$ went and picked up $S10$ $P_2$ went and picked up $S9$ $.......$ $P_5$ went and picked up $S6$ Now for $P_6$ he cannot wear shoe $S_5$ or less, so $\framebox5$ people are left out. $ \square$ Upvote if you liked it.
04.10.2019 18:29
I agree with above. It is impossible to have more than 5 pairs, as that would assure that one of the people who stay would still have their exact pair in the house.
04.10.2019 18:30
16.10.2024 22:38
Is it only me or do you not need to formalise the bound? Here is my solution: Answer: The answer is $\boxed{5}$. Construction: If the shoe $S_i$ belonged to person $P_i$ with $i<j \implies size(S_i) \le size(S_j)$, the person $P(i)$ can take shoe $S(11-i)$, which is the construction for $5$. Note here $i \ge 6$ does not work. Bound: Let \( n \geq 6 \) represent the number of people, where the person with the smallest shoe size is \( 11 - n \) and the largest shoe size available is \( n \) in the worst case scenario. We need to show that for \( n \geq 6 \), the assumption \( 11 - n > n \) leads to a contradiction. Assume for contradiction that the smallest shoe size is larger than the largest shoe size: \[ 11 - n > n \] However, we are given that \( n \geq 6 \), which contradicts this result. Thus, the assumption that \( 11 - n > n \) must be false, and we conclude the proof.