Combinatorics · Lattice paths · Monotone paths · Covering arguments · Extremal configurations
A rectangular grid of size \(7 \times 9\) is given: seven rows of cells and nine columns of cells, as in the figure. At the bottom-left node of the grid sits a colony of ants, and at the top-right node is their anthill. Every one of the remaining nodes carries a single grain of rice.
Each ant walks from the colony to the anthill along the edges of the grid, moving only to the right or upwards. On its way it picks up every grain of rice it meets, and once it reaches the anthill it stays there.
What is the smallest number of ants the colony could contain if all the grains of rice are to be collected?
Sign in to check answers, open hints, read the full solution, and track your progress. Statements are always free.
Slovenian High School Mathematics Competition for Vega Awards (MaSSA), drzavno (national) round 2015, 1. letnik, category A, problem 4. Organized by DMFA Slovenije (Society of Mathematicians, Physicists and Astronomers of Slovenia). Source