Author |
Topic: UVWXYZ (Read 1326 times) |
|
wowbagger
Uberpuzzler
 
Gender: 
Posts: 727
|
Yes, Alice can always win!
First of all, the only reasonable choices for the last digit are Z = 1, 3, 7, 9. So Alice should use three of these digits to press Bob to use the remaining one.
As it turns out, there exists one pattern U_W_YZ with U, W, Y, Z \in {1, 3, 7, 9} that leaves over exactly one prime p matching this pattern. This means that Bob has no choice regarding his digits - if he allows this pattern to emerge (I'll cover that point below).
If Bob chooses V or X different from the corresponding digits in p, Alice will win by choosing her digits according to p. If on the other hand Bob chooses V and X according to p, Alice will be able to win by making Y any valid digit different from the fifth digit of p.
This is true because there is only one (6-digit) prime starting with the first four digits of p.
Now, what happens if Bob tries to disallow the pattern by choosing one of the unused digits in {1, 3, 7, 9} at the second or fourth place? If Alice then uses the other three as her digits, there's only even digits and 5 left, so UVWXYZ can't be prime and Alice wins.
Is there an elegant solution to this? I tried to make use of divisibility rules for a while, but it didn't get me anywhere.
|
|
 IP Logged |
"You're a jerk, <your surname>!"
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
 |
Re: UVWXYZ
« Reply #1 on: Oct 8th, 2002, 9:23pm » |
 Quote  Modify
|
Alice also wins the variant where digits can be repeated. (I worked on that variant because I didn't read the problem carefully and didn't notice that rule!)
I don't have an elegant solution for the variant either; I did it by brute force. Brute force would be easy with a computer (a million nodes is a tiny search space compared with what computer chess programs routinely search), so I did it by hand with a table of prime numbers instead. My table, from an old copy of the Handbook of Mathematical Functions, only goes up to 99999, so I was only able to consider strategies where Alice starts out by choosing 0. The first thing I tried after that was to assume that her second choice is always 9. This required me to search all 100 blocks of primes of the form a9b__, to see if there was a number that could be filled in the tens place such that no value in the ones place would yield a prime. A few minutes of running my finger down the columns showed that this works.
I wonder if the stated problem is harder, in the sense of constraining Alice more in what strategy she must choose. It was certainly easy to find a strategy in the variant.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: UVWXYZ
« Reply #2 on: Oct 8th, 2002, 9:31pm » |
Quote Modify
|
p.s. I've also checked wowbagger's answer to the stated problem, using more modern tools: /usr/games/primes, awk (to fill out the primes with leading 0's), and grep.
This pretty quickly led me to p = 721439 as the only prime whose digits match the pattern 7_1_39, where the _'s must not be 1, 3, 7, or 9. There is no prime without repeated digits that matches 72149_, so the solution works. Nice.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: UVWXYZ
« Reply #3 on: Oct 11th, 2002, 4:22pm » |
Quote Modify
|
Tim,
I don't understand what you are saying about the stated problem possibly being harder than the variant -- it seems that it is much easier to me! I guess I understand that it could potentially be more difficult because of the restriction to her choice, but it is so lax (relatively) that it hardly makes things much more difficult.
The funny thing is that I also misread the problem like you, and tried the other way a bit, but purely number theoretically. I also suspected it was true, but eventually convinced myself that there was no elementary pf (i.e. wo simply using a computer, which is something that would make the problem uninteresting to me). I guess you have now proven that fact, thanks. 
In the meantime, here's my soln for the problem as stated. With all due respect to wowbagger (whose soln is certainly valid!), I believe the problem is intended to be solved wo a prime lookup table.
Start with 9_3_. The goal will be to make U+V+W+X+Y = 2 (mod 3). If Bob fills in the first two gaps with both of 0 and 6, then add a 2, e.g. 90362_. When Bob adds a 1 or 7 the result will be divisible by 3. If Bob leaves one of 0 and 6 available, then he can take at most two out of the three choices for either the 1 (mod 3) or 2 (mod 3) series. Therefore, we have at least one choice available for Y in all of the three series 0, 1, or 2 (mod 3). Choose Y so that again U+V+W+X+Y = 2 and Bob is left with the same choice.
Q.E.D.
Nifty, eh? 
Best,
Eric
|
| « Last Edit: Oct 11th, 2002, 4:23pm by Eric Yeh » |
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: UVWXYZ
« Reply #4 on: Oct 11th, 2002, 10:08pm » |
Quote Modify
|
"Harder" might be a poor choice of term there, but I did try to define what I meant. Count the strategies that work for the stated problem, and count the strategies that work for the variant. I had the impression that there must a lot more for the variant, just because it was so easy for me to find one, so in that sense the variant is "easier" -- if your method of solution is to randomly make up a strategy and check whether it works, you'll solve the variant faster than the original. This of course has no connection to how difficult an actual human being with an actual brain would find the two problems!
Maybe I'm even wrong about this; maybe there are a lot of alternative strategies that work for the stated problem, besides the nice ones you guys found...?
Anyway, your solution is definitely nifty!
|
| « Last Edit: Oct 11th, 2002, 10:09pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: UVWXYZ
« Reply #5 on: Oct 12th, 2002, 1:06pm » |
Quote Modify
|
Tim,
I see -- that makes sense. I'll bet there're quite a few on the restricted version, too, if you use a computer (no need to use only 1379, for example), but as I mentioned I haven't run any simulations for this one.
Best,
Eric
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
continuum
Newbie
Gender:
Posts: 14
|
|
Re: UVWXYZ
« Reply #6 on: Oct 12th, 2002, 7:32pm » |
Quote Modify
|
Eric, very nifty solution! (The same I got  )
By the way, I love congruence classes... They are really useful in solving number theory problems...
|
|
IP Logged |
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: UVWXYZ
« Reply #7 on: Oct 12th, 2002, 10:45pm » |
Quote Modify
|
Thanks, and good job to you, too. 
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
 |
Re: UVWXYZ
« Reply #8 on: Oct 14th, 2002, 5:34am » |
Quote Modify
|
Neatly done indeed!
|
|
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
Eric Yeh
Senior Riddler
Gender:
Posts: 318
|
|
Re: UVWXYZ
« Reply #9 on: Oct 14th, 2002, 6:52am » |
Quote Modify
|
Thanks!
|
|
IP Logged |
"It is better to have puzzled and failed than never to have puzzled at all."
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print