Problems & Puzzles: Puzzles

Puzzle 966. Update Puzzle 353. Here we ask for the unsolved cases for the Puzzle 353 posed time ago by Anurag Sahay. "Arrange the first n2 primes in a n by n matrix such that every two adjacent primes should not have any digit in common." From the contributions to Puzzle 353, this is the status for 3<=n<=22 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, ... Solved in blue: 3, 4, 5, 10, 11 & 14 Impossible in red: 6, 7, 8, 15-22 Unsolved in black: 9, 12 & 13 Q. Send your solutions for these unsolved cases (n = 9, 12 & 13) or show that these solutions are impossible. Solutions already gotten: n= 3 and n=5 by Anurag 23 19   3   11  5  17   7 13   2 and 97 43  67   3 41  31  7  89  17 53  47 61 73   2  79  59 23 19   5 13  37 11 83  71 29 n=4 by Fred Schneider 3 41 37 11  7 23 19 53  13 5 43 2  47 31 29 17 n=10, 11 and 14 , by Jon Wharf 173 449 31 457 139 487 313 67 499 151  59 317 229 13 467 193 227 509 271 349  137 409 311 257 331 277 53 17 439 157  269 113 479 103 79 5 281 43 71 239  131 89 163 97 463 179 433 101 293 167  29 431 7 23 197 283 61 383 107 359  47 2 83 19 223 41 353 241 389 127  191 73 149 367 11 263 401 397 251 443  523 419 337 109 373 181 233 541 379 521  491 307 199 347 211 503 461 37 421 3 and 317 659 173 409 17 283 179 23 61 379 641  269 137 89 71 263 197 223 571 389 461 397  431 229 113 499 107 233 167 349 617 239 41  509 313 449 127 443 157 439 281 593 11 523  31 577 331 599 601 383 271 359 67 29 181  557 631 487 661 479 5 433 607 293 541 2  613 277 103 47 251 463 97 43 151 73 569  457 163 547 619 347 199 643 79 3 59 337  13 257 131 587 191 653 19 563 211 373 521  467 139 227 109 83 419 53 421 503 149 37  193 647 311 7 101 367 491 307 241 353 401      and 137 659 317 509 617 239 761 359 107 653 701 863 271 983  829 173 269 13 809 167 293 1117 593 1087 643 127 389 157  113 859 313 569 17 349 1171 953 1187 563 71 883 571 839  929 131 47 1123 409 281 439 881 463 811 263 1051 233 751  1013 967 103 67 211 503 821 433 181 599 101 887 1151 443  769 1031 947 31 677 241 353 1181 59 2 499 251 397 151  1033 797 1103 997 421 683 401 29 7 449 1021 739 521 937  79 613 977 431 757 41 277 461 229 5 89 61 379 601  1063 97 631 907 11 283 641 877 541 727 661 347 1061 743  479 163 709 331 857 199 577 1129 37 941 827 619 733 1069  1163 547 311 607 19 823 491 373 419 307 691 557 919 383  487 1193 647 1153 467 109 367 149 673 191 83 911 3 1097  193 457 139 787 1109 853 1009 773 1049 223 719 53 179 43  227 1093 257 1039 587 1091 73 1019 337 991 523 971 23 197

---

Contributions came from Dmitry Kamenetsky, Michael Hürter, Paul Cleary and Oscar Volpatti

***

Dmitry wrote on Aug 17, 2019:

N=12 and N=13 exist! I don't think N=9 exists, but I cannot prove it. Here they are:

 

N=12
41 257 139 677 389 71 683 571 439 107 823 719 
653 19 587 131 277 349 751 293 761 53 179 233 
149 83 61 727 419 787 239 157 433 127 353 167 
367 401 73 601 383 2 617 443 271 503 197 283 
449 523 199 773 569 173 89 701 593 241 3 461 
31 409 263 509 181 269 347 599 821 373 421 379 
607 113 47 311 467 313 5 317 659 11 397 101 
359 7 23 769 331 67 431 59 103 229 151 739 
211 643 557 13 227 491 577 631 827 613 79 521 
37 811 43 97 661 733 109 457 619 547 163 479 
499 673 29 541 337 191 647 193 757 281 797 563 
137 809 641 307 691 743 251 487 223 709 463 17 

