wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Some subset has sum 60
        
(Message started by: ecoist on Dec 7^th, 2008, 10:52am)

Title: Some subset has sum 60
Post by ecoist on Dec 7^th, 2008, 10:52am

You have 32 integers between 1 and 60 inclusive, whose total is 120. Show that some subset of these integers has sum 60.

Title: Re: Some subset has sum 60
Post by aicoped on Dec 9^th, 2008, 11:59pm

This is just using the pigeonhole method.

Basically, no matter which number you start with, you know you can't use it's "opposite half" so if the if you start with 1, then you can never use 59, etc, since there are only 29 complete halfs that total to 60, once you have used any of the 29 numbers you have excluded their other half. the only numbers left would be 30 which wouldn't have a half to match with and 60. So any number you picked after that would automatically mena that there is a 60 sum somewhere in your subsets.

Now, I notice you did not say distinct integers and if they could theoretically all be the same or more than one could be the same, as long as their total was 120, then I would have to think more on the problem.

Title: Re: Some subset has sum 60
Post by Grimbal on Dec 10^th, 2008, 5:31am

It looks like the numbers can be repeated. If not, they couldn't sum to 120.

Title: Re: Some subset has sum 60
Post by ecoist on Dec 10^th, 2008, 9:31am

Some pairs of integers amongst the 32 must be equal. Since any 15 pairwise distinct positive integers sum to at least C(16,2)=120, there can be at most 14 pairwise distinct integers among 32 positive integers which sum to 120.

Title: Re: Some subset has sum 60
Post by aicoped on Dec 10^th, 2008, 4:44pm

Yes my bad, i realize now that 120 could not be reached with the other method. I was thinking that was one of those useless things they throw into problems to throw you off the right track.

Title: Re: Some subset has sum 60
Post by Hippo on Dec 12^th, 2008, 12:20pm

Surprisingly noone gives solution yet so I'll give my rather long proof.
[hide]
We have 15m+2 numbers not exceeding 30m summing to 60m and want to proove there exists a subset summing to 30m (where m = 1 or 2).

Let number i appears in the list n_i times. Encode list by (n₁,...,n_30m).

Suppose a counterexample exist. Than there exist the counterexample with lexicographically maximal encodding E=(n₁,...,n_30m).
1) n_1+j is zero whenever jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifn₁ and there are 2 other numbers k,l greater or equal j+1 summing less than 30m.

Proof: Cutting 1 from j+1 and gluing k+l sum and count unchanged, and each newly obtainable sum was obtainable before therefore (n₁+1,...,n_j+1,n_1+j-1,...,n_k-1,...,n_l-1,...,n_k+l+1) is counterexample with bigger encodding.
(The only interesting cases are when the sum uses all n_j j's and no 1 or it uses all n₁ 1's and no j, otherwise the split does not change the situation. As jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifn₁, we can replace one j by j original 1's to obtain the same sum in the former case or j 1's by one j to obtain the same sum in the later case, so in both cases the split does not change the situation. On the other side joining k,l together may prevent some sums)

2) There exists ihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif3 and jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif4 such that n_ihttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/gt.gif0http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lt.gifn_j.

Proof:For average hold 3 < 60m/(15m+2) = 4-8/(15m+2) < 4.

3) n₁http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif1.

Proof: Suppose k=n₁>1. Let l be minimal number greater than 1 in the set. If khttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif15m-1, we can sum remaining numbers until any further summing leads to number greater than 30m. In that case at least one sum is at least 15m+1 so combined with ones gives sum 30m.
So khttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lt.gif15m-1, there are at least 4 remaining numbers, if 2nd and third in size cannot be summed to get number less (or equal to) 30m, then sum of three bigest numbers must be at least 45m+2 so k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif15m-4. If k http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif15m-4, there are at least 6 remaining numbers and 2 of five highest can be summed together to get less than 30m. So for khttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lt.gif15m-1 according 1) lhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gifk+2. We get 60m http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gifk+(15m+2-k)lhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gifk+(15m+2-k)(k+2) = -k²+(15m+1)k+(30m+4). k²-(15m+1)k+(30m-4) http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif0 gives |k-(15m+1)/2|http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/gt.gif1/2http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gif((15m)²-3)http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/gt.gif(15m-1)/2 so khttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/gt.gif15m or khttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif1. First case lead to contradiction so khttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif1.
[/hide]

to be continued ...

Title: Re: Some subset has sum 60
Post by Hippo on Dec 12^th, 2008, 12:27pm

[hide]
4) n₂http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/gt.gif0

Proof: Suppose the contradiction, so the sum 60m is obtained by at most one 1, n₃ 3's and numbers above average.
Lexmin such configuration containing 1 is (1,0,5,15m-4,0,...) (without 1 the arguments would be simplified as we don't use it).
Maintaining the same sum we can simultaneously increment some number different from 3 and decrement one of 4's (both by 1). By such process we can get all remaining cases. If n_jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif3i for jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/gt.gif3, n₃http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif10m-1-ji, otherwise j's and 3's can be summed to 30m. So n₃http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif10m-1-4http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lfloor.gifn₄/3http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rfloor.gifand as n₄http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif15m-4-2(n₃-5)=15m+6-2n₃ we obtain n₃http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif10m-1-20m-8+4http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.gif2n₃/3http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif=-10m-9+4http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.gif2/3n₃http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif. So 10m+9http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif4http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lceil.gif2n₃/3http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/rceil.gif-n₃http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif4(2n₃+2)/3-n₃=5n₃/3+8/3 therefore n₃http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif6m+19/5 and finaly n₃http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif6m+4.
Assumption that for some jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif4 n_jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/gt.gif2 leads to 10m-1-jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gifn₃http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif6m+4, but as mhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif2 we get 10m-1-j-6m-4http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif4m-9http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/lt.gif0 so there is no such n₃ and we get contradiction.
Therefore n_jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gif2 whenever jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/gt.gif3. So at most two increment chains finish on 5, at most 2 on 6, ... the first such encoddings are (1,0,11,1,2,2,0,..) for m=1 and (1,0,31,2,2,2,2,1,2,0,..) for m=2. In both cases 3's can sum upto 30m.

5) Suppose m=2, m'=m/2=1 ... divide the problem by 2 :). By 1) we know n₁=0. Take any pair of numbers of the same parity. As the sum of remaining 15m numbers is at least 30m, the sum of paired numbers does not exceed 30m. Make 15m' pairs and leave one of number's 2 and one other even number extra. After numbers are paired replace them by their sums. We got at least 2+15m' even numbers including number 2 among them summing to 60m. Divide each number by 2. We had 2+15m' numbers from 1,...,30m' with sum 60m' including number 1 among them asking to find subset with sum 30m'. Dividing encodding by 2 we get again lexmax encodding (n'₁,...,n'_30m').
Accordind 1), 2), 3) and 4) applied to m' we get a contradiction as we get both n'₂http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/gt.gif0 and n'₁http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/ge.gif1.
[/hide]