Bài toán: Bắt đầu với dãy: S=(a,b,c,d) của các số nguyên không âm. Đặt S_1=T(S)=(|a-b|,|b-c|,|c-d|,|d-a|). Tương tự S_2=T(S_1). Hỏi có tồn tại S_i sao cho S_i=(0;0;0;0)
Giải
Chúng ta thử vài trường hợp:
(0, 3, 10, 13) → (3, 7, 3, 13) → (4, 4, 10, 10) →
(0, 6, 0, 6) → (6, 6, 6, 6) → (0, 0, 0, 0)
(8, 17, 3, 107) → (9, 14, 104, 99) → (5, 90, 5, 90) →
(85, 85, 85, 85) → (0, 0, 0, 0),
(91, 108, 95, 294) → (17, 13, 99, 203) → (4, 86, 104, 186) →
(82, 18, 82, 182) → (64, 64, 100, 100) → (0, 36, 0, 36) →
(36, 36, 36, 36) → (0, 0, 0, 0).
1) Đặt max S là phần tử lớn nhất của S. Khi đó max S_{i+1} \le max S_i và max S_{i+4}< max S_i ( Vì khi max S_{i+1} = max S_i Khi (S_i=(0, S_{i+1},a,b) tới S_{i+3} nó sẽ giảm)
2) Sau nhiều nhất 4 bước, tất cả 4 số sẽ trở thành số chẵn. Thật vậy ta sẽ xét đồng dư 2. Do tính đối xứng nên ta chỉ xét trường hợp này ( các trường hợp khác tương tự) :
0001 → 0011 → 0101 → 1111 → 0000 và 1110 → 0011. Vì thế sau nhiều nhất 4 bước tất cả các số sẽ chia hết cho 2, sau nhiều nhất 8 bước chia hết 2^2,..sau nhiều nhất 4k bước thì các số sẽ chia hết 2^k cho k thật lỡn ta sẽ có tất cả cá số đều bằng 0
Không có nhận xét nào:
Đăng nhận xét