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[edit]

Largest multiset that cannot be partitioned in two equal sum sets[edit]

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