IMO 2023 Shortlist C3
Let n be a positive integer. We arrange 1 2 ¨¨¨ n circles in a triangle with n rows, such that the ith row contains exac...
Category: Combinatorics
Problem
Let n be a positive integer. We arrange 1 2 ¨¨¨ ` n circles in a triangle with n
rows, such that the ith
row contains exactly i circles. The following figure shows the case n “ 6.
n “ 6
In this triangle, a ninja-path is a sequence of circles obtained by repeatedly going from a
circle to one of the two circles directly below it. In terms of n, find the largest value of k such
that if one circle from every row is coloured red, we can always find a ninja-path in which at
least k of the circles are red.
(Netherlands)