IMO 2013 Shortlist C4
Let n be a positive integer, and let A be a subset of t1,...,nu. An A-partition of n into k parts is a representation of...
Category: Combinatorics
Problem
Let n be a positive integer, and let A be a subset of t1,...,nu. An A-partition of n into k
parts is a representation of n as a sum n “ a1 ¨¨¨ ak, where the parts a1,...,ak belong to A
and are not necessarily distinct. The number of different parts in such a partition is the number
of (distinct) elements in the set ta1,a2,...,aku.
We say that an A-partition of n into k parts is optimal if there is no A-partition of n into r
parts with r ă k. Prove that any optimal A-partition of n contains at most 3
?
6n different parts.
(Germany)