Archive for affaire de logique

Le Monde puzzle [#1071]

Posted in Books, Kids with tags , , , , , , , , , , , on October 18, 2018 by xi'an

A “he said she said” Le Monde mathematical puzzle sixth competition problem that reminded me of the “Singapore birthday problem” (nothing to do with the original birthday problem!):

Arwen and Brandwein are privately and respectively given the day and month of Caradoc’s birthday [in the Gregorian calendar] with the information that the month number is at least the day number. Arwen starts by stating she knows Brandwein cannot deduce the birthday, followed by Brandwein who says the same about Arwen. If this “she says he says” goes on for the largest possible number of steps before Arwen says she knows, when is Caradoc’s birthday? Arwen and Brandwein are later given two numbers corresponding to Deirdre’s birthday with no indication of which one is the day and which one is the month. They know both numbers end up with the same digit and that the month number is strictly less than the day number. Arwen states she does not know the date and she knows Brandwein cannot know either. Then Brandwein says he indeed does not the date but he knows whether he got the day or the month. This prompts Arwen to conclude she knows, then Brandwein to do the same. When is Deirdre’s birthday?

Since this was a fairly easy puzzle (and since I had spent too much time debugging the previous R code!), I did not try coding this one but instead drew the possibilities and remove the impossibilities on a blackboard. The first question is quite simple actually since the day numbers stand between 1 and 12 and that each “I cannot know” excludes one of the remaining endpoints, removing first excludes 1 from both lists, then 12, then 2, then …. 8, ending up with 7. And 07/07 as Caradoc’s birthday. The second case sees 13,…,20,23,…,30 eliminated from Arwen’s numbers, then 3,…,10 as well, which eliminates the same numbers from Brandwein’s possibilities. That he knows whether it is a month or a day leaves only 1,2,21,22,31 as possible numbers. Then Arwen’s certainty reduces her numbers to be 2, 21, 22, or 31, and since Brandwein is also sure, the only possible cases are (2,22) and (22,2). Meaning Deirdre’s birthday is on 22/02. I dunno if this symmetry was to be expected! (And I cannot fathom why this puzzle is awarded so many points, when compared with the others.)

Le Monde puzzle [#1015]

Posted in Books, Kids with tags , , , on July 10, 2017 by xi'an

A combinatoric Le Monde mathematical puzzle:

A game with N questions and N players is such that each question is solved by all players but three, while any pair of players fails to jointly solve the N questions. What is the maximal number N of players?

N=6;play=1;besz=1
while ((besz>0)||(play<N)){
gamz=matrix(1,N,N)
for (qez in 1:N) gamz[qez,sample(1:N,3)]=0
besz=0;play=1
while ((play<N)&(besz==0)){
besz=max(apply(as.matrix(gamz[,play]+
  gamz[,(play+1):N],ncol=N-play),2,prod))
play=play+1}
}

The output of that code is N=7 in that N=8 does not escape the while loop. (Since there are 3N zeros to distribute in the NxN matrix, either all columns contain 3 zeros or one contains only two, in which case it can only share zeros with 2×2=4 other columns, which makes it impossible. When a column holds three zeros, it can share zeros with 3×2=6 other columns, which brings us back to N=7 as the highest possible case.)

A second game with M>N players and questions sees each question solved by all but four players. There is at least a pair of players jointly solving all questions. What is the minimal number M of players?

Given the simple update to the above R code

for (qez in 1:N) gamz[qez,sample(1:N,5)]=0

running the R code leads to suggest N=11, as the first instance when the loop does not exit. (The above logical argument does not run so well since having four zeros per column should allow for at most 4×3=12 other columns sharing zeros with that column, which leads to 14 as an upper bound for the answer, not 11!) However, the published solution is 14, which shows the limitation of this R code…