wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> UVWXYZ
        
(Message started by: wowbagger on Oct 8^th, 2002, 8:46am)

Title: UVWXYZ
Post by wowbagger on Oct 8^th, 2002, 8:46am

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.

Title: Re: UVWXYZ
Post by TimMann on Oct 8^th, 2002, 9:23pm

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.

Title: Re: UVWXYZ
Post by TimMann on Oct 8^th, 2002, 9:31pm

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.

Title: Re: UVWXYZ
Post by Eric Yeh on Oct 11^th, 2002, 4:22pm

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? 8)

Best,
Eric

Title: Re: UVWXYZ
Post by TimMann on Oct 11^th, 2002, 10:08pm

"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!

Title: Re: UVWXYZ
Post by Eric Yeh on Oct 12^th, 2002, 1:06pm

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

Title: Re: UVWXYZ
Post by continuum on Oct 12^th, 2002, 7:32pm

Eric, very nifty solution! (The same I got ;D)

By the way, I love congruence classes... They are really useful in solving number theory problems...

Title: Re: UVWXYZ
Post by Eric Yeh on Oct 12^th, 2002, 10:45pm

Thanks, and good job to you, too. ;)

Title: Re: UVWXYZ
Post by wowbagger on Oct 14^th, 2002, 5:34am

Neatly done indeed!

Title: Re: UVWXYZ
Post by Eric Yeh on Oct 14^th, 2002, 6:52am

Thanks!