Bài 5

Cho

n

là một số nguyên dương. Một tam giác Nhật Bản gồm

1+2+\cdots+n

hình tròn được sắp xếp thành hình tam giác đều sao cho với mỗi

i=1,2,\ldots,n

, hàng thứ

i

có đúng

i

hình tròn, trong đó đúng một hình được tô màu đỏ. Một đường đi ninja trong tam giác Nhật Bản là một dãy gồm

n

hình tròn thu được bằng cách xuất phát từ hàng trên cùng, sau đó liên tiếp đi từ một hình tròn tới một trong hai hình tròn ngay bên dưới nó, và kết thúc ở hàng dưới cùng. Theo

n

, hãy tìm giá trị lớn nhất của

k

sao cho trong mọi tam giác Nhật Bản luôn có một đường đi ninja chứa ít nhất

k

hình tròn đỏ.

Bước 5 trên 5: Giải hệ thức truy hồi để hoàn tất

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

Hiểu nôm na

Khai triển hệ thức truy hồi cho thấy tổng theo hàng tăng thêm gần đúng một đơn vị giá trị trung bình mỗi khi chỉ số hàng tăng gấp đôi, đây chính là cơ chế tạo ra đảm bảo dạng lôgarit.

S_n\ge cn+2r+1\ \text{for}\ n=2^c+r,\ 0\le r<2^c\implies\max_if(i,n)\ge c+1

Phân tích chi tiết

Viết $n=2^c+r$ với $0\le r<2^c$ , quy nạp theo $n$ bằng hệ thức truy hồi ở Bước 4 cho thấy $S_n\ge cn+2r+1$ (bước quy nạp tách thành hai trường hợp tùy theo $n+1$ có là lũy thừa của $2$ hay không, cả hai trường hợp đều khép kín phép quy nạp một cách gọn gàng). Chia cho $n$ , ta được $S_n/n\ge c+(2r+1)/n>c$ , và vì có một phần tử ở hàng $n$ ít nhất bằng trung bình $S_n/n$ , phần tử đó ít nhất bằng $c+1=\lfloor\log_2n\rfloor+1$ . Do đó mọi tam giác Nhật Bản đều có một đường đi ninja chứa ít nhất $\lfloor\log_2n\rfloor+1$ hình tròn đỏ, khớp với cấu trúc ở Bước 2 và chứng minh $k=\lfloor\log_2n\rfloor+1$ .