Ponder This Challenge - July 2022 - The cell doubling game

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.

Solution

• Click here to view the solution

  July 2022 Solution:

  One solution, given by Kevin Bauer, is:

  [
  (855661, 1395050, 1402703, 1575981, 2956165, 4346904, 5516627, 5693538, 6096226, 7359806),
  (855661, 1395050, 1402703, 1575981, 2560462, 4346904, 5693538, 5912330, 6096226, 7359806),
  (183896, 855661, 1395050, 1402703, 1575981, 2560462, 4346904, 5693538, 7359806, 11824660),
  (183896, 855661, 1346634, 1395050, 1402703, 1575981, 2560462, 7359806, 8693808, 11824660),
  (367792, 855661, 1346634, 1395050, 1402703, 1575981, 2560462, 7359806, 8509912, 11824660),
  (367792, 855661, 1346634, 1402703, 1575981, 2560462, 2790100, 7114862, 7359806, 11824660),
  (367792, 855661, 1346634, 1387397, 1575981, 2560462, 2805406, 7114862, 7359806, 11824660),
  (244944, 367792, 855661, 1346634, 1387397, 1575981, 2560462, 2805406,11824660, 14229724),
  (244944, 244944, 367792, 855661, 1346634, 1387397, 1575981, 5120924, 11824660, 14229724),
  (0, 367792, 489888, 855661, 1346634, 1387397, 1575981, 5120924, 11824660, 14229724)
  ]
  For the bonus part, in order to be able to reach 0 in all cells but one, the sum of all cells must be a power of 2; any change to the cells that ensures it will work. A simple solution given by John Tromp relies on the following
  (1576000, 1576000, 1576000, 1576000, 3152000, 4728000, 6304000, 6304000, 6304000, 17336000)

Solvers

• *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)