Maths Olympiad Prep

Library / /58 of 97

Combinatorics Difficulty 8.1 Shortlist Find the answer

Let kk be a positive real. AA and BB play the following game: at the start, there are 8080 zeroes arrange around a circle. Each turn, AA increases some of these 8080 numbers, such that the total sum added is 11. Next, BB selects ten consecutive numbers with the largest sum, and reduces them all to 00. AA then wins the game if he/she can ensure that at least one of the number is k\geq k at some finite point of time.

Determine all kk such that AA can always win the game.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

Let k k be a positive real number. A A and B B play the following game: at the start, there are 80 zeroes arranged around a circle. Each turn, A A increases some of these 80 numbers such that the total sum added is 1. Next, B B selects ten consecutive numbers with the largest sum and reduces them all to 0. A A wins the game if he/she can ensure that at least one of the numbers is k\geq k at some finite point in time.

To determine all k k such that A A can always win the game, we analyze the strategy and the bounds involved.

First, we reduce the problem from F(80,10) F(80, 10) to F(8,1) F(8, 1) . This reduction is valid because B B can only select 10 consecutive buckets, and we can group these buckets into 8 larger buckets, each containing 10 of the original buckets. Thus, the problem simplifies to a scenario where B B can only empty one of these larger buckets at a time.

We now play the game on F(8,1) F(8, 1) . For B B , the optimal strategy is to empty the largest bucket all the time. Let the buckets be labeled 1 1 to 8 8 with amounts of water a1,a2,,a8 a_1, a_2, \ldots, a_8 , arranged in decreasing order so that a1a2a8 a_1 \geq a_2 \geq \ldots \geq a_8 .

The key lemma is that after A A makes a move, the sum of the largest k k buckets is less than k(1+i=k71i) k \cdot \left(1 + \sum_{i=k}^{7} \frac{1}{i} \right) . We prove this by downward induction.

For k=8 k = 8 :
i=18ai1+i=28ai1+78i=18ai, \sum_{i=1}^{8} a_i \leq 1 + \sum_{i=2}^{8} a'_i \leq 1 + \frac{7}{8} \sum_{i=1}^{8} a'_i,
where ai a'_i is the amount of water in the buckets in the previous round. Since initially i=18ai=1 \sum_{i=1}^{8} a_i = 1 , it follows that i=18ai<8 \sum_{i=1}^{8} a_i < 8 .

Assuming the statement is true for k=m k = m , for k=m1 k = m-1 :
i=1m1ai1+i=2mai1+m1mi=1mai<1+(m1)(1+i=m71i). \sum_{i=1}^{m-1} a_i \leq 1 + \sum_{i=2}^{m} a'_i \leq 1 + \frac{m-1}{m} \sum_{i=1}^{m} a'_i < 1 + (m-1) \left(1 + \sum_{i=m}^{7} \frac{1}{i} \right).
Thus, the statement holds for k=m1 k = m-1 as well.

By induction, the statement is true for k=1 k = 1 as well, hence the largest bucket is less than 1+1+12++17 1 + 1 + \frac{1}{2} + \ldots + \frac{1}{7} .

To show that this is the best attainable bound, A A 's strategy is to ensure that a1=a2==a8 a_1 = a_2 = \ldots = a_8 in each round. The amount of water in each bucket follows the sequence:
18,18(1+78),18(1+78+(78)2), \frac{1}{8}, \quad \frac{1}{8} \left(1 + \frac{7}{8} \right), \quad \frac{1}{8} \left(1 + \frac{7}{8} + \left(\frac{7}{8} \right)^2 \right), \ldots
The limit of this sequence is 1. When the buckets are sufficiently close to 1, A A will add 17\frac{1}{7} to the 7 largest buckets, 16\frac{1}{6} to the 6 largest buckets, and so on, finally adding 1 to the largest bucket left. The total amount of water in that bucket can be arbitrarily close to k=1+1+12++17 k = 1 + 1 + \frac{1}{2} + \ldots + \frac{1}{7} .

Therefore, A A can always win the game if k1+1+12++17 k \leq 1 + 1 + \frac{1}{2} + \ldots + \frac{1}{7} .

The answer is: 1+1+12++17\boxed{1 + 1 + \frac{1}{2} + \ldots + \frac{1}{7}}.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.