## Le Monde puzzle [#1008]

**A**n arithmetic Le Monde mathematical puzzle (or two independent ones, rather):

*The set of integers between 1 and 2341 is partitioned into sets such that a given set never contains both n and 3n. What is the largest possible size of one of these sets?**Numbers between 1 and 2N are separated in two sets A and B of size N. Alice takes the largest element out of A and the smallest element out of B, records the absolute difference as S, and then repeats the sampling, adding the absolute difference to S at each draw. Bob does the same with numbers between 1 and 2P, with P<N, obtaining a total value of R. Alice points out that S-R=2341. What are the values of N and P?*

**T**he first question seems hard to solve by brute force simulation. My first idea is to take all prime numbers [except 3!] less than 2341, which is itself a prime number, and all combinations of these numbers less than 2341, since none of those is divisible by 3. Adding 3 as a final item keeps the constraint fine if 1 is not part of it (but 1 is not a prime number, so this is under control). Adding instead 1 to the set has the same impact but seems more natural. The number of prime numbers is 346, while the total size of the set thus constructed is 1561. Equal to 1+2×2340/3. However, the constraint in the puzzle does not exclude *m* and *9m*. Or *m* and *9²m*, or *m* and *9³m*. Considering such multiples within {1,…,2341} leads to a set with 1765 integers.

The second puzzle is indeed independent and actually straightforward when one realises that the sums S and R are always equal to N² and P², respectively. (This is easily proven by invariance under a permutation turning the lowest entries to B and the largest ones to A. But there must be a rank statistic identity behind this result!) Hence it boils down to figuring out a pair (N,P) such that N²-P²=2341. Since 2341=(N-P)(N+P) is prime, this implies N=P+1. And N²-(N-1)²=N²-N²+2N-1=2341. Which leads to (N,P)=(1171,1170) as the only solution.

May 16, 2017 at 11:18 am

In the second puzzle, the constraint is actually S+R=2341. The only solution is then .

May 16, 2017 at 1:04 pm

Oh dear, I confused sum and difference! And lost 24 points in the meanwhile…