Maths Olympiad Prep

Library / /131 of 520

Combinatorics Difficulty 6.5 National olympiad Find the answer

There are 365 cards with 365 different numbers. Each step, we can choose 3 cards ai,aj,aka_{i},a_{j},a_{k} and we know the order of them (examble: ai<aj<aka_{i}<a_{j}<a_{k}). With 2000 steps, can we order 365 cards from smallest to biggest??

Solution

To determine if we can order 365 cards from smallest to largest in 2000 steps, we need to analyze the given sum and the function f(x)=log3x f(x) = \lceil \log_3 x \rceil .

1. **Understanding the function f(x)=log3x f(x) = \lceil \log_3 x \rceil **:
- For x=3 x = 3 , log33=1 \log_3 3 = 1 , so f(3)=1 f(3) = 1 .
- For 4x9 4 \leq x \leq 9 , 1<log3x2 1 < \log_3 x \leq 2 , so f(x)=2 f(x) = 2 .
- For 10x27 10 \leq x \leq 27 , 2<log3x3 2 < \log_3 x \leq 3 , so f(x)=3 f(x) = 3 .
- For 28x81 28 \leq x \leq 81 , 3<log3x4 3 < \log_3 x \leq 4 , so f(x)=4 f(x) = 4 .
- For 82x243 82 \leq x \leq 243 , 4<log3x5 4 < \log_3 x \leq 5 , so f(x)=5 f(x) = 5 .
- For 244x365 244 \leq x \leq 365 , 5<log3x6 5 < \log_3 x \leq 6 , so f(x)=6 f(x) = 6 .

2. **Summing the values of f(x) f(x) **:
- We need to sum log3(i+1) \lceil \log_3 (i+1) \rceil for i i from 2 to 365.
- The sum can be broken down as follows:
i=2365log3(i+1)=i=231+i=492+i=10273+i=28814+i=822435+i=2443656 \sum_{i=2}^{365} \lceil \log_3 (i+1) \rceil = \sum_{i=2}^{3} 1 + \sum_{i=4}^{9} 2 + \sum_{i=10}^{27} 3 + \sum_{i=28}^{81} 4 + \sum_{i=82}^{243} 5 + \sum_{i=244}^{365} 6

3. Calculating each segment:
- For i=231 \sum_{i=2}^{3} 1 :
1(32+1)=12=2 1 \cdot (3 - 2 + 1) = 1 \cdot 2 = 2
- For i=492 \sum_{i=4}^{9} 2 :
2(94+1)=26=12 2 \cdot (9 - 4 + 1) = 2 \cdot 6 = 12
- For i=10273 \sum_{i=10}^{27} 3 :
3(2710+1)=318=54 3 \cdot (27 - 10 + 1) = 3 \cdot 18 = 54
- For i=28814 \sum_{i=28}^{81} 4 :
4(8128+1)=454=216 4 \cdot (81 - 28 + 1) = 4 \cdot 54 = 216
- For i=822435 \sum_{i=82}^{243} 5 :
5(24382+1)=5162=810 5 \cdot (243 - 82 + 1) = 5 \cdot 162 = 810
- For i=2443656 \sum_{i=244}^{365} 6 :
6(365244+1)=6122=732 6 \cdot (365 - 244 + 1) = 6 \cdot 122 = 732

4. Summing all segments:
2+12+54+216+810+732=1826 2 + 12 + 54 + 216 + 810 + 732 = 1826

5. Comparing with the number of steps:
- The total number of steps required is 1826.
- Given that we have 2000 steps, we can indeed order the 365 cards from smallest to largest.

The final answer is True

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.