|
|
|
|
|
|
|
|
CTK Exchange
Bernard Murphy
guest
|
Apr-20-11, 10:38 AM (EST) |
|
"Pigeonhole Principle Qn 43 - an error?"
|
'Prove that no seven distinct positive integers, not exceeding 24, can have sums of all subsets different.' I think the solution given is of a weaker, rather than stronger, result. Here, I hope, is a proof of the proposition as stated. Assume the numbers chosen are a<b<c<d<e<f<g The maximum sum of 6 chosen numbers is 24+23+22+21+20+b=110+b and so the maximum sum which could be repeated is 109+b. The smallest possible sum which could be repeated is 1+b since this could be equal to c. Therefore there are at most 109 different totals but the number of subsets under consideration is 2^7-6=122 since each of {}, {a}, {b}, {b,c,d,e,f,g}, {a,c,d,e,f,g} and {a,b,c,d,e,f,g}cannot have the same sum as another set. So there are 122 pigeons and only 109 pigeonholes. |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
alexb
Charter Member
2794 posts |
Apr-21-11, 10:49 AM (EST) |
|
1. "RE: Pigeonhole Principle Qn 43 - an error?"
In response to message #0
|
>I think the solution given is of a weaker, rather than >stronger, result. Here, I hope, is a proof of the >proposition as stated. Why? The problem asks to show there are repetitions. The proof shows that there repetitions even if the consideration is restricted to 4-element sets. > >Assume the numbers chosen are a<b<c<d<e<f<g > >The maximum sum of 6 chosen numbers is >24+23+22+21+20+b=110+b and so the maximum sum which could be >repeated is 109+b. >and 21 in our set but there is some slack so we can afford >to be a bit wasteful and overlook that.] > >The smallest possible sum which could be repeated is 1+b >since this could be equal to c. > >Therefore there are at most 109 different totals but the >number of subsets under consideration is 2^7-6=122 since >each of {}, {a}, {b}, {b,c,d,e,f,g}, {a,c,d,e,f,g} and >{a,b,c,d,e,f,g}cannot have the same sum as another set. > >So there are 122 pigeons and only 109 pigeonholes.
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Copyright © 1996-2018 Alexander Bogomolny
|
|