Alice and Bob play a game. Starting with Alice, they alternate in selecting digits for a 6-digit decimal number UVWXYZ that they construct from left to right. Alice chooses U, then Bob chooses V, then Alice chooses W, and so on. No digit can be repeated. Alice wins if UVWXYZ is not a prime. Can Alice always win?

I thought I might have seen something in Ady's idea, but can't get it to pan out.  But here's what I have worked out:

Let's call the stage at UVWX the century.

 10   for Cent=1000 to 9999
 20    Founddec=0
 30    for Decd=10*Cent to 10*Cent+9
 40      Good=1
 50      for U=10*Decd to 10*Decd+9
 60        if prmdiv(U)=0 then stop
 70        if prmdiv(U)=U then Good=0
 80      next
 90      if Good then Founddec=1
100    next
110    if Founddec=0 then print Cent
120   next

finds that the only centuries that lack having some decade (UVWXY) with no primes are:

1122
1158
1416
1794
2101
2891
2962
3213
3676
4072
6838
7211
7277
8622
9616
9903

So if Alice starts with U=5, every century that could happen would have some decade (which Alice gets to choose in her turn for Y) which lacks any primes. In fact, even if Alice chose some other digit for U, there'd always be some W she could choose to assure that all centuries that Bob could present with his X would have some no-prime decade.

But for simplicity in Alice's strategy, lets assume that she always chooses 5 for U and 1 for W. Let's see how her choice of Y would depend on Bob's choices of V and X:

 10   for Cent=5000 to 5999
 15    if (Cent\10)@10=1 then
 20    :Founddec=0:print Cent;
 30    :for Decd=10*Cent to 10*Cent+9
 40      :Good=1
 50      :for U=10*Decd to 10*Decd+9
 60        :if prmdiv(U)=0 then stop:endif
 70        :if prmdiv(U)=U then Good=0:endif
 80      :next
 90      :if Good then print Decd;:endif
100    :next
110    :print
120   next

finds the decades that work for the various V and X that Bob might choose:

Winning UVWXY for each possible UVWX when U=5 and X=1:

UVWX  --------Alice's Choices for UVWXY------------------
5010  50105  50106  50109
5011  50111  50114  50116
5012  50124  50126
5013  50130  50132  50133  50135  50137  50139
5014  50143  50144  50147  50148
5015  50152  50153  50154  50155  50158
5016  50164  50166  50167  50168
5017  50172  50174  50175  50178  50179
5018  50183  50185  50187  50189
5019  50190  50192  50198
5110  51102  51104  51107  51109
5111  51113  51114  51118
5112  51125
5113  51130  51131  51134  51137
5114  51142  51149
5115  51153  51156
5116  51161  51164  51165  51167  51168
5117  51173  51174  51176  51177
5118  51182  51188
5119  51191  51192  51194  51195  51197  51198
5210  52101  52107  52108  52109
5211  52112  52114  52118  52119
5212  52121  52122  52127
5213  52133  52134  52138
5214  52141  52143  52145  52146
5215  52154  52157  52159
5216  52161  52162  52163  52168
5217  52171  52173
5218  52182  52184  52185
5219  52191  52193  52194  52195  52196  52197
5310  53100  53103  53105  53106  53108  53109
5311  53111  53115  53118
5312  53121  53124  53127
5313  53130  53131  53132  53136  53137  53139
5314  53140  53141  53142  53143  53144  53146  53147
5315  53150  53151  53153  53159
5316  53160  53164  53165  53169
5317  53171  53172  53174  53175  53176  53177  53178
5318  53180  53181  53188  53189
5319  53192  53193  53194  53195  53196
5410  54101  54103  54105  54107
5411  54110  54111  54116  54117
5412  54122  54125  54129
5413  54131  54132  54135  54137
5414  54140  54142  54145  54147  54149
5415  54155  54156  54159
5416  54160  54162  54164  54167  54168
5417  54170  54173  54174
5418  54180  54182  54184  54186  54187  54189
5419  54191  54193  54194  54197
5510  55104  55107  55108
5511  55113  55115  55116  55118
5512  55122  55124  55125  55127
5513  55130  55135  55137  55139
5514  55141  55143  55145  55147  55149
5515  55152  55157
5516  55160  55161  55162  55163  55164  55166
5517  55170  55178  55179
5518  55182  55183  55185  55187  55188  55189
5519  55194  55197  55199
5610  56100  56102  56103
5611  56111  56112  56113  56114  56115
5612  56120  56121  56123  56124  56126  56128  56129
5613  56132  56133  56139
5614  56142  56144  56145  56147  56148  56149
5615  56150  56151  56153  56154  56156  56157  56158
5616  56161  56162  56163  56164  56165  56167  56168  56169
5617  56172  56174  56175  56177
5618  56181  56184  56185  56186  56187  56188  56189
5619  56195
5710  57102  57105  57107  57108
5711  57110  57112  57117  57118
5712  57124  57125  57128  57129
5713  57131  57134  57135  57137
5714  57141  57142  57144  57146  57148  57149
5715  57150  57151  57152  57155  57156  57159
5716  57161  57162  57164  57166  57168
5717  57173  57176
5718  57182  57183  57188  57189
5719  57191  57192  57194  57195  57198  57199
5810  58100  58101  58103  58105
5811  58111  58112  58115  58116
5812  58121  58124  58125  58127  58128
5813  58138
5814  58143  58146  58148
5815  58150  58151  58153  58156  58158
5816  58160  58162  58164  58167
5817  58171  58178
5818  58181  58183  58188
5819  58191  58193  58196  58197  58199
5910  59100  59101  59103  59104
5911  59110  59114  59115  59117
5912  59120  59121  59122  59124  59126  59129
5913  59132  59133  59135  59136  59138
5914  59141  59147  59148
5915  59151  59153  59154  59156  59157
5916  59163  59166  59168
5917  59171  59172  59176  59178
5918  59180  59181  59183  59185  59187
5919  59191  59192  59194  59196  59198  59199

Unfortunately there's no one Y value that serves all. For example, if UVWX is 5619, then Y must be 5, but if UVWX is 5813, then Y must be 8. Most UVWX have more than one choice; 5616 has the most, eight: any digit except zero or 6.

Posted by Charlie on 2013-05-27 17:27:28