(In memory of Toxie 😀 )
Let’s suppose the following bet were proposed:
Is this bet worth making? Why?
An analysis will be given in the next post.
Follow up to Product & Sum.
As in the “three wise men” puzzle, it’s useful to begin by analyzing simplified variants of the problem. Lets start analyzing the variant where only one islander has blue eyes and the other 999 have brown eyes.
When the foreigner gives his message, as the blue-eyed islander can see that the other islanders are all brown-eyed, he now knows his own eye color and must commit suicide the following day at noon. But, when the blue-eyed islander kills himself, all the other islanders know that they are brown-eyed and they must commit suicide at noon the next day (we can assume that each islander knows that his eye color is either blue or brown).
Now we can examine the variant where two of the 1000 islanders are blue-eyed. In this case the foreigner’s message does not give any information immediately, as any inhabitant of the island knows by observation that there is at least one blue-eyed islander. But the absence of a suicide at noon the following day shows to each of the two blue-eyed islanders that the other one is not the only blue-eyed inhabitant of the island. Then, in the second noon after the message, the blue-eyed islanders commit suicide, followed by the rest of the tribe the next day.
This reasoning can be extended to the full case, where the 100 blue-eyed islanders will commit suicide at the 100th noon since the foreigner’s message and the 900 brown-eyed ones will do the same at the following noon (the 101st).
Followup to Product & Sum.
Contradicting what was said in the previous post, the blue eyed islanders puzzle will be solved in a future post to avoid making this post excessively long. 😀
One way to visualize the structure of this problem is to take each assertion by P and S as a filter to be applied over the initial set of integer pairs. This solution will then represent each of these filters as a block of Python code, with additional text explaining how each filter is connected with the associated assertion.
Given are X and Y, two integers, greater than 1, are not equal, and their sum is less than 100. S and P are two mathematicians; S is given the sum X+Y, and P is given the product X*Y of these numbers.
It is clear that we can restrict the first number to be strictly less than the second number, as the order of the numbers cannot be determined from the given data. Then we can get all the allowed pairs with the following Python code:
all_pairs = [(x, y)
for y in range(2, 100) for x in range(2, y)
if x + y < 100]
– P says “I cannot find these numbers.”
This implies that there are multiple allowed pairs whose products match the value that was given to P. We can start counting the number of pairs with each possible product:
num_pairs_by_prod = {}
for x, y in all_pairs:
if x * y not in num_pairs_by_prod:
num_pairs_by_prod[x * y] = 0
num_pairs_by_prod[x * y] += 1
The pairs allowed by P’s assertion are those whose product is shared with other pairs:
pairs_1 = [(x, y) for x, y in all_pairs if num_pairs_by_prod[x * y] > 1]
– S says “I was sure that you could not find them.”
Then we know that the value of the sum is enough to know that the product cannot identify the pair of integers. The set of sums of integer pairs that can be identified by their products is:
identif_by_prod_pairs_sums = set(x + y for x, y in all_pairs
if num_pairs_by_prod[x * y] == 1)
As the sum is enough to know that the integer pair cannot be identified by its product, the sum of the pair cannot be in the above set:
pairs_2 = [(x, y) for x, y in pairs_1
if x + y not in identif_by_prod_pairs_sums]
– P says “Then, I found these numbers.”
This indicates that in pairs_2, the list of pairs restricted by the first two assertions, the correct pair can be identified by its product. Then we can do essentially the same we did in the first step but now keeping the pairs identifiable by their products:
num_pairs_by_prod_2 = {}
for x, y in pairs_2:
if x * y not in num_pairs_by_prod_2:
num_pairs_by_prod_2[x * y] = 0
num_pairs_by_prod_2[x * y] += 1
pairs_3 = [(x, y) for x, y in pairs_2 if num_pairs_by_prod_2[x * y] == 1]
– S says “If you could find them, then I also found them.”
This implies that the pair can be identified by its sum from the list restricted by the first three assertions. We can get the final pairs list repeating the previous step, but now searching for a unique sum:
num_pairs_by_sum_3 = {}
for x, y in pairs_3:
if x + y not in num_pairs_by_sum_3:
num_pairs_by_sum_3[x + y] = 0
num_pairs_by_sum_3[x + y] += 1
pairs_4 = [(x, y) for x, y in pairs_3 if num_pairs_by_sum_3[x + y] == 1]
Putting the code together, adding a print statement to get the final list of pairs and running the code we get
[(4, 13)]
matching the results in the literature.
Spin Foam 