Thread: January 2019 View Single Post
2019-01-04, 05:57   #29
LaurV
Romulan Interpreter

Jun 2011
Thailand

100010011110102 Posts

Quote:
 Originally Posted by a1call What exactly are you referring to when you say false? Please be more specific. Thanks.
He refers to the fact that if you don't have the restriction of distinct primes, then Alice (the first choicer) wins every time by dividing with the number itself.

25 -> 1
100 -> 1
etc.

This problem has not much to program, is pure math, and quite simple actually. As said above, N must always be a perfect square. The sums can not be square free, because Alice would win in one shot, picking the whole number as the first divisor, and they can't be non-squares, because then Alice will chose the first time in such a way to leave a perfect square, and she wins. For example, if $$N=2^a3^b5^c...$$ then Alice picks first time the product of all primes which have the odd power, and then what is left is a perfect square. Now, the only left for you is to prove that if the number is perfect square, then Bob (the second picker) wins every time. There is a theorem which states that the only numbers with an odd number of divisors are the perfect squares (why? and why do you need an odd number of divisors?) anyhow this is not complicate to prove, but you don't need to go so deep, because there is a simple strategy to win: if N is perfect square, then any prime in N has its pair, and all Bob has to do is to pick the same product Alice picks, every time, leaving every time behind a perfect square. Start with a perfect square, end with a smaller perfect square, repeat. This ends in 1, and it is the "infinite descent" method, invented by Fermat, hehe - as members of mersenneforum, you should know that :razz:

So, all the fuss is about finding two sets of numbers whose paired sums are always perfect squares. How difficult is that? (from the number of the persons who already solved the puzzle in just few hours, and from this current thread, you can see that the puzzle is trivial - so this is another skip this month).

Last fiddled with by LaurV on 2019-01-04 at 06:32