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 1 trên 5: Phát biểu đáp số
Bước trướcBước tiếp
Hiểu nôm na

Việc nhân đôi số hàng gần như chỉ khiến ta phải chấp nhận thêm đúng một hình tròn đỏ không thể tránh khỏi, đây chính xác là cách lôgarit cơ số hai hoạt động.

k=⌊log⁡2n⌋+1k=\lfloor\log_2 n\rfloor+1
Phân tích chi tiết

Đáp số cần tìm là k=⌊log⁡2n⌋+1k=\lfloor\log_2n\rfloor+1; phần còn lại của lời giải chứng minh rằng có một tam giác buộc mọi đường đi chỉ gặp nhiều nhất từng ấy hình tròn đỏ, và mọi tam giác đều đảm bảo có một đường đi gặp ít nhất từng ấy hình tròn đỏ.