Mathematics desk
< April 12	<< Mar \| April \| May >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

April 13

Largest multiset that cannot be partitioned in two equal sum sets

Inspired by the above "addition game". Let M be a fixed integer. For which N, if any, is it guaranteed that a set of N integers (not necessarily distinct) all between 1 and M can be partitioned into two subsets with the same sum? What about the same sum modulo M? (Or, conversely, assume that you are given M and N, can you exhibit N integers such that no partition of the set in two subsets produces the same sum?)

Formally: given M, find (if possible) the smallest N such that

$\forall a_{1},a_{2},...a_{N}\in \{1,2,...M\},\exists b_{1},b_{2},...b_{N}\in \{-1,1\},\sum _{1}^{N}a_{i}b_{i}=0{\text{ (maybe }}mod\ M{\text{)}}$

I would assume that there is a maximum N in both cases, but cannot prove it in either. The second case (modulo M) looks like it ought to be solved with a smart pigeonhole principle but I did not find it. Tigraan^{Click here to contact me} 14:54, 13 April 2018 (UTC)[reply]

I'm probably missing something, but why can't you just take N integers whose sum is odd? You'd then be guaranteed not to be able to divide it into parts with equal sums. --RDBury (talk) 00:16, 14 April 2018 (UTC)[reply]

Huh... yeah, of course. (For the "modulo M" case, it might not work if M is odd, but a similar idea applies: take numbers all but one equal to 0 mod M.) Sounds trivial in retrospect. Tigraan^{Click here to contact me} 20:30, 15 April 2018 (UTC)[reply]

Resolved