Ponder This Challenge - February 2021 - The trusted neighbors' vaccination ring

A set of people is placed on the positive, non-zero values of an NxN grid. Our goal is to vaccinate all the people in the grid against COVID-19. Every person has a subset of "trusted neighbors". Once all of a person's trusted neighbors are vaccinated, that person will get vaccinated as well. (If the set of trusted neighbors is empty, that person is already convinced and gets vaccinated without further convincing.)
To carry out this task as efficiently as possible, we need to find the minimum set of people that must be directly convinced to start a chain reaction that will convince all others.
We can represent the trust relationship as a four-digit binary number. The digit '1' indicates trust, the digit '0' indicates no trust. The neighbors are those people at the four points connected to a given person on the grid, from the above neighbor and clockwise, i.e., the above, right, below, and left neighbors. A point on the edge of the grid has fewer than four neighbors.

For example, the trust relationship 1001 for the point (2,3) means that this grid point trusts its upper neighbor (2,4) and left neighbor (1,3). Once those points are vaccinated, in the next time step (2,3) will also become vaccinated.

As another example, for the point (1,N) the meaning of 1111 is that only the right neighbor (2,N) and the lower neighbor (1,N-1) are counted as trusted neighbors; the upper and left neighbors (1,N+1) and (0,N) are not included in the grid and so do not count (so 1111 is equivalent to 0110 in this case).

To represent the board in a compact fashion, we convert a point's binary number trust relationship to hexadecimal and use that hexadecimal digit to represent that point. So 0101 is represented by '5', 1111 is represented by 'f', etc.
An example of a 3x3 grid is:

Here the point (1,2) has the trust relationship '7', i.e., 0111, meaning it depends on (2,2) (right) and (1,1) (down), but not on (1,3) above (since it is 0) nor on (0,2) to the left (because even though it's defined as a trusted neighbor, it's outside the grid). It can be seen that since (1,1) is "2", i.e., it depends only on its non-existing neighbor (1,0), making its set of trusted neighbors essentially empty, therefore it will get vaccinated by itself, but (2,2) will not; convincing (1,2) to vaccinate directly will start a chain reaction ending in the vaccination of all points. So for this grid, the set [(1,2)] suffices to ensure full vaccination.

Your goal: Find a minimal set for ensuring eventual full vaccination of the following 12x12 grid:

A bonus '*' will be given for finding a 12x12 grid with a minimal set of size exactly 42.

Solution

• Click here to view the solution

  A minimal set of cells contains 35 cells. One possible set is

  [(11, 3), (9, 1), (7, 8), (5, 11), (7, 11), (8, 10), (9, 10), (10, 11), (11, 11), (9, 9), (10, 8), (11, 9), (11, 7), (11, 6), (4, 12), (2, 11), (2, 7), (2, 6), (4, 5), (4, 7), (5, 8), (4, 9), (2, 2), (2, 4), (2, 5), (5, 4), (6, 5), (7, 5), (8, 4), (9, 5), (10, 5), (11, 4), (4, 2), (6, 2), (5, 3)]
  

  A simple way to simplify finding such a set is to compute the strongly connected components of the dependency graph; each connected component can be handled independently (and they are small enough for brute-force solutions).

  To generate a board with a minimal set of size 42, one can join several disconnected components and obtain the sum of their respective sets. One simple way to do this is

  222222000000
  aaaaaa000000
  888888000000
  222222222222
  aaaaaaaaaaaa
  888888888888
  222222222222
  aaaaaaaaaaaa
  888888888888
  222222222222
  aaaaaaaaaaaa
  888888888888
  

  Sent by Thomas Pircher. But many similar methods exist. (The number 42 proved too easy, but I am biased towards it.)

Solvers

