Saturday, November 29, 2014

Galactic Expedition

When the scientific community predicted that the Sun would explode into a supernova in ten years time, destroying the entire Solar System, the Earthlings duly prepared for the Doomsday event. The first intergalactic spaceship was already being built, even before that prediction of doom. A sample of the human population was going to travel to the Andromeda Galaxy, where a planet in the BSC14823 solar system was believed to be able to sustain human life. It was hoped that on this planet, the human race would survive and re-establish itself as the superior being in the universe.

The person that would navigate the ship would have to rely on his/her own mathematical abilities, since obviously there could be no assistance from Earth after the explosion. The journey was predicted to last for at least 30 years, so the selection of this person was extremely tough. Only the very finest mathematical and logical mind would be able to successfully navigate the spaceship through intergalactic travel. A test to find this person was issued, and the best mathematicians of the planet competed.

spaceship puzzle

Competition was feirce, for this person would become the first hero of the new world. Of all canditates, only a young woman and a young man reached the very final stage of the selection process. The chairman of the Special Selection Board explained the final question, "There are three different integers, A, B, C, where A × B × C = 900, and A > B > C. One of you will receive either A + B or A + C, but you will not know which one of the two sums it will be. The other candidate will be given the number B. You will take turns, and the winning candidate will be the one that can tell us what the 3 numbers are."

The young man, named Wadzru, was asked to start first. "I don't know," was his answer. Then it was the young woman's turn. Her name was Zaxre, and her answer was also "I don't know." Wadzru's second turn was another "Don't know," which is the same answer given by Zaxre on her second turn. They went on answering "I don't know" for a certain number of times, until Wadzru suddenly grabbed the pen and started writing down the answer. As soon as he started writing, Zaxre cried a "YES!" and also started writing down the answer.

The selection board was confused. Wadzru did indeed answer first, but only because he was one turn ahead. Zaxre also answered correctly when it was her turn. At that moment a young mathematician entered the room. The chairman of the board called him over, and explained the mathematical problem to him. After a short pause, the man said, "If I understand the problem correctly, sir, then the two candidates must have given the correct answer on their fourth turn, that is when each of them were answering for their fourth time. At this point, I can also tell you what the three numbers are. However, there are two different answers, depending on who was given the first chance to answer: whether it was the candidate who was given number B, or the candidate who was given the sum A + B or A + C."

The board were so impressed by this latecomer that he was nominated as the commander of the expedition.

What are the two different combinations of the three numbers?

Galactic Expedition Puzzle Solution

The table below shows all possible combinations (32 of them) of three different integers, the product of which is 900. Next to each combination there is the result of the sum A+B, then the result of the sum A+C, and finally the the number B for that particular combination:
Combination # Factors A+B A+C B
1 450 * 2 * 1 452 451 2
2 300 * 3 * 1 303 301 3
3 225 * 4 * 1 229 226 4
4 180 * 5 * 1 185 181 5
5 150 * 6 * 1 156 151 6
6 100 * 9 * 1 109 101 9
7 90 * 10 * 1 100 91 10
8 75 * 12 * 1 87 76 12
9 60 * 15 * 1 75 61 15
10 50 * 18 * 1 68 51 18
11 45 * 20 * 1 65 46 20
12 36 * 25 * 1 61 37 25
13 150 * 3 * 2 153 152 3
14 90 * 5 * 2 95 92 5
15 75 * 6 * 2 81 77 6
16 50 * 9 * 2 59 52 9
17 45 * 10 * 2 55 47 10
18 30 * 15 * 2 45 32 15
19 25 * 18 * 2 43 27 18
20 75 * 4 * 3 79 78 4
21 60 * 5 * 3 65 63 5
22 50 * 6 * 3 56 53 6
23 30 * 10 * 3 40 33 10
24 25 * 12 * 3 37 28 12
25 20 * 15 * 3 35 23 15
26 45 * 5 * 4 50 49 5
27 25 * 9 * 4 34 29 9
28 30 * 6 * 5 36 35 6
29 20 * 9 * 5 29 25 9
30 18 * 10 * 5 28 23 10
31 15 * 12 * 5 27 20 12
32 15 * 10 * 6 25 21 10

If the first question was asked to the person (Wadzru) that was given A+B or A+C and he answers "don't know", that means that the number he received appears in the A+B and A+C columns more than once. On the other hand, if that number appears in those columns only once, then the solution would be found immediately, as that number would relate to only one of the 32 combinations.

