Bài 3

Cho

a_1,a_2,a_3,\ldots

là một dãy vô hạn các số nguyên dương, và cho

N

là một số nguyên dương. Giả sử rằng, với mỗi

n>N

, số

a_n

bằng số lần

a_{n-1}

xuất hiện trong danh sách

(a_1,a_2,\ldots,a_{n-1})

. Chứng minh rằng ít nhất một trong hai dãy

a_1,a_3,a_5,\ldots

và

a_2,a_4,a_6,\ldots

là tuần hoàn kể từ một lúc nào đó.

Bước 1 trên 6: Bức tranh các tháp

Bước trước Bước tiếp

Hiểu nôm na

Hãy hình dung đặt một khối được đánh số cho mỗi số hạng của dãy vào tháp mang nhãn bằng giá trị của số hạng đó; khi đó mỗi số hạng mới sau chỉ số N chính là chiều cao hiện tại của tháp mà số hạng trước đó trỏ tới.

M=\max(a_1,\ldots,a_N)

Phân tích chi tiết

Đặt $M=\max(a_1,\ldots,a_N)$ và hình dung một dãy các tháp được đánh số $1,2,3,\ldots$ ; với $i=1,2,\ldots$ , số hạng $a_i$ thêm một khối vào tháp $a_i$ . $N$ khối đầu tiên được gọi là khối đỏ; với $i>N$ , khối $a_i$ được đặt vào tháp $a_i$ , và chiều cao mới của tháp đó sau khi đặt khối chính là $a_i$ , nghĩa là khối $a_i$ nằm đúng ở độ cao $a_i$ trong tháp của nó — phản ánh việc $a_i$ đếm số lần $a_{i-1}$ đã xuất hiện cho tới thời điểm đó.