Prove that if n>=12 then n can be written as a sum of 4's and 5's

Printable View

- Feb 12th 2007, 06:54 PMSingularprove by induction
Prove that if n>=12 then n can be written as a sum of 4's and 5's

- Feb 12th 2007, 10:33 PMCaptainBlack
See this thread for the general idea.

Though in this case you will be assing 4 4's and taking away 3 5's. Take

a bit of care to make sure that you have enough 5s to take 3 away.

So suppose you can make n as a sum of 4's and 5's, add 4 4's, then if there

are three or more 5's take 3 5's out, you now have a total of n+1.

If there are no 5's take 5 4's (at this point we have a minimum of 7 of them)and replace with 4 5's, So now the 3 5's can be removed leaving a total of

n+1.

RonL - Feb 12th 2007, 11:32 PMSoroban
Hello, Singular!

Quote:

Prove that if n__>__12, then n can be written as a sum of 4's and 5's

I haven't devised an inductive proof, but more of an intuitive one.

Suppose*n*is a multiple of 4: . n = 4a, for*a*__>__3.

. . (Our number has at least three 4's.)

We can make*n + 1*by adding a 5 and removing a 4.

We can make*n + 2*by adding another 5 and removing another 4.

We can make*n + 3*by adding another 5 and removing another 4.

The next number is*n + 4*, which is the next multiple of 4.

. . And we can repeat the procedure.

Therefore, we can construct any number*n*__>__12.