August 2020 - Challenge

<< July September >>

Let us consider a game similar to Nim. In this game, Alice and Bob have three piles of coins. The players take turns alternately. At every turn, the current player chooses some of the piles, and removes the same number of coins from each pile chosen (at least one coin must be removed from each pile; there are no other restrictions).
A position in the game can be described by a triplet (a,b,c) where 0≤a≤b≤c denoting the (sorted) number of coins in the piles. The rules of the game consists of two lists of positions, marked LOSE and WIN. In the default set of rules, LOSE contains the single position (0,0,0) and WIN is empty. A player whose turn starts at a LOSE position loses; starting at a WIN position wins; otherwise a move is made and the turn passed to the other player.
A winning position is one where the current player can force a win (in one or more steps) by playing correctly; a losing position is a non-winning position. For example, in the default rules, (0,7,7) is a winning position, since the player can remove 7 coins from the two non-empty piles; (0,1,2) is a losing position since the possible moves result in the positions (0,1,1), (0,0,1) or (0,0,2) which are all winning (so if Alice starts in (0,1,2) Bob wins in the next move).

We consider the set of all positions (a,b,c) where 0≤a≤b≤c≤100, i.e. the maximum number of coins in any of the piles is 100. Out of the total 176851 positions, exactly 1264 positions are losing. Our goal is to lower this number to at most 1252 by finding an alternative set of rules (LOSE and WIN sets). As an example, adding (1,1,1) to LOSE increases the number of losing positions in the game to 1269.
Provide your answer as two lists of positions, e.g.,

[(1,1,1),(2,2,2)]
[(1,2,3),(4,5,6)]

This denotes the set LOSE = {(1,1,1), (2,2,2)} and WIN={(1,2,3), (4,5,6)}}. Both WIN and LOSE should be of size at most 10. The lists should result in a game which has at most 1252 losing positions.




A bonus '*' for finding and proving the minimum number of losing positions in this game, or for the case where 0≤a≤b≤c≤10, i.e., where each pile has at most 10 coins.



We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Challenge: 30/07/2020 @ 12:00 PM EST
Solution: 03/09/2020 @ 12:00 PM EST
List Updated: 02/09/2020 @ 12:00 PM EST

People who answered correctly:

Uoti Urpala(02/8/2020 01:56 AM IDT)
Sean Egan(02/8/2020 02:10 AM IDT)
Alper Halbutogullari(02/8/2020 08:12 AM IDT)
JJ Rabeyrin(02/8/2020 10:48 AM IDT)
Guillermo Wildschut(02/8/2020 01:33 PM IDT)
Loukas Sidiropoulos(02/8/2020 06:03 PM IDT)
Jacob Burnim(02/8/2020 08:20 PM IDT)
Keith Schneider(02/8/2020 09:46 PM IDT)
Anders Kaseorg(03/8/2020 04:40 AM IDT)
Michael Branicky(03/8/2020 05:59 AM IDT)
Graham Hemsley(03/8/2020 11:40 AM IDT)
Dominik Reichl(03/8/2020 04:16 PM IDT)
Ricardo Koller(03/8/2020 05:31 PM IDT)
Anders Kaseorg(03/8/2020 09:40 PM IDT)
Parth Trivedi(04/8/2020 12:44 AM IDT)
Dan Piponi(04/8/2020 01:29 AM IDT)
Victor Chang(04/8/2020 11:42 AM IDT)
Reiner Martin(04/8/2020 10:16 PM IDT)
Noam Zaks(05/8/2020 06:00 PM IDT)
Jacoby Jaeger(06/8/2020 10:57 AM IDT)
Bertram Felgenhauer(06/8/2020 07:28 PM IDT)
Dieter Beckerle(06/8/2020 08:11 PM IDT)
*Vladimir Volevich(07/8/2020 10:52 PM IDT)
Clive Tong(07/8/2020 11:07 PM IDT)
Siddhartha Srivastava(07/8/2020 11:09 PM IDT)
Nir Paz(08/8/2020 11:08 PM IDT)
Tom K(10/8/2020 05:42 PM IDT)
Lorenz Reichel(10/8/2020 07:02 PM IDT)
Bert Dobbelaere(10/8/2020 09:20 PM IDT)
Kai Guttmann(12/8/2020 12:14 AM IDT)
Balakrishnan Varadarajan(12/8/2020 08:07 AM IDT)
Iván Rendo-Barreiro(12/8/2020 12:45 PM IDT)
Rif A. Saurous(12/8/2020 09:32 PM IDT)
Daniel Bitin(13/8/2020 9:08 PM IDT)
Amir Sarid(14/8/2020 6:19 PM IDT)
Todd Will(16/8/2020 6:31 PM IDT)
David Greer(17/8/2020 12:09 AM IDT)
David Friedman(17/8/2020 12:52 AM IDT)
*Fabio Michele Negroni(18/8/2020 4:02 PM IDT)
Shouky Dan and Tamir Ganor(20/8/2020 11:01 PM IDT)
Yongxing Jim Wang(21/8/2020 5:38 AM IDT)
Philipp Seemann(23/8/2020 6:05 PM IDT)
Daniel Chong Jyh Tar(24/8/2020 8:40 PM IDT)
Collin Pearce(26/8/2020 7:54 PM IDT)
LI WANG(27/8/2020 1:05 PM IDT)
Nyles Heise(28/8/2020 6:41 AM IDT)
Божидар Стајчић(28/8/2020 11:24 AM IDT)
Eden Saig(29/8/2020 11:52 PM IDT)
Florian Fischer(30/8/2020 9:56 PM IDT)
Zhou Hangbo(31/8/2020 10:17 AM IDT)
David Smalling(1/9/2020 12:55 AM IDT)
Radu-Alexandru Todor(1/9/2020 12:57 AM IDT)
Markus Kottmann(1/9/2020 1:55 AM IDT)
Oscar Volpatti(1/9/2020 2:06 AM IDT)
Li Li(1/9/2020 7:36 AM IDT)
Kang Jin Cho(1/9/2020 10:55 PM IDT)
Jörg Schepers(1/9/2020 11:50 PM IDT)
Erik Wünstel(2/9/2020 7:01 PM IDT)