Maths Olympiad Prep

Library / /457 of 520

Combinatorics Difficulty 7.5 National olympiad, round 2 Find the answer

Initially, one cow is located on every negative integer on the number line. Each day, Farmer John chooses an integer kk where the interval [k,k+5000][k, k+5000] has cows. First, he moves each cow in [k,k+5000][k, k+5000] to another integer in the interval, so that no two cows move to the same integer. Then, he chooses a cow in the interval and removes it.

Can Farmer John get a cow on 100,000,000100,000,000 after some time?

Solution

1. Assigning Weights to Cows:
Each cow at position n n is assigned a weight hn h^n , where h=1.000000159=1+159109 h = 1.000000159 = 1 + \frac{159}{10^9} . When a cow moves from position m m to n n , its weight changes from hm h^m to hn h^n .

2. Weight Change Analysis:
We need to show that moving the cows strictly decreases their total weight. Consider an interval [0,5000][0, 5000] without loss of generality. Suppose there are 2501 cows initially at positions 0,1,,2500 0, 1, \ldots, 2500 . After moving, they occupy positions 2501,2502,,5000 2501, 2502, \ldots, 5000 .

3. Initial and Final Weights:
- Initial weight: i=02500hi=h25011h1\sum_{i=0}^{2500} h^i = \frac{h^{2501} - 1}{h - 1}
- Final weight: i=25015000hi=h50011h1h25011h1\sum_{i=2501}^{5000} h^i = \frac{h^{5001} - 1}{h - 1} - \frac{h^{2501} - 1}{h - 1}

4. Weight Decrease Condition:
If the initial weight is greater than the final weight, we must have:
h50012h2501+1<0 h^{5001} - 2h^{2501} + 1 < 0

5. **Approximating h5001 h^{5001} :**
Using the binomial expansion:
h5001=(1+159109)50011+5001159109+(50012)(159109)2+(50013)(159109)3+ h^{5001} = \left(1 + \frac{159}{10^9}\right)^{5001} \approx 1 + 5001 \cdot \frac{159}{10^9} + \binom{5001}{2} \left(\frac{159}{10^9}\right)^2 + \binom{5001}{3} \left(\frac{159}{10^9}\right)^3 + \cdots
We can show that higher-order terms are negligible.

6. Simplifying the Expansion:
- First term: 1 1
- Second term: 5001159109=0.000795159 5001 \cdot \frac{159}{10^9} = 0.000795159
- Third term: (50012)(159109)2=5001250015921018=0.0000003160757025 \binom{5001}{2} \left(\frac{159}{10^9}\right)^2 = \frac{5001 \cdot 2500 \cdot 159^2}{10^{18}} = 0.0000003160757025
- Fourth term: (50013)(159109)30.0000000001024 \binom{5001}{3} \left(\frac{159}{10^9}\right)^3 \approx 0.0000000001024
- Fifth term and beyond are even smaller.

Summing these, we get:
h5001<1.0007954754281025 h^{5001} < 1.0007954754281025

7. **Approximating h2501 h^{2501} :**
Similarly,
h2501=(1+159109)25011+2501159109+(25012)(159109)2+ h^{2501} = \left(1 + \frac{159}{10^9}\right)^{2501} \approx 1 + 2501 \cdot \frac{159}{10^9} + \binom{2501}{2} \left(\frac{159}{10^9}\right)^2 + \cdots
- Second term: 2501159109=0.000397659 2501 \cdot \frac{159}{10^9} = 0.000397659
- Third term: (25012)(159109)2=0.00000007903472625 \binom{2501}{2} \left(\frac{159}{10^9}\right)^2 = 0.00000007903472625

Summing these, we get:
h2501>1.00039773803472625 h^{2501} > 1.00039773803472625

8. Combining Inequalities:
h5001<1.0007954754281025 h^{5001} < 1.0007954754281025
2h2501<2.0007954760694525 -2h^{2501} < -2.0007954760694525
Adding these:
h50012h2501+1<1.00000000064135<1 h^{5001} - 2h^{2501} + 1 < -1.00000000064135 < -1
Thus, h50012h2501+1<0 h^{5001} - 2h^{2501} + 1 < 0 .

9. Total Initial Weight:
The total initial weight of the cows is:
i=11hi=1h1=1091596289309 \sum_{i=1}^{\infty} \frac{1}{h^i} = \frac{1}{h-1} = \frac{10^9}{159} \approx 6289309

10. Weight of a Cow at 100,000,000:
Using Bernoulli's inequality and approximations:
h100,000,000>4.7910>4.7934.797>109.912000>6289309 h^{100,000,000} > 4.79^{10} > 4.79^3 \cdot 4.79^7 > 109.9 \cdot 12000 > 6289309
Thus, h100,000,000>109159 h^{100,000,000} > \frac{10^9}{159} .

Since the weight of a cow at 100,000,000 exceeds the total initial weight, it is impossible for Farmer John to get a cow to position 100,000,000.

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