Maths Olympiad Prep

Library / /42 of 44

Combinatorics Difficulty 7.0 National Olympiad Prove it Slovenia

Eight boxes numbered 11 to 88 are lined up next to an empty bag. Each box contains one token. Miha has a lot of extra tokens and he plays a game where the following two actions are allowed:
* removing 11 token from box ii (i<8i < 8) and adding 22 tokens into box (i+1)(i + 1),
* removing 11 token from box ii (i<8i < 8) and moving 11 token from box (i+1)(i + 1) into the bag.

The game ends when there are no possible moves left. At least how many tokens are in the bag at the end?

Solution

Let AiA_i and BiB_i denote the first and second move taken on the boxes marked ii and i+1i+1. Let i6i \le 6. If Miha chooses to play BiB_i, then the number of tokens in the boxes marked ii and i+1i+1 is reduced by 11, the number of tokens in the box i+2i+2 remains the same, and the number of tokens in the bag increases by 11. If Miha chooses to play the sequence of moves AiA_i, Ai+1A_{i+1}, Bi+1B_{i+1}, then the number of tokens in the box ii decreases by 11, the number of tokens in the box i+1i+1 remains the same, and the number of tokens in the box i+2i+2 and in the bag is increased by 11. The end result is better in the second case since the only difference is that two boxes contain an extra token each. We conclude that the moves BiB_i for i6i \le 6 are not profitable.

As for other moves, only B7B_7 increases the number of tokens in the bag, so Miha should make that move as many times as possible. Without loss of generality we may assume that this move is only taken at the very end. Before that, Miha uses AiA_i, i6i \le 6, to move the tokens into the seventh box which then contains 1+2+22++26=271=1271 + 2 + 2^2 + \dots + 2^6 = 2^7 - 1 = 127 tokens, while the final box contains 11 token.

Let xx denote the number of tokens in the seventh box at a certain point in time, and let yy be the number of tokens in the last box at the same time. In order for Miha to make as many moves B7B_7 as possible, min{x,y}\min\{x, y\} has to be as large as possible. Since A7A_7 decreases the number of tokens in the seventh box by 11 and increases the number of tokens in the last box by 22, this minimum will be the greatest when we have xyx \le y for the first time, so when y=xy = x.

After kk moves A7A_7 we have x=127kx = 127 - k and y=1+2ky = 1 + 2k. Thus, we are looking for the smallest kk such that 127k1+2k127 - k \le 1 + 2k, or k12713=42k \ge \frac{127-1}{3} = 42. The smallest such kk is k=42k = 42.

After 4242 moves of type A7A_7 Miha can use the B7B_7 moves to move 12742=85127 - 42 = 85 tokens into the bag, and this is the greatest possible number of tokens that he can have in the bag at the end.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.