• *Bertram Felgenhauer (1/2/2021 3:27 PM IDT)
• *Alper Halbutogullari (1/2/2021 5:56 PM IDT)
• Daniel Chong Jyh Tar (1/2/2021 6:20 PM IDT)
• *Guillaume Escamocher (1/2/2021 8:45 PM IDT)
• *Gary M. Gerken (2/2/2021 10:25 AM IDT)
• *Sanandan Swaminathan (2/2/2021 11:40 AM IDT)
• *Walter Sebastian Gisler (2/2/2021 2:41 PM IDT)
• *Paul Shaw (3/2/2021 12:06 AM IDT)
• *Uoti Urpala (3/2/2021 2:54 AM IDT)
• *Eden Saig (3/2/2021 3:09 AM IDT)
• *Paul Revenant (3/2/2021 3:50 PM IDT)
• Reda Kebbaj (3/2/2021 6:14 PM IDT)
• *Luca Pintori (3/2/2021 6:39 PM IDT)
• *Ilya Tarygin (3/2/2021 7:20 PM IDT)
• *Dominik Reichl (3/2/2021 8:24 PM IDT)
• *Giuliano Bertoletti (3/2/2021 9:54 PM IDT)
• Dieter Beckerle (4/2/2021 12:33 AM IDT)
• *Chuck Carroll (4/2/2021 10:12 AM IDT)
• *Willem Hendriks (4/2/2021 1:50 PM IDT)
• *Andreas Stiller (5/2/2021 2:40 AM IDT)
• *Harald Bögeholz (5/2/2021 7:11 AM IDT)
• *Dan Dima (5/2/2021 1:37 PM IDT)
• *Yasodhar Patnaik (5/2/2021 8:43 PM IDT)
• *Glauber Guarinello (5/2/2021 9:25 PM IDT)
• *Florian Fischer (6/2/2021 12:21 AM IDT)
• *Karl D’Souza (6/2/2021 12:25 AM IDT)
• Andrew Mullins (6/2/2021 10:34 PM IDT)
• *Latchezar Christov (6/2/2021 10:48 PM IDT)
• Alex Fleischer (6/2/2021 11:01 PM IDT)
• *Kai Guttmann (7/2/2021 3:15 AM IDT)
• Graham Hemsley (7/2/2021 12:49 PM IDT)
• *Joaquim Neves Carrapa (7/2/2021 8:29 PM IDT)
• *Christopher Marks (7/2/2021 8:51 PM IDT)
• *Amos Guler (7/2/2021 10:38 PM IDT)
• *Thomas Pircher (7/2/2021 10:51 PM IDT)
• *Glauber Guarinello (7/2/2021 11:19 PM IDT)
• *Nicolas Lopez (8/2/2021 7:46 PM IDT)
• *Hans Kodde (8/2/2021 11:01 PM IDT)
• *Pål Hermunn Johansen (9/2/2021 4:15 PM IDT)
• *Kamil Jarosz (9/2/2021 7:05 PM IDT)
• Thomas Egense (9/2/2021 11:44 PM IDT)
• *Victor Chang (10/2/2021 8:34 AM IDT)
• *Hu Shuai (13/2/2021 2:47 PM IDT)
• *Lorenz Reichel (13/2/2021 8:46 PM IDT)
• Soonho You (14/2/2021 3:51 AM IDT)
• *Simeon Krastnikov (15/2/2021 6:56 AM IDT)
• Ilya Tarygin (15/2/2021 2:21 PM IDT)
• *Vladimir Volevich (15/2/2021 4:45 PM IDT)
• *Phil Proudman (15/2/2021 6:52 PM IDT)
• *Fei Xie (15/2/2021 7:21 PM IDT)
• *Cynthia Beauchemin (15/2/2021 10:09 PM IDT)
• *James Muir (16/2/2021 5:10 AM IDT)
• *Matthews, Aaron (16/2/2021 7:05 AM IDT)
• Daniel Bitin (16/2/2021 9:19 AM IDT)
• *David Greer (16/2/2021 1:27 PM IDT)
• *Marco Bellocchi (16/2/2021 3:22 PM IDT)
• *Nyles Heise (17/2/2021 7:51 AM IDT)
• *Bert Dobbelaere (20/2/2021 4:36 PM IDT)
• Egil Støren (22/2/2021 4:29 PM IDT)
• *Tamir Ganor & Shouky Dan (25/2/2021 9:55 AM IDT)
• *Chris Shannon (27/2/2021 1:47 AM IDT)
• *Motty Porat (27/2/2021 9:21 PM IDT)
• Todd Will (27/2/2021 10:41 PM IDT)
• *Oscar Volpatti (28/2/2021 6:41 AM IDT)
• Egil Støren (22/2/2021 4:29 PM IDT)
• *Tamir Ganor & Shouky Dan (25/2/2021 9:55 AM IDT)
• *Chris Shannon (27/2/2021 1:47 AM IDT)
• *Motty Porat (27/2/2021 9:21 PM IDT)
• Todd Will (27/2/2021 10:41 PM IDT)
• *Oscar Volpatti (28/2/2021 6:41 AM IDT)
• Arne Vik (28/2/2021 3:04 PM IDT)
• Steven Langerwerf & Susan Brommer (28/2/2021 3:45 PM IDT)
• *Andy Greig (only the "*" part) (28/2/2021 7:15 PM IDT)
• *Zhou Hangbo (only the "*" part) (28/2/2021 7:43 PM IDT)
• *Fabio Filatrella (28/2/2021 9:09 PM IDT)
• *Clement Heyd (only the "*" part) (28/2/2021 11:39 PM IDT)
• Reiner Martin (1/3/2021 1:03 AM IDT)
• *Radu-Alexandru Todor (1/3/2021 2:54 AM IDT)
• *Dezhi Zhao (1/3/2021 4:49 AM IDT)
• *Filippos Christou (only the "*" part) (1/3/2021 2:41 PM IDT)
• *Muralidhar Seshadri (1/3/2021 6:18 PM IDT)
• Dipto Thakurta (1/3/2021 6:34 PM IDT)
• *Alexander Strasser (2/3/2021 12:17 AM IDT)
• *Kang Jin Cho (2/3/2021 7:45 PM IDT)
• *Vromen, Tomer (2/3/2021 10:54 PM IDT)
• Li Li (3/3/2021 2:23 AM IDT)