Maths Olympiad Prep

Library / /301 of 397

Algebra Difficulty 6.6 National Olympiad Prove it Taiwan

Given a positive integer MM, define a sequence a0,a1,a2,a_0, a_1, a_2, \dots as follows: a0=2M+12a_0 = \frac{2M+1}{2}, and for all k=0,1,2,k = 0, 1, 2, \dots, let ak+1=akaka_{k+1} = a_k \lfloor a_k \rfloor.
Find all positive integers MM such that in the sequence a0,a1,a2,a_0, a_1, a_2, \dots defined above, at least one term is an integer.
(Remark: [x][x] denotes the greatest integer not exceeding the real number xx.)

Solution

MM 可以是任何大於或等於 2 的正整數,即 M2M \ge 2
首先對所有的非負整數 kk,定義 bk=2akb_k = 2a_k。則有
bk+1=2ak+1=2akak=bkbk2. b_{k+1} = 2a_{k+1} = 2a_k \lfloor a_k \rfloor = b_k \left\lfloor \frac{b_k}{2} \right\rfloor.
因為 b0b_0 是整數 2M+12M+1,所以數列 bk\langle b_k \rangle 的每一項都是整數。
用歸謬法。如果 ak\langle a_k \rangle 的每一項都不是整數,則 bk\langle b_k \rangle 的每一項都是奇數。故
bk+1=bkbk2=bk(bk1)2(1) b_{k+1} = b_k \left\lfloor \frac{b_k}{2} \right\rfloor = \frac{b_k(b_k-1)}{2} \quad (1)
所以
bk+13=bk(bk1)23=(bk3)(bk+2)2(2) b_{k+1} - 3 = \frac{b_k(b_k-1)}{2} - 3 = \frac{(b_k-3)(b_k+2)}{2} \quad (2)
對所有的 k0k \ge 0 均成立。
b03>0b_0 - 3 > 0。則由 (2) 式可推得 bk3>0b_k - 3 > 0 對所有的 k0k \ge 0 均成立。現在對每一個 k0k \ge 0,定義 ckc_k 為整除 bk3b_k - 3 之 2 的最高乘幂 (即 2ck(bk3)2^{c_k} \parallel (b_k - 3))。因為每一個 bk3b_k - 3 都是偶數,所以 ckc_k 都是正整數。
注意到 bk+2b_k+2 總是奇數。故由 (2) 式知 ck+1=ck1c_{k+1} = c_k - 1。於是 c0,c1,c2,c_0, c_1, c_2, \dots 為嚴格遞減的正整數數列,此為不可能。故 b03<0b_0 - 3 < 0,即 M=1M = 1
M=1M = 1 時,ak\langle a_k \rangle 為常數數列 32\frac{3}{2}。所以本題解答為 M2M \ge 2

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 translated into English from zh; metadata (topic, difficulty) added by this project.