7
$\begingroup$

Two players, Alice and Bob, take turns in identifying and circling prime numbers in this 8 x 8 board of digits. Primes must be read as continuous string of digits, either horizontally (from left to right) or vertically (from top to bottom). Likewise, they must not overlap, they must all be different, and can be of any number of digits but with no leading zeros. The winner is whichever player moves last.

Which of the two players wins if both play optimally?

It can be shown that in the longest possible game, Alice wins. Who wins when the shortest possible game is played?

enter image description here

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ All the digits must be in the same row or column? Or merely that each must be adjacent to the next digit? $\endgroup$
    – msh210
    Commented Sep 14, 2023 at 3:19
  • $\begingroup$ I find that there are 77 primes here, and there are 157 possible first moves, so any brute-force search must be heavily optimised. By the way, OP you didn't say who moves first. $\endgroup$
    – Benjamin Wang
    Commented Sep 14, 2023 at 14:36
  • $\begingroup$ @BenjaminWang I count 84 one- and two-digit primes, not including two-digit numbers beginning with 0 (e.g. 07, 03), which would add 4 more. I'm sure there are still more three-or-more-digit primes. $\endgroup$
    – GentlePurpleRain
    Commented Sep 14, 2023 at 15:57
  • $\begingroup$ @GentlePurpleRain ahh I meant 77 distinct primes. $\endgroup$
    – Benjamin Wang
    Commented Sep 15, 2023 at 8:38

1 Answer 1

Reset to default
1
$\begingroup$

EDIT: I missed the requirement that primes must be unique. That invalidates this first grid. But the final solution should still be fine.

The longest game I can find comprises 39 moves. This is basically every single-digit prime in the grid, and then as many 2- or 3-digit primes as will fit in the remaining space:

enter image description here

This is far from unique, as many of the unused digits could be combined with adjacent single-digit primes to create new primes, but I don't think there is any way to fit more primes in.

Since Alice wins this game, and there are an odd number of moves, Alice must also start.

The shortest game would have to use as many long primes as possible.

Ideally, if each row (or column) were an 8-digit prime, then it would only be 8 moves. But of course, that is not the case. Significantly, in the bottom-left corner, the ending 5 immediately indicates that the first column cannot be an 8-digit prime, and some checking with a prime number checker demonstrates that the only number on the bottom row that contains that 5 and is prime is either 53 or 5 itself. If we use 5 by itself, the other 7 digits make up a prime number, which is promising.

So we will definitely need to use some significanly smaller numbers.

Continuing with the bottom row, and looking at the fifth column, any number extending down that column can't contain the final 5 or the penultimate 2, as those would immediately make the number composite. So we probably want to try to contain the 2 and the 5 in horizontal numbers (because otherwise they would have to be counted on their own, which wouldn't use up much of the grid).

Some more prime checking shows that the best we can do for the 2 is a 3-digit number (233), but the row above it has an 8-digit prime.

Continuing to try to fill large primes across the rows (and a little juggling of digits here and there) provides the following grid, with 12 moves:

If this is the fewest moves possible, then assuming Alice continues to play first, Bob would be the winner, because 12 is an even number.

enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Great effort, but the rules stipulate all primes must be different - many are repeated in the longest game attempt. $\endgroup$
    – Nuclear Hoagie
    Commented Sep 14, 2023 at 18:59
  • $\begingroup$ @NuclearHoagie Good point. The final solution still has unique primes, though. $\endgroup$
    – GentlePurpleRain
    Commented Sep 14, 2023 at 19:06

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.