6
$\begingroup$

I can intuitively see why this is true:

  1. Let us assume $n = \alpha \times 4 + \beta \times 5$ with $\alpha,\beta \in \mathbb{N} \cup \{0\}$.
  2. $\forall n \in \mathbb{N} \cup \{0\}$: $n \div 4$ will yield a remainder $r \in \mathbb{N} \cup \{0\}$, $0 \le r \lt 4$.
  3. $r$ can be 'split' into 1s, and each of those 1s can be added to one of the 4s that go into $n$ to turn them into 5s. Therefore, if $n = a\times4 + r \Rightarrow n = (a-r)\times4 + r\times5$ with $a \in \mathbb{N}\cup\{0\}$.
  4. That is the reason why this only works for $n \ge 12=3\times4$: it's readily obvious by the pigeonhole principle, and if $a \lt 3 \Rightarrow \exists \ r \ | \ (a-r) \lt 0 \Rightarrow \alpha \lt 0$ which contradicts the initial assumption.

Could this give me a start for the inductive proof? I don't know if induction would be the most straightforward or elegant way to prove it, but I have to do it as an exercise (my Elementary Number Theory textbook actually suggests proving it individually for $n\in[12,16]$ and then using 16 as $n_0$). I understand how induction works but I can't think of a way to translate this problem into it. I would also like some help with formally expressing step 3 of my proof.

$\endgroup$
3
  • $\begingroup$ Notice that the set $S$ of numbers $n\geq12$ that cannot be written $n=4a+5b$ is either empty, either has a minimum element $n_0$ (since $S$ is then a nonempty set of nonnegative integers, or a subset of $\Bbb N$, which is well ordered). But then $n_0$ must be $\leq15$, otherwise one of $n_0-4$ or $n_0-5$ would be in $S$, contradiction. Thus you just have to check $12,13,14,15$. Almost the same argument will give you an induction proof. $\endgroup$
    – Jean-Claude Arbaut
    May 25, 2015 at 16:24
  • $\begingroup$ Looks like FLT. :p $\endgroup$
    – Sufyan Naeem
    May 25, 2015 at 16:36
  • 1
    $\begingroup$ Your points 2 and 3 taken together already provide a nicer proof than the one your textbook has in mind (and explained by jca). Your proof hides the induction inside a standard construction (division with remainder). Kudos for that. $\endgroup$
    – Rob Arthan
    May 25, 2015 at 16:39

4 Answers 4

Reset to default
6
$\begingroup$

I think your approach could easily be used for induction and is at least as good as the textbook suggestion of multiple base cases (which is also a perfectly adequate proof).

So to build on your ideas, we have:

Base case
$12=4+4+4$

Inductive step
Assume true for $k\ge 12$. Note that we have at least $3$ terms in the decomposition of $k$. We must therefore have either (a) three $5$s or (b) at least one $4$.

For a $4$-$5$ decomposition of $k+1$: in case (a) substitute four $4$s for the three $5$s in the decomposition of $k$, and in case (b) substitute a $5$ for a $4$.

Note how this links to the ideas in the question: the greatest possible remainder value is $3$ - that's the case that gives three $5$s in the decomposition. The subsequent integer has remainder $0$, giving no $5$s in the decomposition - so the three $5$s will be replaced by four $4$s. The base case is chosen so that there is a valid partition that has (at least) three components. $12$ is the smallest such.

For clarity, the textbook was (I think) expecting that you demonstrate the existence of a valid partitions from $12$ to $15$, and then use induction for $k\ge 16$ with the inductive assumption that there is a solution for $k-4$, and then add another $4$ to that decomposition.

