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?
-
$\begingroup$ (off topic) Have you done any coding for solving 'ball sort' puzzles? $\endgroup$– Daniel MathiasAug 8, 2022 at 21:47
-
$\begingroup$ @DanielMathias no, but it sounds like an interesting thing to try. $\endgroup$– Dmitry KamenetskyAug 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$– Daniel MathiasAug 9, 2022 at 23:34
4 Answers
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.
-
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
-
-
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$– quaragueAug 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
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;
-
$\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$– RobPrattAug 4, 2022 at 3:12
-
1
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.
-
$\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$– FalcoAug 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$– FalcoAug 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$– WhatsUpAug 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
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]
-
1
-
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