Author |
Topic: 4 out of 7 numbers (Read 1258 times) |
|
jollytall
Senior Riddler
Gender: 
Posts: 585
|
 |
4 out of 7 numbers
« on: Mar 28th, 2014, 11:30pm » |
 Quote  Modify
|
Proove that from 7 natural numbers we can always choose 4 so that the total of them is devidable by 4.
Try a general solution that works for larger numbers too (8 out of 15, etc.)
|
|
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: 4 out of 7 numbers
« Reply #1 on: Mar 31st, 2014, 7:36am » |
Quote Modify
|
I'll go straight to the general proof:
Base case:Any single natural number will always be divisible by 1.
Induction step: If, for a power of 2, 2n, you can always find 2n numbers that sum to a multiple of 2n out of any given set of 2n+1-1 numbers, then you can guarantee to be able to find a set of 2n+1 numbers that sum to a multiple of 2n+1 given any set of 2n+2-1 numbers:
Proof:
| hidden: | Take 2n+1-1 of the numbers (leaving 2 lots of 2n numbers aside for now) and find 2n of them that sum to a multiple of 2n. Replace those with the first set aside lot of numbers, find a second set that sum to a multiple of 2n from the new set of 2n+1-1 numbers, and repeat with the final set aside lot of numbers.
At this point, you have three distinct subsets of the set of 2n+2-1 numbers, each of which has 2n numbers that sum to a multiple of 2n. Each of them is either an odd multiple or an even multiple, so, by the pigeonhole principle, you must have a pair that are the same parity. Combining those two sets, you'll get a set of 2n+1 numbers which must sum to a multiple of 2n+1 |
Hence, by induction, for any power of 2, 2n, you can find a subset of 2n numbers whose sum is divisible by 2n in any given set of 2n+1-1 numbers.
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: 4 out of 7 numbers
« Reply #2 on: Mar 31st, 2014, 11:55am » |
Quote Modify
|
Very nice and even more elegant than the one I had.
My was also a full induction, using 2 and n to come up with n+1. The logic was, e.g. for n=15. Take any 3 and you can be sure to find 2 of them that give an even sum. The third one goes back to the pack. Repeat it 6 more times to have 7 pairs with even sums. Take one pair as one number and divide it by two. Now we have 7 numbers. We know that we can choose 4 that add up to 0 mod 4. Since these are pairs and halves, so we found actually 8 that gives 0 mod 8.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 4 out of 7 numbers
« Reply #3 on: Apr 1st, 2014, 6:59am » |
Quote Modify
|
on Mar 31st, 2014, 11:55am, jollytall wrote:| Very nice and even more elegant than the one I had. |
|
We're both describing the same process - pairing numbers with the same parity then pairing pairs with the same parity, then pairing quads with the same parity, and so on - the only slight difference is that your approach is more efficient than a naive implementation of mine - mine would recurse down to forming three pairs from a subset of 7, use two of them to form a quad and forget the other pair, using it and the 7th number as three of the next subset of 7 to make three pairs again to make a second quad. After making the third quad, one of the quads is forgotten, its pairs dissolved and used (along with another abandoned pair and an odd number) as part of the next subset of 15 - and so on. If you don't remember the pairs, etc you've already found, then you can end up forming and forgetting the same pair for every quad you form, including all the extra quads you form (one for each octet) and so on - doing almost 50% more work than needed (forming pairs 3 times for each quad rather than 2 for each quad and 1 extra)
|
|
IP Logged |
|
|
|
jollytall
Senior Riddler
Gender:
Posts: 585
|
|
Re: 4 out of 7 numbers
« Reply #4 on: Apr 1st, 2014, 8:18am » |
Quote Modify
|
Using as an algorithm mine indeed might be more efficient, but I still like yours more as a mathematical proof. You used n to get to n+1, while I used 2 and n to get to n+1. Yours is a clean full induction, mine is more complex.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print