Maths Olympiad Prep

Library / /30 of 264

Combinatorics Difficulty 5.0 AIME, harder Prove it Romania

If nn is a positive integer, we will call a triple (x,y,z)(x, y, z) of positive integers of type nn if x+y+z=nx + y + z = n. Denote s(n)s(n) the number of triples of type nn.
a) Prove that there exists no positive integer nn such that s(n)=14s(n) = 14.

Solution

Let us count the triples (x,y,z)(x, y, z) of positive integers such that x+y+z=nx + y + z = n, where n3n \ge 3 is a given integer. One can assign to xx any value from 11 to n2n-2. If x=1x=1, then, taking into account that z1z \ge 1, yy can take n2n-2 values: from 11 to n2n-2. If x=2x=2, then yy can take n3n-3 values, ..., if x=n2x=n-2, then yy can take only the value 11. This shows that the number of triples of type nn is
s(n)=1+2+3++(n3)+(n2)=(n2)(n1)2. s(n) = 1 + 2 + 3 + \dots + (n-3) + (n-2) = \frac{(n-2)(n-1)}{2}.

a) If there exists nn such that s(n)=14s(n) = 14, then (n2)(n1)=28(n-2)(n-1) = 28, which is impossible: if n6n \le 6, then (n2)(n1)20(n-2)(n-1) \le 20 and if n7n \ge 7, then (n2)(n1)30(n-2)(n-1) \ge 30.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.