Le Monde puzzle [#1157]
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 odd is a sure win for Kimmernaq. 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: calling 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 Aputsiaq 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 Kimmernaq 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!
October 1, 2020 at 10:26 am
Author states: “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.” This seems to me to be a non sequitur, a fallacy of the form ((A -> B) and B) therefore A. If the sum of the ten numbers is even, it can be split into two equal parts, but it does not follow that it can be so split using the numbers given. To be sure, I do not say that the sum being even is NOT a sufficient condtion for the requested partition being possible, but I do not think the author has shown this.
I would be interested in a proof.
October 1, 2020 at 11:51 am
Sorry, indeed I meant the exact opposite: When the sum is odd, the game is a sure win for Kimmernaq!!!
October 1, 2020 at 12:17 pm
Ah, I see. Nice. Thank you.
October 1, 2020 at 2:44 pm
Now that I understand the general reasoning I would like to understand and try out your code, but there are two problems when I try to run it:
1) It looks as if “{” is missing after the second while
2) the line “o=sample(a,10-t)” returns error “object a not found”
Did something go wrong when copying your code?
Kind regards
October 1, 2020 at 7:04 pm
The R code is running on my machine. Is it a matter of fonts or colour? Here is a rendering on tio.run
October 1, 2020 at 7:26 pm
Thanks, but the two codes differ. In your article you use two while loops (with only one opening { and two closing }}.
In the tio.run you use three while loops with two {{ and two }} and one one-line while without {}.
October 1, 2020 at 10:18 pm
You lost me: I cut & pasted the blog code into the tio.run… Cheers!
October 1, 2020 at 10:57 pm
This is the code in the article:
P=1;M=1e3
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}}
This is the code in your tio.run
P=1;M=1e2
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}}
max(2*cumsum(b)==s)
October 1, 2020 at 11:00 pm
The code that I am speaking of is the code in the R-Bloggers mailing list article. I see that your blog-code is indeed the same as that in tio.run
October 2, 2020 at 7:09 pm
It may be that R-Bloggers is not making a perfect copy of the original. Thank you!
October 1, 2020 at 8:11 am
[…] article was first published on R – Xi'an's Og, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here) […]
October 1, 2020 at 6:06 am
[…] article was first published on R – Xi’an’s Og, and kindly contributed to R-bloggers]. (You can report issue about the content on this page […]
October 1, 2020 at 5:24 am
[…] article was first published on R – Xi’an’s Og, and kindly contributed to R-bloggers]. (You can report issue about the content on this page […]
October 1, 2020 at 2:56 am
[…] by data_admin [This article was first published on R – Xi’an’s Og, and kindly contributed to R-bloggers]. (You can report issue about the content on this page […]