Credited with solving this puzzle:
Alice and Bob are playing the following game: they start from a number N and each one of them in his or her turn (Alice starts) divides N by any divisor that is either a prime or a product of several distinct prime numbers. The winner is the one who gets to one – thus leaving the other player with no legal move.
To define the initial N, Alice chooses a number a from a set A, and a number b from a set B. The game is played with N=a+b. Charlie knows that Alice will start, and he wants to let Bob win. He does that by fixing the sets A and B.He can do that, for example, by choosing A=[3,99] and B=[1,22]. (Why?)
Your challenge, this month, is to help Charlie find sets A and B with at least four different numbers each, that will allow Bob to win.
The underlying challenge of this problem is to recognize that the starting value (N) must be a perfect square. This is because a perfect square is a number that will always have prime factors with even exponents; you can recognize this by considering that a square is the product of two of the same number so it stands to reason that its prime factorization will be comprised of pairs. By having even prime factor exponents and Alice going first it ensures that Bob will always reduce the final prime factor because if there are even exponents it will take an even number of times to reduce them by reductions of distinct prime factors.
Here are the possible combinations of the solution I provided and their prime factorization showing that they are all perfect squares.
While I did end up solving this using an optimized algorithm I spent a long time trying to formulate an analytic solution; this greatly informed my algorithmic approach. My line of thinking was to visualize the problem similar to getting four musical notes to play in harmony by considering a wave function to describe squares and look at the problem through the lens of trying to get 4 tones to have 4 common nodes. Here for instance is a wave that passes through the axis at every perfect square:
So if Alice chooses from a set A containing just 0 then if set B is made up of any four roots of this function Bob will win, but we need 3 more values for Alice to choose in set A though. Let’s add 96 to set A for instance. After a bit of thinking you will conclude that this is simply the equivalent of shifting this waveform to the left because the addition of 96 to any of its root will shift it back to passing through a perfect square:
So now Alice can select from a set A containing 0 and 96 and set B can contain any root shared by both of these functions. In this instance there are exactly four solutions.
This means if Alice selects 96 or 0 from set A, she can then select any one of those four values in set B to add to it and be sure that the result is a perfect square and Bob wins.
Ok, so that is two values for set A, how about a third? Well… this starts to get tricky, because how do you select a shift of a third copy of this function that will have those very same roots? Short answer: I don’t know. So I decided to look at what a solution set looks like graphically for all possible combinations of two functions to look for patterns:
Here what we are seeing is the orange vertical lines representing the roots of the base unshifted function, these are all perfect squares. The Y axis represents the shift of the function and its roots are shown in green, you can see how they shift left as the shift increases. Where a green and orange line crosses is then a root that is shared between the shifted function and the base function. Now the trick is to find horizontal lines that cross 4 intersections. For instance, in our prior example, if we drew a horizontal line at 96 it would cross at the intersections of green and orange lines at x = 4, 25, 100 and 529. Where I might have gone from here would be to look at the way the space visibly warps expanding in a curve from the origin and think about how to describe that space (perhaps a linear transformation?). Perhaps if I could describe the space I could gain an insight into deriving a way to identify a horizontal intersect…. but…. I am out of time and about to leave on a plane for vacation!
So I cranked out an algorithm that functioned as such:
- Create a list of Set A values (shifts) up to an arbitrarily high number
- Subtract each Set A value from an arbitrarily large list of perfect squares and record each value that is also a perfect square with each Set A value. These are the Set B values that when added to the Set A value are squares.
- If the Set A value has less than 4 Set B values I discard it.
- Now we have our data set, time to mine it! I iterate over each Set A value, compare it’s Set B values with the Set B values of all Set As after it in the list. If they match on at least 4 Set B values, compare those matching Set B values against the Set B values of all the Set A values in the list after that match.
- If I can find four Set A Values that share four (or more) of the same Set B Values, I have a solution!
I ran it for Set A values up to 1,000,000 and Set B values up to 40,000^2. The data set built in about 2hrs, mining found an answer in the first 30mins but ran to completion finding a dozen solutions over the next 12hrs of run time. I did not find a solution with more than 4 values in this data set (but they certainly exist).