$\endgroup$
5
  • $\begingroup$ I don't entirely understand how that works – could you explain the inductive step a bit further? By 3 5s or at least one 4, do you mean the resulting terms after r is distributed among three of them, regardless of all the other terms which would remain 4s? Thanks! $\endgroup$
    – reggaelizard
    May 25, 2015 at 20:21
  • $\begingroup$ I started off with using your idea of distributing the remainder after division by 4 - but the final wording has perhaps diluted that link. Effectively your method accumulates $3$ terms that are $5$, then turns them into $4$ $4$s on the next step. I tried to reflect that in the induction. $\endgroup$
    – Joffan
    May 25, 2015 at 20:28
  • $\begingroup$ Do you mean that $16=3\times5+1$, and you can then sum a 1 from each 5 to the remainder 1 so you end up with $4\times4$? My biggest issue is that I don't understand how it translates into $k\gt12$ or $k\gt16$. $\endgroup$
    – reggaelizard
    May 25, 2015 at 20:46
  • 1
    $\begingroup$ The 15-16 transition is an outcome, but the link to your process is that the greatest possible remainder value is $3$ - that's the case that gives three $5$s in the decomposition, and then the next value has remainder $0$, so the three $5$s will be replaced by four $4$s. The base case is chosen so that (a) there is a valid partition that (b) has three components. $12$ is the smallest such. $\endgroup$
    – Joffan
    May 25, 2015 at 21:12
  • 1
    $\begingroup$ I understand it much better now! I'm gonna try doing it in mathematical terms and I'll just ask questions here if I have any doubts. Thanks a lot for your help! $\endgroup$
    – reggaelizard
    May 25, 2015 at 21:23
4
$\begingroup$

$12=4+4+4$

$13=4+4+5$

$14=4+5+5$

$15=5+5+5$

Now, suppose $n>15$; as the inductive hypothesis you can assume that any number $m$ with $12\le m<n$ can be written as sum of fours and fives. Then $n-4>11$ can be written as sum of fours and fives, which implies the thesis also for $n$.

This is indeed a constructive approach: divide $n\ge12$ by $4$, with remainder $r$, that is, $n=4q+r$, with $0\le r<4$. Then $q\ge3$, as $n\ge12$.

If $r=0$ we are done.

If $r=1$, $n=4(q-1)+5$

If $r=2$, $n=4(q-2)+5+5$

If $r=3$, $n=4(q-3)+5+5+5$

$\endgroup$
2
  • $\begingroup$ Yes, that's the multiple base case approach that the textbook talks about. $\endgroup$
    – Joffan
    May 25, 2015 at 16:58
  • $\begingroup$ @Joffan It's very similar to the proof for existence of quotient and remainder of the division of $a$ by $b>0$: if $a=0$, the result is true; suppose $a>0$ and the result holds for any number less than $a$; if $a<b$, there's nothing to prove, otherwise $0\le a-b<a$ and so $a-b=bq+r$ with $0\le r<b$, so $a=b(q+1)+r$. This gives a procedure for finding $q$: just subtract $b$ as many times as you can from $a$. $\endgroup$
    – egreg
    May 25, 2015 at 17:40
1
$\begingroup$

Just to see the pattern: $12=4+4+4$. $13=4+4+5$. $14=4+5+5$. $15=5+5+5$. $16=4+4+4+4$.

Base case: $12$.

Note that $12=4+4+4$.

Inductive case.

Assume that $n$ can be written as $n=4x+5y$ with $x,y \in \mathbb{N}_0$.

If $x>0$, then $n=4(x-1)+4+5y$ so $n+1=4(x-1)+5(y+1)$.

If $x=0$, then $n=5y$ so $n+1=5y+1$. Note $y\geq4$ (we handled the case $n=15$). So then $n+1=5(y-3+3)+1=5(y-3)+16=5(y-3)+4+4+4+4$.

$\endgroup$
0
0
$\begingroup$

In general, the Chicken McNugget theorem says that for any coprime integers $p, q$, the largest integer that is not of the form $px + qy$ is $pq - p - q$. So in this case, $11$ is the largest integer which cannot be expressed as so, so every integer $\geq 12$ can.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .