Maths Olympiad Prep

Track / Stage 7 / 219 of 300 #1619 of 1964

Problem 1619

National olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.4 Find the answer

Positive numbers are written in the squares of a 10 × 10 table. Frogs sit in five squares and cover the numbers in these squares. Kostya found the sum of all visible numbers and got 10. Then each frog jumped to an adjacent square and Kostya’s sum changed to 10210^2. Then the frogs jumped again, and the sum changed to 10310^3 and so on: every new sum was 10 times greater than the previous one. What maximum sum can Kostya obtain?

A number or a short expression. Spacing, $ signs and \frac vs / are all fine.

Official solution

1. Initial Setup and Problem Understanding:
- We have a 10 × 10 table with positive numbers.
- Frogs sit on five squares, covering the numbers in these squares.
- Kostya calculates the sum of all visible numbers and gets 10.
- Each frog jumps to an adjacent square, and the sum changes to 10210^2.
- This pattern continues, with each new sum being 10 times greater than the previous one.

2. Formulating the Problem:
- Let S0 S_0 be the initial sum of visible numbers, which is 10.
- After the first jump, the sum becomes S1=102=100 S_1 = 10^2 = 100 .
- After the second jump, the sum becomes S2=103=1000 S_2 = 10^3 = 1000 .
- This pattern continues up to S6=106 S_6 = 10^6 .

3. Analyzing the Sum Changes:
- The increase from S0 S_0 to S1 S_1 is 10010=90 100 - 10 = 90 .
- Since 5 squares are revealed and 5 are covered, the net change in the sum is due to the difference in the values of these squares.
- Let a1,a2,a3,a4,a5 a_1, a_2, a_3, a_4, a_5 be the values of the squares initially covered by the frogs.
- Let b1,b2,b3,b4,b5 b_1, b_2, b_3, b_4, b_5 be the values of the new squares covered by the frogs after the first jump.
- The change in sum can be expressed as:
S1S0=(b1+b2+b3+b4+b5)(a1+a2+a3+a4+a5) S_1 - S_0 = (b_1 + b_2 + b_3 + b_4 + b_5) - (a_1 + a_2 + a_3 + a_4 + a_5)
Given S1=100 S_1 = 100 and S0=10 S_0 = 10 , we have:
10010=(b1+b2+b3+b4+b5)(a1+a2+a3+a4+a5)=90 100 - 10 = (b_1 + b_2 + b_3 + b_4 + b_5) - (a_1 + a_2 + a_3 + a_4 + a_5) = 90

4. Bounding the Values:
- Since the sum increases by a factor of 10 each time, the values of the revealed squares must be significantly larger than the values of the covered squares.
- For the increase from 10k 10^k to 10k+1 10^{k+1} , the increase is 10k+110k=9×10k 10^{k+1} - 10^k = 9 \times 10^k .
- At least one of the revealed squares must have a value greater than 9×10k5=1.8×10k \frac{9 \times 10^k}{5} = 1.8 \times 10^k .

5. Proving the Maximum Sum:
- For the sum to reach 107 10^7 , the increase from 106 10^6 to 107 10^7 would be 9×106 9 \times 10^6 .
- This would require at least one square to have a value greater than 1.8×106 1.8 \times 10^6 .
- However, since there are only 5 frogs and each jump reveals 5 new squares, the values of these squares must be unique and within specific ranges.
- The ranges for the values of the revealed squares are:
(1.5×102,10×102),(1.5×103,10×103),,(1.5×106,10×106) (1.5 \times 10^2, 10 \times 10^2), (1.5 \times 10^3, 10 \times 10^3), \ldots, (1.5 \times 10^6, 10 \times 10^6)
- These ranges are non-intersecting, meaning each value must be unique.
- Since there are only 5 frogs, at least one square must be visible at all times, which is impossible given the constraints.

6. Conclusion:
- Therefore, Kostya cannot achieve a sum of 107 10^7 .
- The maximum sum Kostya can obtain is 106 10^6 .

The final answer is 106 \boxed{10^6}

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.