Induction problem basics

Question

For which values of $n \in \mathbb{N}$ can a group of $n ≥ 1$ people be divided into teams, where each team consists of exactly $4$ or $7$ people? Use induction to prove your answer correct.

I just made a long list of $n$ values and saw that after $n=18$, all values of $n$ can be split up in terms of $4$ or $7$. That's about it...how do I start?

Thanks!

The general result here is discussed under the (Frobenius) coin problem & see also this question asked today on a similar theme. — Joffan, Oct 10 '17 at 17:29
@Joffan It's also known as the McNuggets problem, since McNuggets can be bought only in certain increments. — Patrick Stevens, Oct 10 '17 at 17:32
Yes, the McNugget paragraph at the link I gave gives a good example of setting up a multi-part base case for a simple induction proof. — Joffan, Oct 10 '17 at 17:34

score 2 · Answer 1 · answered Oct 10 '17 at 17:48

2

Base $n=18,19,20,21$: $$18 = 1\cdot 4+2\cdot 7$$

$$19 = 3\cdot 4+1\cdot 7$$

$$20 = 5\cdot 4+0\cdot 7$$

$$21 = 0\cdot 4+3\cdot 7$$

Now $n\to n+4$:

By I.H. $n= 4a+7b$ for some $a,b\geq 0$ Then $n+4 = 4(a+1)+7b$ and we are done.

answered Oct 10 '17 at 17:48

nonuser

90,026

Unusual induction, but giving an easy solution of the problem. Well done!(+1) – Peter Oct 10 '17 at 18:06
Can you explain the multiple base cases? I've only ever seen it solved for n and n+1 so this n+4 thing is new. – VV6570 Oct 10 '17 at 19:34

score 0 · Answer 2 · answered Oct 10 '17 at 17:31

0

We want to show that $$4a+7b=n$$ has a non-negative integer solution for every $n\ge 18$ :

For $18$, we have a solution because of $1\cdot 4+2\cdot 7=18$

Suppose , we have a non-negative integer solution of $4a+7b=n$ , where $n\ge 18$

We have to show that we can solve $4a'+7b'=n+1$ as well.

If $b>0$, then we can take $a'=a+2$ and $b'=b-1$ Then, we have $$4a'+7b'=4a+8+7b-7=4a+7b+1=n+1$$

If $b=0$, then we have $a\ge 5$ because otherwise $4a+7b<18$ Taking $a'=a-5$ and $b'=b+3$ gives $$4a'+7b'=4a-20+7b+21=4a+7b+1=n+1$$

This completes the proof.

answered Oct 10 '17 at 17:31

Peter

84,454

Why did you work with b > 0 and b = 0? Don't you have to do it for a > 0 and a = 0 as well ? – VV6570 Oct 10 '17 at 17:54
No, because the cases $b=0$ and $b>0$ cover all possible solutions. In the case $b=0$, we cannot take $b'=b-1$ because $b'$ must be non-negative, therefore we must use another transformation. – Peter Oct 10 '17 at 18:04

score 0 · Answer 3 · answered Oct 10 '17 at 17:40

hint:

we need to check basis scenario (18 = 14 + 4) assume that we proved it for n so there are a,b >= 0: n = 4a + 7b

now lets look on n+1, if b >= 1 so n+1 = 4(a+2) + 7(b-1) otherwise b = 0 and because n >= 18 then a >=5 means n = 4a >= 20 so n+1 >= 21 so n+1 = 4(a-5)+21

Induction problem basics

3 Answers3