There's an italian weekly magazine (La settimana enigmistica) that once in a while publishes “A puzzle with Susi”. Susi is a cute and smart girl who accepts to solve challenges her friend Gianni is used to throw to her.
In one of my italian blog I've tackled two (so far) of these puzzles using Prolog and Haskell.
Gianni's friend at the cinema
Susi meets Gianni with four of his friends at the cinema. They sit in a particular sequential order, one after another, from left to right. Susi asks Gianni to be introduced to his friends. And Gianni puts it as a puzzle: «Currently I say you only this: Luca sits near Aldo, but not near Berto». Then Gianni's friends swap seats and Gianni states that now Berto is near Aldo. Gianni specifies that the fourth friend is Franco, then ask Susi: «Can you tell me the number on the ticket of Luca?»
The number on the ticket is just a way to label each friend; using these labels, in the last frame we see Gianni's friends sat in this order: 1, 2, 3, 4. In the first frame the order was 4, Gianni, 2, 1, 3. In the second frame the order was 1, 2, 3, Gianni, 4 (we can assign the labels using peculiar visual clue, mainly the colors of the hairs and hairstyles—if the link is not broken yet, you can try to look at the scan of the page).
The seat occupied by Gianni is important, since he “breaks” the row isolating the same friend (label 4) once on the left end, then on the right end. With this little tip we can solve the puzzle…
But let's code it in Prolog instead.
vicino means “near” (A and B are near if their absolute “distance” is 1), and
chi means “who”. The label 0 is used to mark Gianni's seat. The code needs some extra constraints: neither Luca, Aldo or Berto are Gianni (label 0), and each of them is distinct from the others.
Visiting the Prolog code gives the solution.
Susi and the ten cards deck
Gianni invites Susi to solve another puzzle.
«Susi» says Gianni, «the cards on the table have values from 1 to 10. Now I turn them upside down». Then he gives Susi three cards, takes four for him and leaves three cards on the table. He continues: «The sum of the values of your three cards is a fifth of the sum of my four cards. Which is the sum of the three cards on the table?»
This is a strange puzzle, since it's very, very easy for Susi: she knows the cards in her hands, hence he reaches the solution immediatly: it's enough she computes a multiplication and a difference:
\[ x = 55 - 6S_s \]
In fact, she knows exactly Ss (the sum of her cards). The equation comes from the fact that we know the sum of the values from 1 to 10 (it's 55) and we can write:
\[ S_g + S_s + S_t = 55 \]
I.e., the sum of all the numbers from 1 to 10 is equal to the sum of the cards of Gianni, added to the sum of the cards of Susi, aded to the sum of the cards left on the table. But we also know that
\[ S_g = 5S_s \]
I.e. the sum of the cards of Gianni is five times the sum of the cards of Susi. This leads to our first equation, where I've used x instead of St, just to stress it's our unknown number we are interested in.
Susi knows the result, but the reader must go through some extra reasoning. I did it in the italian blog, I won't translate it here. Instead, let us take a look at the Haskell code we can use to solve the puzzle.
This is straightforward (and inefficient) as well. We have a list of all number from 1 to 10 and we consider all the possibile permutations. Then, we use the following convention: the first three numbers of the list are the Susi's cards, the next four numbers are the Gianni's cards, and the last three numbers are the cards left on the table.
checkSol checks if a permutation satisfies the constraints, given their “partitions” as said above. The constraints are trivial: the sum of all the cards is equal to the sum of the sum of the cards in each “partitions” (in the code, this sum of the cards in a partition is called after the owner:
tavolo means “table”); and, five times
susi must be equal to
checkSol to filter the list of all permutations, so that we obtain a list containing only the right permutations (namely those satisfying the constraints); we expect there can be several right permutations given the same sum of the three cards on the table; we pick the first and compute the sum of the “cards” once removed those in the hands of Susi and Gianni. It's the solution we wanted.
That's all, but the demanding reader could have noticed something obscure: how do we know that the wanted sum is unique? Are there right permutations that give a different sum and still fulfil the constraints?
No analytical proof given; but we can check it looking at all the sums of the filtered permutations. (The nature of the game requires an unique solution… this is not a proof, of course… but it turns to be a valuable observation…)
Project Euler offers several interesting problems you can tackle using a programming language, and also math and logic. Have fun!