July 2022 - Challenge
The cell doubling game
Let’s assume there are n cells, each containing some amount of balls, in sorted order: a_1\le a_2\le \ldots \le a_n where a_i\in\mathbb{N} for 1\le i\le n.
Our goal is to empty one of the cells, but we can only perform one type of move: Choose two cells, i,j and transfer balls from a_i to a_j until the amount of balls in a_j is doubled.
As an example, assume k=3 and we are given the cells (3,4,8). By moving 3 from cell 2 to cell 1, we arrive at (6,1,8). Since we keep the cells in sorted order, we write this as (1,6,8).
A sequence of moves leading to one cell being emptied is
[(3, 4, 8), (1, 6, 8), (2, 6, 7), (4, 4, 7), (0, 7, 8)]
Your goal: Find a sequence of at most 20 moves emptying one cell from the initial configuration
(855661, 1395050, 1402703, 1575981, 2956165, 4346904, 5516627, 5693538, 6096226, 7359806)
Give the sequence in your solution in the above format.
A Bonus "*" will be given for finding a way to add at most 30,000,000 to the content of the cells given in the previous question, such that there is a sequence of moves emptying all the cells except one. As the solution pass the initial state; there is no need to supply the whole sequence.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/06/2022 @ 11:30:00 AM EST
Solution:
04/08/2022 @ 12:00 PM EST
List Updated:
02/08/2022 @ 11:30 AM EST
People who answered correctly:
*Lazar Ilic (30/6/2022 6:54 PM IDT)
Daniel Chong Jyh Tar (30/6/2022 7:04 PM IDT)
*Bert Dobbelaere (30/6/2022 11:27 PM IDT)
Giorgos Kalogeropulos (1/7/2022 12:12 AM IDT)
*Alper Halbutogullari (1/7/2022 4:59 AM IDT)
Gary M. Gerken (1/7/2022 5:50 AM IDT)
Prashant Wankhede (1/7/2022 6:48 AM IDT)
*Anders Kaseorg (1/7/2022 9:58 AM IDT)
Evert van Dijken (1/7/2022 12:23 PM IDT)
Paul Revenant (1/7/2022 12:31 PM IDT)
*Bertram Felgenhauer (1/7/2022 1:03 PM IDT)
Phil Proudman (1/7/2022 4:42 PM IDT)
*Eran Vered (1/7/2022 9:23 PM IDT)
*Ariel Landau (1/7/2022 11:45 PM IDT)
*Kevin Bauer (2/7/2022 12:15 AM IDT)
Alex Fleischer (2/7/2022 12:57 AM IDT)
*Victor Chang (2/7/2022 5:41 AM IDT)
*Harald Bögeholz (2/7/2022 8:08 AM IDT)
*Andreas Stiller (2/7/2022 11:38 AM IDT)
Michael Branicky (2/7/2022 8:04 PM IDT)
RichardGosiorovsky (2/7/2022 8:58 PM IDT)
Fabio Michele Negroni (2/7/2022 11:04 PM IDT)
*Daniel Bitin (3/7/2022 12:02 AM IDT)
Noam Zaks (3/7/2022 1:36 PM IDT)
Stéphane Higueret (3/7/2022 3:00 PM IDT)
*Benjamin Lui (3/7/2022 5:04 PM IDT)
Dieter Beckerle (3/7/2022 5:37 PM IDT)
Shouky Dan & Tamir Ganor (3/7/2022 5:52 PM IDT)
*Lorenz Reichel (3/7/2022 9:25 PM IDT)
*Dominik Reichl (3/7/2022 11:49 PM IDT)
*Stephen H. Landrum (4/7/2022 7:58 AM IDT)
Graham Hemsley (4/7/2022 3:06 PM IDT)
Clive Tong (4/7/2022 3:22 PM IDT)
*Tim Walters (5/7/2022 1:02 AM IDT)
*Lorenzo Gianferrari Pini (5/7/2022 10:20 AM IDT)
*Vladimir Volevich (5/7/2022 1:02 PM IDT)
Nir Paz (5/7/2022 5:26 PM IDT)
*Ali Gurel (6/7/2022 12:58 AM IDT)
Stefan Wirth (6/7/2022 5:21 AM IDT)
Ralf Jonas (6/7/2022 12:39 PM IDT)
Thomas Egense (6/7/2022 3:48 PM IDT)
*Daniel Johnson-Chyzhykov (7/7/2022 6:40 PM IDT)
*Luke Pebody (8/7/2022 11:37 AM IDT)
Kandala Srinivas (8/7/2022 9:40 PM IDT)
*Liubing Yu (9/7/2022 3:40 AM IDT)
*Yasodhar Patnaik (11/7/2022 9:58 AM IDT)
*Franciraldo Cavalcante (12/7/2022 12:47 AM IDT)
*Motty Porat (12/7/2022 3:03 AM IDT)
Andreas Puccio (12/7/2022 7:41 PM IDT)
*Soumitra Agarwal (13/7/2022 11:00 PM IDT)
*Zhang Zhiqiang (14/7/2022 4:49 AM IDT)
David Greer (14/7/2022 1:12 PM IDT)
Marco Bellocchi (15/7/2022 1:09 AM IDT)
Grant Boudreaux (15/7/2022 7:04 PM IDT)
Ivan Rendo (17/7/2022 12:21 PM IDT)
Viswanadh Kandala (17/7/2022 1:25 PM IDT)
*Nyles Heise (18/7/2022 4:51 AM IDT)
*Latchezar Christov (20/7/2022 5:38 PM IDT)
Fakih Karademir (22/7/2022 3:47 PM IDT)
Almog Yair (23/7/2022 10:07 PM IDT)
*Karl Mahlburg (24/7/2022 2:44 AM IDT)
Sachal Mahajan (24/7/2022 7:00 AM IDT)
Shirish Chinchalkar (25/7/2022 3:54 AM IDT)
Andrew Milas (25/7/2022 8:27 PM IDT)
Sanandan Swaminathan (26/7/2022 1:15 PM IDT)
*Issa Bou Zeid (27/7/2022 11:54 AM IDT)
*John Tromp (28/7/2022 4:12 PM IDT)
Walter Sebastian Gisler (29/7/2022 7:25 AM IDT)
Stephane Michel (29/7/2022 2:01 PM IDT)
Kang Jin Cho (29/7/2022 9:49 PM IDT)
*Chris Shannon(30/7/2022 12:51 AM IDT)
David F.H. Dunkley (31/7/2022 11:54 PM IDT)
Radu-Alexandru Todor (2/8/2022 2:59 AM IDT)