MathLabs

Bài 5

Cho nn là một số nguyên dương. Một tam giác Nhật Bản gồm 1+2+⋯+n1+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,…,ni=1,2,\ldots,n, hàng thứ ii có đúng ii 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 nn 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 nn, hãy tìm giá trị lớn nhất của kk 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 kk hình tròn đỏ.
Bước 2 trên 5: Một cấu trúc nhân đôi giới hạn mọi đường đi
Bước trướcBước tiếp
Hiểu nôm na

Nhóm các hàng thành các khối có kích thước 1, 2, 4, ..., 2^(e-1) và đặt các hình tròn đỏ sao cho một đường đi đi xuống chỉ có thể gặp đúng một hình tròn đỏ trong mỗi khối, nhờ đó tổng số hình tròn đỏ bị chặn ở đúng một hình mỗi khối.

n=2e−1  ⟹  some triangle admits no path with more than e red circlesn=2^e-1\implies\text{some triangle admits no path with more than } e \text{ red circles}
Phân tích chi tiết

Với n=2e−1n=2^e-1, ta chia các hàng thành ee nhóm liên tiếp có kích thước 1,2,4,…,2e−11,2,4,\ldots,2^{e-1} (hàng 11; các hàng 22–33; các hàng 44–77; …; các hàng 2e−12^{e-1}–2e−12^e-1). Trong mỗi nhóm, các hình tròn đỏ có thể được đặt (như trong các hình minh họa gốc) sao cho bất kỳ đường đi ninja nào, một khi đã chọn một nhánh bên trong một nhóm, sẽ không thể chạm tới các hình tròn đỏ khác của cùng nhóm đó trước khi rời khỏi nhóm. Do đó một đường đi ninja gặp nhiều nhất một hình tròn đỏ mỗi nhóm, tức là nhiều nhất e=⌊log⁡2n⌋+1e=\lfloor\log_2n\rfloor+1 hình tròn đỏ tất cả, cho thấy kk không thể vượt quá giá trị này.