Maths Olympiad Prep

Library / /156 of 299

Algebra Difficulty 6.5 National Olympiad Prove it Iran

Find the maximum possible value of integer kk for which there exist distinct real numbers x1,x2,,xkx_1, x_2, \dots, x_k greater than 11 such that
 1i,jk:xi[xj]=xj[xi] \forall\ 1 \le i,j \le k : x_i^{[x_j]} = x_j^{[x_i]}
(By [x][x] we mean the greatest integer less than or equal to xx.)

Solution

We start with some lemmas.

Lemma. For positive integers m>3m > 3 and k>2k > 2 we have mm+k>(m+k+1)mm^{m+k} > (m+k+1)^m.
Proof. We must show that mk>(m+k+1m)m=(1+k+1m)mm^k > \left(\frac{m+k+1}{m}\right)^m = \left(1 + \frac{k+1}{m}\right)^m. But we have (1+k+1m)m<ek+1\left(1 + \frac{k+1}{m}\right)^m < e^{k+1} and so
(1+k+1m)m<ek+1<(2.8)k+1(2.8)43k<4kmk. \left(1 + \frac{k+1}{m}\right)^m < e^{k+1} < (2.8)^{k+1} \le (2.8)^{\frac{4}{3}k} < 4^k \le m^k.

Lemma. For all positive integers m>4m > 4 and n>5n > 5, we have em>(m+1)3e^m > (m+1)^3 and 2n>(n+1)22^n > (n+1)^2.
Proof. The proof of both parts are consequences of some elementary inductions.

Now for the main problem suppose that kk is the largest possible integer and x1<x2<<xkx_1 < x_2 < \dots < x_k are kk numbers satisfying the condition. First note that if [xi]=[xj][x_i] = [x_j] for some i,ji, j we have
xi[xi]=xj[xj]    xi=xj    i=j x_i^{[x_i]} = x_j^{[x_j]} \implies x_i = x_j \implies i = j
This means that [xi][x_i]'s are distinct and so [xk][xi]ki[x_k] - [x_i] \ge k - i. We claim that k4k \le 4. Assume to the contrary that k>4k > 4.

* If [x2]>3[x_2] > 3 since [xk][x2]>2[x_k] - [x_2] > 2 using the first lemma we get ([xk]+1)[x2]<[x2][xk]([x_k] + 1)^{[x_2]} < [x_2]^{[x_k]}. But on the other hand we have
[x2][xk]x2[xk]=xk[x2]([xk]+1)[x2] [x_2]^{[x_k]} \le x_2^{[x_k]} = x_k^{[x_2]} \le ([x_k] + 1)^{[x_2]}
This leads to a contradiction and implies that [x1]<[x2]3[x_1] < [x_2] \le 3.

* If [x2]=3[x_2] = 3, then
3[xk]x2[xk]=xk[x2]=xk3([xk]+1)3 3^{[x_k]} \le x_2^{[x_k]} = x_k^{[x_2]} = x_k^3 \le ([x_k] + 1)^3
By the second lemma, we deduce that [xk]4[x_k] \le 4 and therefore k4k \le 4 which contradicts with our assumption.

* If [x2]=2[x_2] = 2, then similar to the previous part we have
2[xk]x2[xk]=xk[x2]=xk2([xk]+1)2 2^{[x_k]} \le x_2^{[x_k]} = x_k^{[x_2]} = x_k^2 \le ([x_k] + 1)^2
and so by the second lemma [xk]5[x_k] \le 5 therefore k5k \le 5. Now if k=5k = 5, then [xi]=i[x_i] = i for all 1i51 \le i \le 5 which contradicts, because
6>x5=x15=x12×x13=x2×x32×3=6 6 > x_5 = x_1^5 = x_1^2 \times x_1^3 = x_2 \times x_3 \ge 2 \times 3 = 6
Therefore k4k \le 4. For k=4k = 4, the numbers x1=313x_1 = 3^{\frac{1}{3}}, x2=323x_2 = 3^{\frac{2}{3}}, x3=3x_3 = 3, x4=343x_4 = 3^{\frac{4}{3}} satisfy the condition, because [xi]=i[x_i] = i and so xi[xj]=3ij3=xj[xi]x_i^{[x_j]} = 3^{\frac{ij}{3}} = x_j^{[x_i]}. So the proof is complete and the desired maximum is 44. ■

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.