4
$\begingroup$

Here is a 5x4 rectangular wordsearch (area 20) containing the primes between 1 and 100,
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
(numbers in any direction or diagonal/backwards, overlaps permitted (17 = 7,17,71))

15414
29763
38310
05100

It has a score of "4" because we were able to pack 4 unused zeros in there.

We can't make a 3x3 wordsearch as there are too many digits due to the '11';
in theory, the highest score we can get is "2" with a 3x4 wordsearch (area 12):

112
345
678
900
But this is missing primes like "23", so is invalid.

Without using a computer:
What is the minimum possible area for a valid rectangular wordsearch?
For a wordsearch with that area, what is the highest possible score you can find?
Provide an example.

Proof of optimality would be a bonus, by hand (preferred) or computer (acceptable), but I don't know if a proof beyond brute force exists, so am less concerned with that, although it would be interesting.

$\endgroup$

1 Answer 1

4
$\begingroup$

    258
    393
    174
    610
 

Proof of optimality:

Note that there is only one redundant digit. We'll show by contradiction that there is no arrangement without redundant digits. Otherwise, since 2,5,7,8 all have to pair with 3 and 9, 3 and 9 must be sandwiched between the 4 others. But 1 also has to pair with 3 and 9 and with itself which at this point is impossible with only two 1s.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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