12
$\begingroup$

You start with a 4x4 grid filled with zeroes. If you press a cell then the cell and all its neighboring (horizontally and vertically) cells will have their numbers increased by 1. What is the most number of distinct primes you can obtain?

$\endgroup$
3
  • $\begingroup$ (off topic) Have you done any coding for solving 'ball sort' puzzles? $\endgroup$ Aug 8, 2022 at 21:47
  • $\begingroup$ @DanielMathias no, but it sounds like an interesting thing to try. $\endgroup$ Aug 9, 2022 at 2:46
  • 1
    $\begingroup$ I thought so too. Don't limit yourself to the 'easy' levels, though; the app I've been playing on uses up to 15 colors with 5 balls of each color. $\endgroup$ Aug 9, 2022 at 23:34

4 Answers 4

15
$\begingroup$

Here is my solution:

All 16 cells are primes:

 Moves          Result
 117 51 50 30   173 223 179 101
 5   5  48 21   127 139 131 103
 0   30 7  4    59  79  107 83
 24  37 18 51   61  109 113 73

How I found this:

First I used light chasing to fill the top 3 rows with primes. That is to say, I did some nice large number of moves on the top row cells, and then on each subsequent row I did some mostly arbitrary moves to make the row above show distinct primes. The last row then contains numbers that are not necessarily prime or distinct.

 Moves          Result
 90 70 50 30    173 223 179 101
 13 13 29 21    127 139 131 103
 11 14 18 23    59  79  107 83
 21 23 23 21    55  81  85  67

To turn the bottom row into primes I added on the following patterns (the first pattern was added 3 times, the second pattern was added 14 times):

 Moves             Result
 -5  3  0  0    0  0  0  0
  2  2 -3  0    0  0  0  0
  1 -4  1  3    0  0  0  0
  1  0  3 -4    2  0  0  2

  3 -2  0  0    0  0  0  0
 -1 -1  2  0    0  0  0  0
 -1  2 -1 -2    0  0  0  0
  0  1 -1  3    0  2  2  0

These two patterns were found by pressing one button on the top row, and then using light chasing (allowing negative moves) to make the top three rows zero and see what the effect is on the bottom row. Linear combinations of these were then constructed to make them change only two of the bottom row numbers.

No doubt smaller solutions are possible. I started out using too few moves on the top row, and kept running into problems of duplicate primes, or negative numbers of moves. I then used a fairly large number of top row moves and hit upon this solution.

$\endgroup$
4
  • 2
    $\begingroup$ Brilliant work! If you want an extra challenge, try finding a solution where all primes are less than 70. $\endgroup$ Aug 3, 2022 at 14:46
  • $\begingroup$ absolutely amazing. $\endgroup$
    – JLee
    Aug 3, 2022 at 15:41
  • 2
    $\begingroup$ This looked like an answer of the form 'I wrote a computer program and this is the solution' but you actually provided a strategy and a solution that can be found with pen and paper. Well done. $\endgroup$
    – quarague
    Aug 4, 2022 at 8:55
  • $\begingroup$ @quarague I didn't write a program, but I used an Excel spreadsheet to help me with this by calculating the result boards from the moves I entered. The numbers in my post were basically copy/pasted directly from the spreadsheet. $\endgroup$ Aug 4, 2022 at 11:12
16
$\begingroup$

Via integer linear programming, the minimum number of moves turns out to be:

98

    Moves        Result
    2  8  9  4   11 23 43 13
    1  4 22  0    7 37 59 31
    0  2 24  5    3 47 53 29
    0 17  0  0   17 19 41  5

This same solution minimizes the largest prime.


By request, here's the SAS code I used:

proc optmodel;
   /* declare parameters */
   num n = 4;
   set ROWS = 1..n;
   set COLS = ROWS;
   set CELLS = ROWS cross COLS;
   set NEIGHBORHOOD {<i,j> in CELLS} = {<i2,j2> in CELLS: abs(i-i2) + abs(j-j2) <= 1};

   /* construct primes */
   num maxprime = 200;
   set COMPOSITES = union {i in 3..sqrt(maxprime) by 2} i*i..maxprime by 2*i;
   set PRIMES = {2} union (3..maxprime by 2 diff COMPOSITES);
   put PRIMES=;

   /* declare decision variables */
   var NumMoves {CELLS} >= 0 integer;
   var IsCellPrime {CELLS, PRIMES} binary;

   /* declare objective */
   min TotalNumMoves = sum {<i,j> in CELLS} NumMoves[i,j];

   /* declare constraints */
   con OnePrimePerCell {<i,j> in CELLS}:
      sum {p in PRIMES} IsCellPrime[i,j,p] = 1;
   con AtMostOneCellPerPrime {p in PRIMES}:
      sum {<i,j> in CELLS} IsCellPrime[i,j,p] <= 1;
   con Link {<i,j> in CELLS}:
      sum {<i2,j2> in NEIGHBORHOOD[i,j]} NumMoves[i2,j2] 
    = sum {p in PRIMES} p * IsCellPrime[i,j,p];

   /* call MILP solver */
   solve;

   /* print solution */
   print NumMoves;
   num sol {CELLS};
   for {<i,j> in CELLS} do;
      for {p in PRIMES: IsCellPrime[i,j,p].sol > 0.5} do;
         sol[i,j] = p;
         leave;
      end;
   end;
   print sol;
