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 4 trên 5: Một hệ thức truy hồi kiểu Dirichlet cho tổng theo hàng

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

Hiểu nôm na

Cộng dồn các giá trị đường đi tốt nhất trên toàn bộ một hàng rồi so sánh với hàng kế tiếp cho thấy tổng phải tăng nhanh hơn hẳn tuyến tính, bởi vì theo nguyên lý Dirichlet, giá trị lớn nhất trong một hàng đã chiếm một phần đáng kể của tổng hàng đó.

S_j=\sum_{i=0}^{j}f(i,j),\qquad S_{j+1}\ge S_j+\left\lceil\dfrac{S_j}{j}\right\rceil+1

Phân tích chi tiết

Đặt $S_j=\sum_{i=0}^jf(i,j)$ . Theo nguyên lý Dirichlet, có một phần tử $f(m,j)$ trong hàng $j$ ít nhất bằng trung bình $S_j/(j+1)$ , và khi tái sử dụng phần tử lớn nhất này để hình thành đóng góp của nó cho hàng $j+1$ (qua cả hai nhánh dẫn tới nó, cùng với $+1$ bắt buộc đến từ hình tròn đỏ riêng của hàng $j+1$ ), ta thu được hệ thức truy hồi $S_{j+1}\ge S_j+\left\lceil S_j/j\right\rceil+1$ .