Track / Stage 5 / 347 of 400 #947 of 1964

Problem 947

AIME late

Number theory Difficulty 5.9 Prove it

Show that any natural number $n$ can be represented in the form $n=C_{x}^{1}+C_{y}^{2}+C_{z}^{3}$ , where $x, y, z-$ are such integers that $0 \leq x<y<z$ , or $0=x=y<z$ .

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Let $z$ be the largest number for which $C_{z}^{3} \leq n$ . Then the "remainder" $r0$ , let $y$ be the largest number for which $C_{y}^{2} \leq r$ . In this case, the number $r-C_{y}^{2+1}<C_{y+1}^{2}-C_{y}^{2}=C_{y}^{1}$ can be written as $C_{x}^{1}$ , where $x<y$ .

On the other hand, the largest number that can be represented in this form using $C_{z-1}^{3}$ is

$C_{z-1}^{3}+C_{z-2}^{2}+C_{z-3}^{1}<C_{z-1}^{3}+C_{z-2}^{2}+C_{z-3}^{1}+C_{z-3}^{0}=C_{z-1}^{3}+C_{z-2}^{2}+C_{z-2}^{1}=C_{z-1}^{3}+C_{z-1}^{2}=C_{z}^{3},$

therefore, it is not possible to represent our number $n$ in any other way.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.