quit;
$\endgroup$
3
  • $\begingroup$ Nice work. Does minimal number of moves necessarily minimize the largest prime? $\endgroup$ Aug 4, 2022 at 3:04
  • 2
    $\begingroup$ Thanks! No, but this solution happens to be optimal for both objectives. $\endgroup$
    – RobPratt
    Aug 4, 2022 at 3:12
  • 1
    $\begingroup$ Can you share the code you used? $\endgroup$
    – pajonk
    Aug 4, 2022 at 6:28
10
+100
$\begingroup$

Here is my solution without doing any computation.

The following moves produce an "all-one" result:

 Moves          Result
 0 1 0 0        1 1 1 1
 0 0 0 1        1 1 1 1
 1 0 0 0        1 1 1 1
 0 0 1 0        1 1 1 1

The following moves produce an "all-different" result:

 Moves                  Result
 2^0  2^1  2^2  2^3     d_0  d_1  d_2  d_3
 2^4  2^5  2^6  2^7     d_4  d_5  d_6  d_7
 2^8  2^9  2^10 2^11    d_8  d_9  d_10 d_11
 2^12 2^13 2^14 2^15    d_12 d_13 d_14 d_15

The numbers $d_0, \dots, d_{15}$ are clearly all different, because of the binary number system.

Taking a positive linear combination of the previous two sets of moves, we can make the results of the form $a + md_0, a + md_1, \dots, a + md_{15}$ for any positive integers $a, m$.
Now we choose $a, m$ such that $a, a + m, \dots, a + md$ are all prime numbers, where $d = \max\{d_0, \dots, d_{15}\}$. The existence of such $a, m$ is guaranteed by the Green-Tao theorem.
Consequently, all the $a + md_i$ are distinct prime numbers.

$\endgroup$
7
  • $\begingroup$ This is a very nice generalisation. It means we can find solutions for a grid of any size. $\endgroup$ Aug 3, 2022 at 23:40
  • $\begingroup$ @DmitryKamenetsky I don't think that's true. This answer requires a set of moves which produce 1 on all cells. Such a move does not exist for any grid. E.g. a 2x3 grid cannot be filled with all 1s. $\endgroup$
    – Falco
    Aug 5, 2022 at 8:47
  • 1
    $\begingroup$ I especially like this answer, because it found the solution (16) without actually searching for any specific primes. $\endgroup$
    – Falco
    Aug 5, 2022 at 8:48
  • 1
    $\begingroup$ @Falco A $2\times 3$ grid can be filled with all-one by making moves in two opposite corners. With small modification, this method also works if one can produce an "all-equal" result, which is equivalent to saying that the "all-one" vector lies in the $\Bbb Q$-vector space generated by the basis vectors. I have checked every rectangular grid up to $20\times 20$ that this is always true. Perhaps there is a general argument to prove that. $\endgroup$
    – WhatsUp
    Aug 5, 2022 at 14:56
  • 1
    $\begingroup$ @WhatsUp, I think that argument requires negative moves? But that's fine, just crank up the binary representation grid with more moves. $\endgroup$ Aug 5, 2022 at 16:00
6
$\begingroup$

Here is a solution with 12 primes. Cells with brackets have to be pressed as often as their number indicates. Other cells will not be pressed. Note that cells have to be pressed in a checkerboard pattern. Dotted cells contain even, non-prime numbers. I used a small program to find primes that are sums of three other primes.

 [ 3]  31  [23] ....
  37  [ 5] .... [19]
 [29] .... [13]  43
 .... [17]  41  [11]
 

With the idea of JLee, we can upgrade this to 13 primes:

  [ 3]  31  [23] ....
  .... [ 5] .... [29]
  [ 2]  37  [13]  53
   19  [17]  41  [11]
 

$\endgroup$
2
  • 1
    $\begingroup$ @JLee thanks for the idea! it worked, indeed. $\endgroup$
    – daw
    Aug 3, 2022 at 12:52
  • 1
    $\begingroup$ This is a great solution. Just letting you know that it is possible to do better... $\endgroup$ Aug 3, 2022 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.