Le Monde puzzle [#1157]

This article is originally published at https://xianblog.wordpress.com

The weekly puzzle from Le Monde is an empty (?) challenge:

Kimmernaq and Aputsiaq play a game where Kimmernaq picks ten different integers between 1 and 100, and Aputsiaq must find a partition of these integers into two groups with identical sums. Who is winning?

Indeed, if the sums are equal, then the sum of their sums is even, meaning the sum of the ten integers is even. Any choice of these integers such that the sum is even is a sure win for Aputsiaq. End of the lame game (if I understood its wording correctly!). If some integers can be left out of the groups, then both solutions seem possible: usng the R code

P=1;M=1e3
while (P<M){
a=sample(1:M,10);P=Q=0
while((P<M)&(!Q)){
t=sample(1:7,1)     #size of subset
o=1         #total sum must be even:
while(!!(s<-sum(o))%%2)o=sample(a,10-t)
Q=max(2*cumsum(b<-sample(o))==s)
P=P+1}}

I found no solution (i.e. exiting the outer while loop) for M not too large…  So Kimmernaq is apparently winning. Le Monde solution considers the 2¹⁰-1=1023 possible sums made out of 10 integers, which cannot exceed 955, hence some of these sums must be equal (and the same applies when removing the common terms from both sums!). When considering the second half of the question

What if Kimmernaq picks 6 distinct integers between 1 and 40, and Aputsiaq must find a partition of these integers into two groups with identical sums. Who is winning?

recycling the above R code produced subsets systematically hitting the upper bound M, for much larger values. So Aputsiaq should have a mean to pick 6 integers such that any subgroup cannot be broken into two parts with identical sums. One of the outcomes being

 
> a
[1] 36 38 30 18  1 22

one can check that all the possible sums differ:

aa=a
for(i in 2:5){
 bb=NULL
 while(length(bb)<choose(6,i))bb=unique(c(bb,sum(sample(a,i))))
 aa=c(aa,bb)}
unique(aa)

and the outcome is indeed of length 2⁶-2=62!

As an aside, a strange [to me at least] R “mistake” was that when recycling the variable F in a code-golfing spirit, since it is equal to zero by default, rather than defining a new Q:

while((P<M)&(!F)){
...
F=max(2*cumsum(b<-sample(o))==s)
P=P+1}

the counter P was not getting updated!

Thanks for visiting r-craft.org
This article is originally published at https://xianblog.wordpress.com
Please visit source website for post related comments.