N=13
401 653 179 463 859 613 829 631 227 19 283 971 383 
569 811 53 229 431 827 433 887 419 37 619 83 421 
173 499 787 43 709 313 257 491 773 2 73 521 967 
269 337 641 599 13 727 691 373 659 317 5 797 113 
857 991 587 163 977 181 233 449 131 809 761 23 769 
439 67 149 757 101 937 881 367 409 137 929 577 311 
271 359 277 331 79 211 347 109 733 29 487 103 947 
953 167 389 647 251 673 199 563 919 47 31 997 883 
17 503 241 89 743 1009 353 719 853 601 479 263 71 
509 661 379 41 59 443 197 523 61 547 281 457 983 
821 397 541 907 863 571 643 911 307 11 557 193 677 
739 461 7 3 701 349 157 823 941 877 139 607 239 
151 97 683 127 593 107 839 751 223 191 467 293 617

***

Michael wrote on Aug 18, 2019:

I found the following solutions:

For n = 12:

 

541 739 41 359 71 389 701 659 401 673 811 349
73 61 23 17 439 127 563 211 367 191 337 251
461 233 179 463 271 683 149 773 419 257 619 733
239 571 43 109 643 719 523 199 3 19 307 11
751 293 617 823 197 83 647 383 151 347 521 379
263 487 509 467 283 677 353 491 37 821 397 181
587 193 7 139 557 113 607 5 29 373 281 547
601 757 101 47 613 599 331 479 131 499 67 223
227 431 827 631 97 241 769 31 409 317 89 641
691 277 313 709 421 79 433 59 311 809 167 593
727 653 797 163 577 13 229 743 269 157 443 107
503 787 103 457 661 449 173 569 137 2 761 53

 

For n = 13:

 

29 751 499 113 569 223 59 337 149 887 613 509 137
587 929 173 5 347 19 373 919 257 311 229 317 599
941 883 449 37 1009 773 691 877 631 479 13 859 463
233 197 853 419 827 619 227 193 727 131 659 23 557
191 433 199 307 461 733 911 547 331 757 41 97 103
563 719 43 991 283 101 73 269 457 163 857 3 79
809 523 179 53 409 577 641 7 109 787 431 977 503
643 971 2 491 653 241 379 881 277 139 67 31 487
157 823 907 263 47 593 661 743 811 467 251 947 313
839 617 443 107 953 607 353 601 397 181 709 151 769
761 239 701 983 271 389 647 359 281 367 541 739 211
89 17 349 571 383 167 829 11 967 521 937 821 997
127 83 61 293 677 439 71 863 421 673 401 797 683

 

***

Paul wrote on Aug 19, 2019:

For n=12 and 13 here are my solutions.

 

599	673	811	379	601	757	199	43	661	449	613	89
773	151	739	251	349	211	373	821	743	181	727	631
641	293	41	389	71	53	419	367	109	677	503	787
397	61	223	751	643	197	523	19	487	139	47	13
421	359	617	83	127	563	11	457	193	827	103	479
509	761	593	271	3	241	587	313	557	163	797	311
263	409	7	383	691	733	491	577	331	709	653	79
541	2	443	5	337	149	277	431	769	823	179	283
683	17	269	317	659	37	191	67	433	719	23	157
401	569	137	499	173	59	467	113	607	353	701	439
257	31	809	167	229	73	281	647	131	97	463	571
619	227	461	29	307	521	347	101	547	233	107	239

 

 

And

 

 

