Initially, Aslı distributes $1000$ balls to $30$ boxes as she wishes. After that, Aslı and Zehra make alternated moves which consists of taking a ball in any wanted box starting with Aslı. One who takes the last ball from any box takes that box to herself. What is the maximum number of boxes can Aslı guarantee to take herself regardless of Zehra's moves?
Problem
Source: Turkey JBMO TST 2023 Day 1 P4
Tags: combinatorics
30.04.2023 19:58
Answer is 15 i will add solution later
30.09.2023 17:10
We will say a box is "good" if it contains an odd number of balls. Let $a_n$ be the number of good boxes after $2n$ moves and let $b_n$ be the number of moves where Aslı took a ball from a good box in her first $n$ moves. Assume that Zehra always takes balls from good boxes. (obviously she can do that) In that case, we have $a_n=a_{n-1}-2$, if Aslı takes a ball from a good box on her $n$th move, $a_n=a_{n-1}$, if Aslı doesn't take a ball from a good box on her $n$th move. Therefore, it is easy to see that $a_n=a_0-2b_n$ $(1)$ Let the answer to the original question be $N$. Notice that if Aslı wants to take a box to herself, she will have to take a ball from a good box, since $1$ is an odd number. Hence, $b_{500}\geq N$ If we plug in $n=500$ in $(1)$, we get $0=a_{500}=a_0-2b_{500}\leq a_0-2N$ By definition, $a_0\leq 30$. Therefore, $0 \leq 30-2N \implies \boxed{N\leq 15}$ If Aslı distributes the balls such that 29 boxes have 1 ball and 1 box has 971 balls, she can easily take 15 boxes. $N=15$ QED.
01.03.2024 23:52
Aslı'nın herhangi bir top diziliminde çift sayıda çift toplu kutu ve tek toplu kutu olacağı barizdir. Bu durumda tek toplu kutuya tek toplu kutu ve çift toplu kutuya çift toplu kutu eşleştirmesi yapılabilir.Zehra aşağıdaki algoritma ile Aslı'nın mümkün olduğunca az kutu almasını sağlayabilir: .Aslı çift toplu kutuya hamle yaparsa Zehra aynı kutuya hamle yapar. .Aslı tek toplu kutuya hamle yaparsa Zehra o tek toplu kutuyla eşleştirilmiş başka bir tek toplu kutuya hamle yapar. Bu algoritma sonunda Zehra 15 kutu garantilemiş olur.O yüzden Aslı en fazla 15 kutu garantiler. Aslı ilk 29 kutuya 1 top,son kutuya 971 top koyarsa Zehra'dan önce 15 kutu alabilir.