Advanced Math/Proof by Induction
Hi Clyde I have a discrete maths course coming up after finishing Differential Equations and I purchased the book for study prior to the course and am lost. This question is number 37 page 267 Discrete Maths with Applications by Epp.
On the Outside of the rim of a circular disk the integers from one to thirty are painted in random order. Prove there must be three successive integers whos sum is at least forty-five.
I have to prove this by induction.
Let P equal set of numbers from one to thirty randomized
Let Q equal the highest of the set
I just need to know where this went wrong if it did.
The proof you've presented really doesn't make sense for two reasons:
1. You aren't using induction. In fact, this is not
a statement that has any parameter "n" for which you could prove it
2. You haven't given a proof that there should be any three consecutive numbers totaling 45, unless 30, 29, and 28 are consecutive. The distribution is random -- you can't assume those three occur together.
Now, I will prove this without using induction. This is a very common problem that has a simple solution -- a solution that does not
use induction. I've looked up the problem in the text by Epp. It does not
specify that you should use induction (although it is in the section about induction). So you may be wrong when you say "[you] have to prove this by induction." In fact, this problem appears to be a non-induction question thrown in to help you with the following problem (number 38).
Consider the numbers 1 through 30 arranged in a circle. There are 30 possible triples, and you can sum them all. In other words, if they are arranged as follows:
a = 27
a = 13
a = 11
a = 2
a = 30
a = 1
a = 21
a = 7
Then at each position, you can form the sum s[i] = a[i] + a[i+1] + a[i+2], where if i=29 or 30, you wrap around the ordering. So, in this example:
s = 51
a = 26
a = 43
a = 33
a = 55
a = 47
Well, in this example already there are three that total greater than 45, so that's good.
To prove this, consider the sum of all s[i], that is:
S = s + s + s + ... + s + s
Each of the terms a, a, ..., a are counted three times, so you get:
S = 3 ( a + a + ... + a )
Since the order doesn't matter, you get:
S = 3 ( 1 + 2 + ... + 30 ) = 1395
Now, this is important because the average of the s[i] is S/30 = 46.5
For that reason, if 46.5 is the average s[i], at least one s[i] should be at least 45 (in fact, one of the s[i] should be at least 47).
And that's it. No induction required.
You can use this methodology for any number. The idea is you have 1 through n arranged in a circle, and you want to ensure that k consecutive numbers add up to some total (call this M). The above is the case is n=30 and k=4, but for any n and k, you get:
a through a[n] some permutation of 1 through n.
s through s[n] defined as the sum s[i] = a[i] + a[i+1] + ... a[i+k]
S = k n (n+1) / 2
s[i] average = k (n+1) / 2
which means that there is some s[i] that is at least M = k(n+1)/2, rounded up.
This argument is much better than any inductive argument you could devise.
Now, if you feel bound to prove this by induction, you can. But you have to come up with some statement that you can apply induction to at all (that is, a statement with some "n" in it) to which you could apply induction. That's the reason I wanted to prove the above first -- so that you know where to find this statement.
What you want to show, presumably, is that if you arrange 1 through n in a circle, you get at least 3(n+1)/2 rounded down as a sum of 3 consecutive numbers. If you prove this for all n, then that includes n=30, which is the one you wanted.
For n=3, this is trivial, since 3(3+1)/2 = 6, which is the only sum you get (1+2+3). That is the base case.
Assuming it's true for some value n, consider the arrangement of 1 through n+1 around the table. You can remove n+1 from its position temporarily and consider whether you already have 3(n+2)/2 somewhere on the table. If not, some argument can tell you that adding n+1 to the arrangement must make this happen. To have 3(n+1)/2 but not 3(n+2)/2 means the numbers are very evenly distributed -- no matter where the n+1 goes, it will be enough (with two of its neighbors) to get you to 3(n+2)/2
You could also do induction on the parameter "k" (or a double-induction, possibly).
But, as I stated, induction is not the most direct way to prove this statement (even with parameters like "n" or "k") and the problem does not
require induction, as stated, so I suggest you just prove it directly, as above.