379	641	397	421	733	659	137	829	743	991	283	157	439
461	983	521	937	811	773	449	53	1009	587	41	83	727
389	127	43	181	67	109	353	691	337	919	233	107	593
71	563	997	523	149	277	619	307	541	367	599	443	167
383	971	23	941	673	881	347	191	827	401	227	101	839
11	823	17	223	199	757	911	73	419	557	311	257	61
883	761	5	179	503	229	467	281	607	193	677	139	877
751	433	7	643	719	653	19	37	59	787	359	647	293
263	79	103	977	463	197	863	491	887	953	617	509	47
947	251	97	241	797	853	701	683	409	211	349	271	569
31	907	151	769	13	269	3	709	821	739	601	859	317
487	331	967	431	809	571	29	631	577	661	457	613	2
239	857	131	89	373	499	113	547	163	479	313	929	173

 

***

Oscar wrote on August 23, 2019

I solved the cases n = 12 and n = 13; the case n = 9 is impossible.

 

Solution for n = 12:

 

  107  349  127  463  227  139  257  313    2  179  263  479
  439  157  643  751  443  277  163  557  149  653  197  563
  271  449  571   43  709   13  457  193  577  419  683  719
  499  701  433   29   31  727  331  487  613  587  491   23
  821    3  109   37   59  113  757  631  547   19  607  191
  367  541  733  101   73   89  131  787   61  307  199   53
  521  673  241  379  151  337  229  311  827   11   83  619
  773  811  397  401  739  181  373  509  661  223  691  353
  809  347  251  769  421   67  211  677  599   17  503   41
  431  269   47  281   79  103    7  233   71  593  167  293
  569  173  659  743  601   97  283  467  523  617  359  461
  317  409  137    5  797  383  647  823  761  389  641  239
 

Solution for n = 13:

  107  349  127  463  227  139  257   61  503  179  653  479  263
  439  157  643  907  313  277  163  557  149  523  197  563  947
  271  449  571   43  709   13  457  193  577  419  863  719  683
  499  701  433   29   31  727  661  487  613  587  491  823  971
  751    3  109   37   59  113  757  631  547  991  827  941   23
  443 1009  733  101   73   89  131  787  691  887   19  307  191
  601  773  241  379  151  337  229  311  877  331  607  199   53
    5  811  397  401  739  181  373  509   11  857  911   83  619
  809  367  251  769  421  797  211    7  883  919  223   47  353
  317  829  673  281  937  541  967  821  977  853   17  839   41
  269  347  859  677  521   79  881  997  233   71  593  167  293
  173  569  743  929   67  103   97  283  467  953  617  359  461
  409  137  659  431  599    2  383  647  983  761  389  641  239
 

I built the 12x12 solution by manual arrangement.
 

I noticed that exactly 50% of the first 144 primes contain at least one rare digit from the set D2 = {0,2,5,8}, and I decided to place such primes on even positions only.

Therefore, I only needed to consider the frequent digits from the sets D0 = {3,6,9} and D1 = {1,4,7}.
 

I filled the matrix as follows:

top left corner: even {1,7}, odd {4,d0',d0"} or {4,d0};

top right corner: even {3,6}, odd {9,d1',d1"} or {d1',d1"};

bottom left corner: even {6,9}, odd {3,d1',d1"} or {d1',d1"};
 

bottom right corner: even {3,9}, odd {6,d1',d1"}, or {d1',d1"};
 

completing main diagonal: even {9};

above main diagonal: even {7} or {4,7}, odd {1,d0',d0"}, or {1,d0};

below main diagonal: even {1} or {1,4}, odd {7,d0',d0"}, or {7,d0};

finally, the remaining positions.

I built the 13x13 solution in the same way, just placing the primes 2 and 5 in odd positions.

 

Impossibility proof for n = 9.

 

In order to detect the bottleneck, consider the following simpler problem:

on a 9x9 board, place 14 pawns in non-adjacent squares in order to minimize the number x of empty squares adjacent to at least one pawn.

 

Solution: x>= 18, and the following configuration is an elegant optimal example (among many others):

 

1 0 1 0 1 0 1 0 1

0 1 0 1 0 1 0 1 0

1 0 1 0 1 0 1 0 1

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0

Going back to the original problem, place the 14 primes containing both 1 and 3 (necessarily, in non-adjacent positions).

The positions adjacent to such primes must be filled by primes not containing neither 1 nor 3.

But there are at least 18 such posiions, and only 16 such primes.

***

---