A dragon gave a captured knight $100$ coins. Half of them are magical, but only dragon knows which are. Each day, the knight should divide the coins into two piles (not necessarily equal in size). The day when either magic coins or usual coins are spread equally between the piles, the dragon set the knight free. Can the knight guarantee himself a freedom in at most (a) $50$ days? (b) $25$ days?
Problem
Source:
Tags: combinatorics, game, game strategy
05.05.2020 07:43
solution?
11.06.2022 03:06
Solved with JustinLee2017 The knight can guarantee himself a freedom in at most $\boxed{25}$ days. Construction: Start by having the knight split the coins into a pile of 75 and a pile of 25. Each day, the knight takes one coin from the larger pile and puts it in the smaller pile. Proof of construction: Suppose there are $x$ magical coins in the 75 pile on the first day. Thus, there are $75-x$ normal coins in the 75 pile, $50-x$ magical coins in the 25 pile, and $x-25$ normal coins in the 25 pile. Note that $75-x \leq 50$ and so $x \geq 25$. The knight takes at least $$\text{min}\left(\frac{|(x)-(50-x)|}{2}, \frac{|(75-x)-(x-25)|}{2}\right)$$days to finish, and thus takes at most $$\left(\frac{|(x)-(50-x)|}{2} - 1\right) + \left(\frac{(75-x)-(x-25)|}{2} - 1\right) +1$$days to finish. Since $x \geq 25$, we have that $x \leq 50-x$ and $x-25 \leq 75-x$, and we can rewrite this as $$\left(\frac{50-2x}{2}-1\right) + \left(\frac{100-2x}{2}-1\right) + 1 = 74-2x \leq 24$$ Therefore, using this method, the knight can guarantee his freedom in $25$ days.