Therefore the first candidate was given one of the following numbers: 65, 61, 37, 65, 29, 28, 27, 25, 23. These numbers appear more than once in columns A+B and A+C, and because of this, they do not yet allow to find the correct combination. But we can now discard, from the 32 combinations, the ones where the 9 numbers listed above are not included in columns A+B and A+C. The combinations left were then:
Combination # Factors A+B A+C B
9 60 * 15 * 1 75 61 15
11 45 * 20 * 1 65 46 20
12 36 * 25 * 1 61 37 25
19 25 * 18 * 2 43 27 18
21 60 * 5 * 3 65 63 5
24 25 * 12 * 3 37 28 12
25 20 * 15 * 3 35 23 15
27 25 * 9 * 4 34 29 9
28 30 * 6 * 5 36 35 6
29 20 * 9 * 5 29 25 9
30 18 * 10 * 5 28 23 10
31 15 * 12 * 5 27 20 12
32 15 * 10 * 6 25 21 10

The second candidate (Zaxre) followed the same reasoning, so she then knew that these were the only possible combinations left, after Wadzru gave his answer. The situation for Zaxre was the same though: if the number she was given appeared only once in column B, then the right combination would be the one containing that number; if the number appeared more than once in column B, then the solution would not yet be within reach. And this is what happened, since she answered "don't know". But the elimination of certain combinations could go on nevertheless, because after she said "don't know", combinations # 11, 12, 19, 21, 28 were automatically discarded. Then it was Wadzru's second turn, and the current situation was:
Combination # Factors A+B A+C B
9 60 * 15 * 1 75 61 15
24 25 * 12 * 3 37 28 12
25 20 * 15 * 3 35 23 15
27 25 * 9 * 4 34 29 9
29 20 * 9 * 5 29 25 9
30 18 * 10 * 5 28 23 10
31 15 * 12 * 5 27 20 12
32 15 * 10 * 6 25 21 10

At this point, the first contestant answered again "don't know", and automatically discarded combinations 9 and 31. Then the second candidate, after following, again, the logical reasoning of Wadzru, answered "don't know", therefore discarding combinations 24 and 25.The third turn started with the first contestant facing the following combinations:
Combination # Factors A+B A+C B
27 25 * 9 * 4 34 29 9
29 20 * 9 * 5 29 25 9
30 18 * 10 * 5 28 23 10
32 15 * 10 * 6 25 21 10

Wadzru, by answering "don't know" on his third turn, discarded the only combination with no alternatives, ie 30, so Zaxre was presented only with combinations 27, 29, 32; her answer "don't know" left only two combinations: 27 and 29. Then it was the first contestant again, and he was faced with the following situation:
Combination # Factors A+B A+C B
27 25 * 9 * 4 34 29 9
29 20 * 9 * 5 29 25 9

If the first contestant now answered "don't know", then the number he was given must have had to be 29; but since he was given number 25, he was able to know the correct combination requested: 20*9*5. When Zaxre saw that Wadzru had the answer, she was also able to find the solution, because she had also been able to follow the selection process. For her, it was only possible to give the answer on her 4th turn, because if Wadzru could have been able to come up with the answer on his 3rd turn (when the numbers appering just once in columns A+B and A+C were more than one), then Zaxre would not have been able to know which of the combinations contained the number given to her opponent.

If instead, the question was first asked to Zaxre, who was given number B, then after her first "don't know" it would have been possible to discard from the table (the one with all 32 combinations) combinations 1, 11, 12. After her opponent also said "don't know", the combinations to be discarded would have been 2, 3, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15, 16, 17, 18, 20, 21, 22, 23 and 26, leaving the table looking like this:
Combination # Factors A+B A+C B
19 25 * 18 * 2 43 27 18
24 25 * 12 * 3 37 28 12
25 20 * 15 * 3 35 23 15
27 25 * 9 * 4 34 29 9
28 30 * 6 * 5 36 35 6
29 20 * 9 * 5 29 25 9
30 18 * 10 * 5 28 23 10
31 15 * 12 * 5 27 20 12
32 15 * 10 * 6 25 21 10

For the second turn, the "don't know" answer of the contestant answering first (Zaxre in this scenario) would have automatically discarded combinations 19, 25 and 28, and the "don't know" from her opponent would have further discarded another one: 31. For the third turn, the remaining possible combinations are: 24, 27, 29, 30 and 32. If Zaxre could not answer yet, then combination 24 would be discarded, while Wadzru's "don't know" would discard combination 30. The situation would now be:
Combination # Factors A+B A+C B
27 25 * 9 * 4 34 29 9
29 20 * 9 * 5 29 25 9
32 15 * 10 * 6 25 21 10

If Zaxre would now be able to know the solution, she would have been given, as B, number 10 (combination # 32), resulting with the product 15*10*6. But her opponent would also be able to answer then, thanks to Zaxre being able to find the solution. This scenario, like the previous one with Wadzru starting, where both opponents are able to find the solution at the same time, can only happen on the fourth turn. It's worth knowing that a fourth "don't know" from the candidates would have led to the problem being left unsolved.