by Richard Taylor : 2023-05-15
I like puzzles. Mostly they are just a bit of fun ending in mild satisfaction or slight frustration. As a software engineer my solution to the latter is to write a bit of code to brute force a solution: so usually it's win-win.
Sometimes though there's a puzzle that niggles in a different way. I get the "right" answer but have a nagging doubt that there's more to it somehow. Such was so with last week's New Scientist puzzle #220. This article is about the puzzle and the roles of curiosity and intuition in software engineering.
The puzzles in New Scientist are often a bit wordy so the first challenge is always to decode the language. This one combines the current hot topics of "AI" and "Eurovision" to frame a numerical problem.
The way I read the problem was: there are a number of countries (N) who all vote for each other; they each give one country a score of 10 and all the other countries the same score (less than 10). But "the jury" reset all the 10 scores to zero. If the total of all the final scores is 222, and no two countries get the same score, how many countries took part and what was the winning score?
By way of example we are also told that one country gave a 10 to Ruritania and 7s to everyone else. So we know that one set of "surviving" scores was 7.
There is a little bit of ambiguity here. I assume that all the scores are whole numbers, that's pretty uncontroversial, and that countries can't vote for themselves. But what is the minimum score? The puzzle just says "less than 10" so does that go down to 1 or 0? At first I went with 1.
I did get the same result as the published solution but, as I said, something felt a bit off with it (notwithstanding the 0 or 1 question).
To get the number of countries (N) you notice that 222 = 2 x 3 x 37 and that 37 is prime so that is the full factorisation. Since each of the countries gives out (N-2) times their chosen vote then also 222 = (N-2) x (sum of chosen votes)
So (N-2) is either 2, 3, 37 or the product of 2 of them, 6, 74 or 111. Then as the scores are all less than 10 you can deduce that it has to be 6 so N=8.
So far so good. There were 8 countries taking part.
How do we work out the winning score? The only other information we have is that there were no ties and one of the votes was a 7. Oh, and from the calculation of N we know that the sum of the chosen votes (one of each from each country) is 37.
All I could think of was that if there are no ties then maybe that means all the scores had to be unique. That might be true if it weren't for the 10 becoming 0. But was it true here?
If you assume all the votes are unique, then notice that 1+2+3+4+5+6+7+8 = 36, which is one short of 37, so bump the 8 to a 9 (bumping any of the others gives 2 the same). Thus we get votes of (1,2,3,4,5,6,7,9) with each country not voting for itself; and possibly getting some 10s which are relegated to 0s, so each gets at most 7 of those 8 scores; which makes the winner the one with 2+3+4+5+6+7+9 = 36. Bingo!
Even though I got the same solution as the published one (8 countries, winning score 36) it didn't feel quite right. When I looked at the published solution I kind of hoped there would be some cunning trick there that I'd missed, but there wasn't.
My nagging doubt was that changing those 10s to 0s makes a difference and gives the sums enough wiggle room to not need all the votes to be unique.
Of course I could have just left it there. I got the "right" answer. I could have gone on to the next puzzle. But I didn't. Was my intuition right? I had to know. So I wrote a Python script to solve this anyway.
When it comes to brute forcing there are a couple of tactics. If you think there is only one solution among many possibilities then you need to iterate over all the possibilities to find it; but if you think there are many solutions you can just sample randomly and you'll find one in a reasonable time.
In this case I thought there might be several solutions so I went for random sampling:
for country in range(8):
vote = random.randint(1, 9)
if vote == 7:
seven = True
ten = country
while ten == country:
ten = random.randint(0, 7)
votes = [vote] * 8
votes[ten] = 0
votes[country] = 0
totals = list(map(add, totals, votes))
scores.append(votes)
Each country picks a random vote between 1 and 9 and picks a random country to give its 10 to. The ten gets reduced to a zero and the country gives itself 0 too.
The script then tests whether the votes add up to 222 and there are no ties. It keeps going until it finds a combination that fits the constraints. I know it's ugly but this is "throw away" code. I can check the results manually at the end to be sure there were no bugs.
Sometimes when this happens it turns out that the published solution was correct after all and they just didn't have space to explain all the details. Which is fine; when my curiosity is satisfied I'm happy. This time I was right about the uniqueness of votes being unnecessary. Here is a combination of votes where two countries chose 2 and two chose 9 but none chose 5, 6 or 8. The total is 222, there is a 7, and there are no ties. ("X" is the 10 which is counted as 0).
A B C D E F G H
A 0 2 2 2 2 2 X 2
B 3 0 3 X 3 3 3 3
C 4 4 0 4 4 4 4 X
D X 2 2 0 2 2 2 2
E 1 1 1 1 0 X 1 1
F 7 7 X 7 7 0 7 7
G 9 9 X 9 9 9 0 9
H 9 9 9 9 9 X 9 0
= 33 34 17 32 36 20 26 24
^^
The winning score is still 36, so at this point it looks like I am just nitpicking about the method... but look at this other example:
A B C D E F G H
A 0 3 3 3 3 X 3 3
B 6 0 6 6 6 X 6 6
C 8 8 0 8 8 8 X 8
D 7 7 7 0 X 7 7 7
E X 3 3 3 0 3 3 3
F 3 3 3 3 3 0 X 3
G 2 2 2 2 2 X 0 2
H X 5 5 5 5 5 5 0
= 26 31 29 30 27 23 24 32
^^
This also satisfies the constraints but the winning score is 32. This was actually the lowest winning score I found, with other results between 32 and 36 also possible. And it turns out that even if you force the votes to be unique then it is still possible to win with a score as low as 32.
So the answer to the question "Can you figure out how many countries took part and how many points the winning song scored?" is "The number of countries is 8 and the winning score is between 32 and 36 inclusive".
When I wrote my script I intended the votes to be between 1 and 9, but I made a mistake and put 0 as the lower bound. This happened to make only a small difference, which was that a country which gives everyone zero can win with a score of 37 if no other country does the same. The lowest winning score still seems to be 32 though.
This puzzle is an example of where I learned something by being curious about a solution that seemed not quite right. Maybe it will come in useful one day; maybe not. But I definitely got to practise investigating.
Curiosity is a good thing. Particularly in technology. Just because someone or some document says something is so, it doesn't mean it necessarily is. People make mistakes all the time. Technology is complicated. It's easy to mix things up or write down the wrong result.
If you are curious about things and investigate them you will get a better understanding of that particular thing and will, over time, build up an intuition about what feels right and what might be wrong. You should not rely on that being 100% correct and act on it unquestioningly, but it helps to be alerted to possible anomalies so you can discover things that are both interesting and potentially valuable.