Puzzle
8 minute read

Ponder This Challenge - January 2021 - Vaccinating Robot

A robot is distributing COVID-19 vaccines on an NxN grid. At the beginning, the robot is located at the (0,0) cell facing UP, and every cell in the grid is marked as having received zero doses of the vaccine. The robot's goal is to ensure that each cell on the grid gets two doses of vaccine by visiting each cell twice.

Unfortunately, the robot was attacked by anti-vaccine bots, causing its navigation system to malfunction. As a result, the robot now acts like this at every step:

  1. If the cell was vaccinated 0 times, it administers one dose (raising the cell's status from "0" to "1") and turns 90 degrees CLOCKWISE.

  2. If the cell was vaccinated 1 time, it administers one dose (raising the cell's status from "1" to "2") and turns 90 degrees COUNTERCLOCKWISE.

  3. If the cell was vaccinated 2 times, the robot does not change direction.

    The robot then takes one step in the direction it is currently facing. If the step takes it out of the grid, it returns from the other side (i.e., coordinate arithmetic is modulo N). Here is an example of how the robot acts on a 4x4 grid for the first few steps (the cell (0,0) is pictured at the top-left corner). The current cell is marked by square brackets; recall that the robot begins by facing upwards.

    [0]  0   0   0
 0   0   0   0
 0   0   0   0
 0   0   0   0
            
 1  [0]  0   0
 0   0   0   0
 0   0   0   0
 0   0   0   0
            
 1   1   0   0
 0  [0]  0   0
 0   0   0   0
 0   0   0   0
    
 1   1   0   0
[0]  1   0   0
 0   0   0   0
 0   0   0   0
        
[1]  1   0   0
 1   1   0   0
 0   0   0   0
 0   0   0   0
        
 2   1   0  [0]
 1   1   0   0
 0   0   0   0
 0   0   0   0

    It can be seen already that for N=4, the robot cannot administer two doses to the whole grid. Luckily, some of the anti-vaccine bots remain and can be used to our benefit. We can change some cells of the grid to contain the value "B" and give the robot an additional rule:

  4. If the cell's status is "B", the robot avoids the anti-vaccine bots, administers no vaccine, and turns 90 degrees COUNTERCLOCKWISE. The robot then takes one step as usual (the anti-vaccine bot cannot harm it).

    For example:

    [0]  B   0   0
 0   0   0   0
 0   0   0   0
 0   0   0   0
            
 1  [B]  0   0
 0   0   0   0
 0   0   0   0
 0   0   0   0
            
 1   B   0   0
 0   0   0   0
 0   0   0   0
 0  [0]  0   0

    We do not need the "B" cells to be vaccinated.

Your goal is to find a placement of two "B" cells that ensures the rest of the grid will reach "2" status eventually for N=50. Give your answer in the following format: [(a,b), (x,y)] where (a,b) are the coordinates of the first "B" cell and (x,y) are the coordinates of the second "B" cell.

A bonus '*' for finding a placement of at most three "B" cells that works for N=100. Give your answer in the format [(a,b), (x,y), (r,s)] or [(a,b), (x,y)].

A bonus '**' for finding the minimum N such that 2 "B" cells do not suffice for it.

Solution

  • A possible solution for the 50x50 grid is [(0,34) , (48,1)].

    A possible solution for the 100x100 grid is [(62, 0), (64, 0)].

    The "**" part was phrased wrong, since it omitted the possibility that two bots always suffice, for any grid size. Many solvers found solutions with two bots for large grid sizes, the largest is [(133, 974), (1099, 421)] for N=1106 found by Alper Halbutogullari. Finding a proof that two bots always suffice seems to be an interesting problem.

Solvers

  • *Alper Halbutogullari (30/12/2020 11:33 PM IDT)
  • Lorenz Reiche (31/12/2020 12:14 AM IDT)
  • *Reiner Martin (31/12/2020 1:12 AM IDT)
  • Keith Schneider (31/12/2020 1:28 AM IDT)
  • *Gary M. Gerken (31/12/2020 7:01 AM IDT)
  • *Daniel Chong Jyh Tar (31/12/2020 7:51 AM IDT)
  • *Harald Bögeholz (31/12/2020 8:37 AM IDT)
  • JJ Rabeyrin (31/12/2020 9:24 AM IDT)
  • Yuanjie Pu (31/12/2020 9:26 AM IDT)
  • *Dmitry Kim (31/12/2020 11:59 AM IDT)
  • *Dieter Beckerle (31/12/2020 5:29 PM IDT)
  • Franciraldo Cavalcante (31/12/2020 5:30 PM IDT)
  • *Guillaume Escamocher (31/12/2020 6:06 PM IDT)
  • *Amos Guler (31/12/2020 6:31 PM IDT)
  • *Almog Yair (31/12/2020 10:29 PM IDT)
  • *Uoti Urpala (31/12/2020 10:38 PM IDT)
  • *Muralidhar Seshadri (1/1/2021 2:04 AM IDT)
  • *Evert van Dijken (1/1/2021 11:19 AM IDT)
  • *Eden Saig (1/1/2021 1:59 PM IDT)
  • Graham Hemsley (1/1/2021 3:51 PM IDT)
  • *Richard Gosiorovsky (1/1/2021 8:14 PM IDT)
  • *Cynthia Beauchemin (1/1/2021 9:31 PM IDT)
  • *Christian Pfaffenzeller (2/1/2021 2:20 AM IDT)
  • *Victor Chang (2/1/2021 4:53 AM IDT)
  • *Sanandan Swaminathan (2/1/2021 8:23 AM IDT)
  • Yasodhar Patnaik (2/1/2021 8:31 AM IDT)
  • Greg Janée (2/1/2021 6:55 PM IDT)
  • Kennedy (3/1/2021 1:51 AM IDT)
  • James Dow Allen (3/1/2021 1:07 PM IDT)
  • Dan Dima (3/1/2021 3:29 PM IDT)
  • Franciraldo Cavalcante (3/1/2021 4:02 PM IDT)
  • Shirish Chinchalkar (3/1/2021 5:02 PM IDT)
  • Ivan Rendo (3/1/2021 6:56 PM IDT)
  • *Fabio Michele Negroni (3/1/2021 7:47 PM IDT)
  • Seth Cohen (3/1/2021 11:40 PM IDT)
  • *Bert Dobbelaere (4/1/2021 12:49 AM IDT)
  • *Joaquim Carrapa (4/1/2021 5:17 AM IDT)
  • *Florian Fischer (4/1/2021 9:53 AM IDT)
  • andy greig (4/1/2021 2:33 PM IDT)
  • *Govind Raj Jujare (4/1/2021 8:02 PM IDT)
  • Willem H Hendriks (4/1/2021 10:30 PM IDT)
  • *Thomas Egense (4/1/2021 11:05 PM IDT)
  • *Kai Guttmann (4/1/2021 11:17 PM IDT)
  • Harry Liversedge (5/1/2021 9:16 AM IDT)
  • Michael Oosterhagen (5/1/2021 9:52 AM IDT)
  • *Sebastian Bohm and Martí Bosch (5/1/2021 11:59 AM IDT)
  • Ralf Jonas (5/1/2021 1:58 PM IDT)
  • Sri Mallikarjun J (5/1/2021 6:16 PM IDT)
  • *Nigel Brumpton (5/1/2021 11:19 PM IDT)
  • *Shouky Dan & Tamir Ganor (5/1/2021 11:06 PM IDT)
  • *Hugh Taiyo Coleman (6/1/2021 5:29 AM IDT)
  • Rainy Sokhonn (6/1/2021 8:35 AM IDT)
  • Alex Fleischer (6/1/2021 7:58 PM IDT)
  • Erik Hostens (6/1/2021 9:49 PM IDT)
  • *Paul Revenant (6/1/2021 10:54 PM IDT)
  • Kamlesh Nahata (7/1/2021 1:39 AM IDT)
  • Mario Zemancik (7/1/2021 10:19 AM IDT)
  • *Vladimir Volevich (7/1/2021 6:01 PM IDT)
  • Walter Sebastian Gisler (7/1/2021 8:52 PM IDT)
  • Daniel Bitin (8/1/2021 1:58 PM IDT)
  • Filippos Christou (8/1/2021 6:54 PM IDT)
  • *Clive Tong (9/1/2021 9:41 AM IDT)
  • *Marcelo De Barros (9/1/2021 8:53 AM IDT)
  • *Aviran Sadon (10/1/2021 5:33 PM IDT)
  • *Toke Eskildsen (11/1/2021 10:07 AM IDT)
  • Radu-Alexandru Todor (11/1/2021 12:04 PM IDT)
  • *Albert Stadler (11/1/2021 2:24 PM IDT)
  • *Florian Sikora (11/1/2021 4:30 PM IDT)
  • *Dipto Thakurta (11/1/2021 8:09 PM IDT)
  • Jordan Rinder (11/1/2021 9:58 PM IDT)
  • *Michael Liepelt (11/1/2021 10:10 PM IDT)
  • *Emmanuel Lazard (12/1/2021 12:52 AM IDT)
  • *Liubing Yu (12/1/2021 10:12 AM IDT)
  • *Marco Bellocchi (12/1/2021 3:08 PM IDT)
  • *Yasodhar Patnaik (12/1/2021 5:43 PM IDT)
  • *Rajesh Sathiyanarayanan (13/1/2021 10:46 AM IDT)
  • *Fakih Karademir (14/1/2021 1:41 AM IDT)
  • *Matias A Amado (14/1/2021 5:01 AM IDT)
  • *Kang Jin Cho (14/1/2021 8:48 AM IDT)
  • *Thomas Huet (14/1/2021 12:26 PM IDT)
  • *Daniel Moolman (15/1/2021 1:05 PM IDT)
  • *José Eduardo Gaboardi de Carvalho (15/1/2021 8:38 PM IDT)
  • *David Greer (17/1/2021 10:41 PM IDT)
  • *Suryaprasad Kareenahalli (18/1/2021 5:49 AM IDT)
  • *Bertram Felgenhauer (18/1/2021 12:01 PM IDT)
  • Daniëlle van den Berg (18/1/2021 1:41 PM IDT)
  • *Eric Niblock (19/1/2021 1:18 AM IDT)
  • Balakrishnan V (19/1/2021 7:26 AM IDT)
  • *Latchezar Christov (19/1/2021 4:36 PM IDT)
  • Emmanuel Lazard (20/1/2021 9:37 PM IDT)
  • *Paolo Farinelli (21/1/2021 8:23 PM IDT)
  • *Nicolas Lopez (23/1/2021 12:48 AM IDT)
  • *Christopher Marks (24/1/2021 5:54 AM IDT)
  • Vromen, Tomer (24/1/2021 10:39 AM IDT)
  • *Thomas Pircher (24/1/2021 4:44 PM IDT)
  • *Reda Kebbaj (25/1/2021 3:07 AM IDT)
  • *Carlos Lopez (25/1/2021 6:35 PM IDT)
  • *David F.H. Dunkley (26/1/2021 1:25 AM IDT)
  • *Hu Shuai (26/1/2021 1:10 PM IDT)
  • David Friedman (27/1/2021 5:16 PM IDT)
  • Steven Langerwerf (28/1/2021 1:28 AM IDT)
  • *Nyles Heise (28/1/2021 4:57 AM IDT)
  • *Fabio Filatrella (28/1/2021 2:41 PM IDT)
  • *Ilya Tarygin (28/1/2021 6:01 PM IDT)
  • *Li Wang (30/1/2021 1:35 PM IDT)
  • *Motty Porat (31/1/2021 12:16 AM IDT)
  • *Chris Shannon (31/1/2021 5:40 AM IDT)
  • *Matt Rips (31/1/2021 7:25 AM IDT)
  • Clement Heyd (31/1/2021 1:14 PM IDT)
  • Zhou Hangbo (31/1/2021 2:56 PM IDT)
  • Michael Branicky (31/1/2021 5:21 PM IDT)
  • *Andreas Stiller (31/1/2021 8:02 PM IDT)
  • *Hans Kodde (31/1/2021 10:15 PM IDT)
  • *Alexander Strasser (31/1/2021 11:32 PM IDT)
  • *Karl D’Souza (31/1/2021 11:35 PM IDT)
  • *Oscar Volpatti (1/2/2021 8:05 AM IDT)
  • *Li Li (1/2/2021 10:37 AM IDT)
  • Sumanth Ravipati (1/2/2021 12:03 PM IDT)
  • *James Muir (1/2/2021 5:20 PM IDT)
  • Todd Will (1/2/2021 7:35 PM IDT)
  • Armin Krauss (1/2/2021 8:50 PM IDT)
  • *Collin Pearce (3/2/2021 2:07 AM IDT)

Related posts