Problem

Source: ELMO Shortlist 2023 C7

Tags: Elmo, combinatorics



A discrete hexagon with center \((a,b,c)\) \emph{(where \(a\), \(b\), \(c\) are integers) and radius \(r\) (a nonnegative integer)} is the set of lattice points \((x,y,z)\) such that \(x+y+z=a+b+c\) and \(\max(|x-a|,|y-b|,|z-c|)\le r\). Let \(n\) be a nonnegative integer and \(S\) be the set of triples \((x,y,z)\) of nonnegative integers such that \(x+y+z=n\). If \(S\) is partitioned into discrete hexagons, show that at least \(n+1\) hexagons are needed. Proposed by Linus Tang