Conference rusure::math

    (Presumably you cannot take away more than the number).
    Here's a partial table:
    
    Wins:	2, 5, 7
    Loses:	1, 3, 4, 6, 8, 9, 10, 11, 12, 13, 14
    
    Obviously perfect squares and cubes lose.  As noted in .0, 
    leaving 2 is a winner.  So,
    
     3 loses because opponent can take 1 leaving 2, a win for him,
    10 loses because opponent can take 8 leaving 2, a win for him,
     5 wins  because opponent can only leave 1, 4, 10 -- all losers for him,
     6 loses because opponent can take 4 leaving 2, a win for him,
    14 loses because opponent can take 9 leaving 5, a win for him,
     7 wins  because opponent can only leave 3, 6, 14 -- all losers for him,

    etc.  But except for the obvious special cases I can't figure out
    how to characterize a random integer as a winner or loser.  Odds
    are it's a loser!
    
      John

There are 1976 winners less than 100000, including 0 as a winner.
The first 50 winners are:


0, 2, 5, 7, 17, 19, 22, 24, 37, 39, 50, 57, 63, 70, 76, 87, 89, 94,
104, 109, 115, 133, 135, 148, 154, 159, 165, 172, 177,
200, 205, 211, 217, 222, 224, 237, 243, 250, 257, 267, 274, 287,
315, 327, 333, 353, 356, 377, 403, 409,

I would have thought that socodi winners would be denser than primes,
because they can both be found using sievelike methods and the prime
sieve is "finer" than the socodi sieve - i.e. the set {n*p} is denser
than the set {w+i^2} U {w+i^3}. So much for my intuition.....

BTW, there seem to be only around 38 numbers less than 50000
which only lose because they are 1/2 of a winner - the smallest is 12.

							Richie

A couple comments on the replies so far.

.1: Are you *sure* that 12 is a loser?

.2: Are you *sure* that 24 is a winner?

.1 & .2: Need a number be classifiable either as a winner or a loser?   What
other possibilities are there?

    Re: the questions in .-1
    
    If you leave 12, do you win or lose?

    Your opponent can subtract squares (1,4,9), cubes (1,8), or double
    it; i.e., your opponent can leave 3, 4, 8, 11, or 24.  The first
    four all lose quickly, so your opponent will leave you with 24.
    
    Now, you can subtract a square (1,4,9,16), a cube (1,8), or double
    it.  So you can leave 8, 15, 16, 20, 23, or 48.  Leaving 8, 15,
    16, or 23 lose [for 23, your opponent subtracts 16 leaving 7 and
    wins; you lose] so you must decide between leaving 20 or 48.
    
    If you leave 20, your opponent can subtract 8 and leave 12 to you!
    That was what you left to start this analysis!  So you can cycle
    like this forever.
    
    Now, if you leave 20, and the opponent subtracts the squares 1,4,9,16
    then the opponent loses.  So the opponent will either cycle by
    subtracting 8 and leaving 12, or will double to 40.
    
    If leaving 48 wins, then you will play from 24 to 48 and win, which
    will finally establish that leaving 12 wins.
    
    If leaving 48 loses and leaving 40 wins, then leaving 12 loses,
    because your opponent doubles to 24 and you either lose, or play
    to 20 and [your opponent doubles to 40 and so you] lose, or play
    to 48 and lose.
    
    But if leaving 48 loses and leaving 40 loses, you will play from
    24 to 20 [everything else loses] and your opponent will play from
    20 to 12 [everything else loses] and you both will cycle.
    
    So who wants to study leaving 40 and leaving 48?
    
    Dan
    

Dan is mostly on the right sort of lines (although he's wrong about the
fate of 20).   I thought I'd tabulate here the results for some small
numbers.   (Hope I've got them right!)

 0 W   1 .   2 W   3 .   4 .   5 W   6 .   7 W   8 .   9 .
10 .  11 .  12 ?  13 .  14 .  15 .  16 .  17 W  18 .  19 W
20 .  21 .  22 W  23 .  24 ?  25 .  26 .  27 .  28 .  29 .
30 .  31 .  32 .  33 .  34 .  35 .  36 .  37 ?  38 .  39 ?
40 ?  41 .  42 .  43 .  44 .  45 ?  46 .  47 .  48 ?  49 .
50 W

. stands for Loss.

That makes the ground a bit more solid for those speculating on the fate of
12, 24, 48 etc.

But how are you going to find out the fate of arbitrary n?   The W's seem
to be getting sparser, don't they?

Andrew Buchanan.

    Re .-1, .-2:
    
    Right.  If you leave 20, your opponent doesn't have a choice between
    leaving 12 or 40; subtracting one will leave the winner 19.
    
    I looked at this a little more yesterday.  After A leaves 12, B
    leaves 24 [or else loses], A leaves 48 [or else loses], and there
    is no forced win for A, and there is a forced win for B if and only
    if there is a forced win after leaving 96.  If there isn't, then
    B can "play safe" and the two can cycle.
    
    Is there also the potential to keep doubling forever?
    
    Dan

    Obviously my .1 was wrong about leaving 12.
    
    It occurs to me that the rules need to be updated to prevent the
    game from going on indefinitely.  That way, every number is either
    a Winner or a Loser.
    
    For example, one could add the "rule" that you cannot leave a number
    that has already been "left".  Add another "rule" that limits either
    the number of doubles per player or sets an upper limit on doubling
    somehow.  Together these rules would make 12, etc. all winners,
    since you would make it impossible for your opponent to "flee" to them.
    (Unless 12 * 2^n had been previously played, in which case they
    would become losers; but you can figure that out easily enough).
    
      John

Nice idea for the rules modification.   Let's define:

SCORCHED EARTH SOCODI (SES)

to be like normal SOCODI, except that you can't say a number that's appeared
before in the game.   Let's not define any fiddly rules limiting doubles,
until we see how SES plays: that might get rid of all the draws anyway.

Offhand, I'd say that it's going to make the game more complicated to analyse.
I'm going to think about it.

There still remains the problem of solving the *puzzle*: who wins ordinary 
SOCODI, starting from n.

    Then there is lobotomized SOCODI [square or cube or double it?]
    where one player [the lobotomized one] always doubles.  Given any
    initial "n" can the nonlobotomized player always win?
    
    Dan

>    Then there is lobotomized SOCODI [square or cube or double it?]
>    where one player [the lobotomized one] always doubles.  Given any
>    initial "n" can the nonlobotomized player always win?

The impaired player in LOBOTOMIZED SOCODI is strictly weaker than in SHUCKS
SOCODI, where he still loses.   In SS, one player is nearly normal,
lacking only the killer instinct to win the game by saying 0 at the end.
For all n > 0, the game is a forced win for the other player, who wins in 
a finite time by adopting the following algorithm:

     (a) For any finite time, he does anything he wants.
     (b) He picks the largest reduction he can make (this will be greater
than n/2 except when he reaches 2 or 3.   Iterate on (b) until win or 2 or 3.
     (c) 3 he wins normally.   2 he wins by playing to 4, when ("shucks!") his
opponent plays to 3 or 8.

However: I've been exploring SCORCHED EARTH, which seems sufficiently tough
that I'll explain VANILLA SOCODI, so that we're all on equal terms for the
journey into terra incognita.

See you in the next reply.

Andrew Buchanan.

P.S. I have a suggestion for a new game, called DERAMO.  I don't know what it
is, but I do know that DERAMO is an acronym for the rules.   Any ideas, Dan?

Ordinary SOCODI: the solution.










Press return.










The winning numbers are:

W = {0, 2, 5, 7, 17, 19, 22, 50}   That's all folks.

The losing numbers are those numbers of the form w + s, where:

w is in W
s is in S, the set of positive squares and cubes.

Everything else is a draw.

Why?

0 is a win.
So all numbers s in S lose.
So 2 is a win, since all moves from there lose.
So 2 + S all lose.
Thus we build up each winning number, (and then its associated family of losers)
on the basis of only the numbers we have resolved the fate of before.
We reach a total of eight winners.

Key point: Suppose there are more winners.   One of these, w9 is such that all
possible moves from it are in the set W + S (the set of numbers w + s, w in W,
s in S).

To see this, suppose this were not the case.   I.E. There are more winners, but
non of them have the property stated for w9.   Then from x0, a win for us, our
opponent makes a move that avoids entering W + S, this time round.   We follow
our winning strategy, and play x1, another winning position for us.   But once
again, our opponent can avoid enter the killing zone of W + S.   Indeed our
opponent can up this jig indefinitely, either diverging xi towards infinity,
or cycling.   Contradiction.

Therefore, if there's another winner it satisfies the property of w9 above.
So for all s in S, there exists s' in S, w in W, such that:
   w9 = s + s' + w
(For completeness, it must also be the case that there exists sd in S, wd in W,
such that:
   2*w9 = sd + wd,
but I'm not going to use this).

We'll consider the three values in S: 1, 9 and 25 (the reason for their choice
will become evident in a moment.   It's a sneaky one).

So we can conclude the existence of s'a, s'b and s'c, w'a, w'b and w'c,
such that:
     w9 = 1 +  s'a +  w'a
     w9 = 9 +  s'b +  w'b
     w9 =25 +  s'c +  w'c

Now each of the s'i is *either* a square or a *cube* (possibly both (e.g. 1)).
Therefore in the set {s'a, s'b, and s'c} (this would be much better with
underscores) at least two will be of the same kind (square or cube).   Discard
entirely the equation referring to the third, and subtract the other two from
one another, to get something that looks like this:

     0 = d + (s'i - s'j) + (w'i - w'j).

Now |d| is in D = {8, 16, 24}, since it's the difference of two of {1, 9, 25}
e = |(w'i - w'j)| is the difference of two members of W, i.e. appears in E =

   {0,2,3,5,7,10,11,12,13,14,15,17,19,20,22,28,43,25,48,50}

So (s'i - s'j) = �d �e (Oh, joy, I managed to compose a character).

Since D and E are disjoint (hence the sneaky picking of 1, 9 and 25)
the rhs is non-zero.
the mod of the rhs is <= 50 + 24 = 74.

Key point: the lhs is defined to be either difference of squares, or difference
of cubes.   Two unequal squares, a^2 < b^2 must differ by at least 2*b - 1.   

Thus if s'i and s'j are both squares, one of them, has root(s'i) < (74 - 1)/2.

i.e. w9 <=  36^2 + 50 + 25 = 1371.

This may seem quite a high bound, but it's relatively easy to check even by 
hand that no winner exists in that range.   I'm sure some weenie here has a
program that will eagerly mutate to do the check.   E.g. only need to check
numbers that are one more than some number in W + S.   I allege I did check
by hand once.

One last wrinkle: since we're considering subtracting 25 from our hypothetical
w9, we need to check that no tiny number less than that could do the job.
12 and 24 both double into numbers of unknown fate.   So that's OK.

SCORCHED EARTH SOCODI seems tough indeed compared to this.   I'll report on
my first foray into this wasteland tomorrow.   But before I go, observe that
the decided numbers: W and W+S all have the same fate that they do now.   There
is no access from them to any cycles or infinite doublings (under rational 
play).

At first I thought that SCORCHED EARTH would be prone to incredible doubling
sequences, but I think I may have been premature.   Consider the fate of 24
in SES, if 12 has not appeared in the history, for example.

Goodnight.
Andrew Buchanan.

    I thought Richie Lary settled this a while ago.  I wrote a program
    to duplicate the results in reply .2, and found that it *must* do
    some back-tracking (which I've not yet coded).

    Anyway, the numbers 12 and 24 are fairly simple to determine.

    Assume 24 is a loser.  This implies that 12 is a winner (from 12,
    there is no way to reach a winner).  It also implies that 48 is a
    winner (since doubling 24 is the only way that 24 can be a loser).
    But since 12 is a winner, that makes 48 a loser (48 - 36 = 12).
    Thus, we've reached a contradiction, and so our assumption is false.

    Thus, 24 must be a winner.  Since 24 is a winner, 12 must be a loser,
    and 48 must be a loser.

P.S.
    I find the terminology confusing -- it's backwards from what I'm used to,
    which assigns the win/lose terms to the state at the *beginning* of the
    player's turn.  The idea is to give the next player a losing position.

    Re .-1
    
>>       Assume 24 is a loser. ... and so our assumption is false.
    
>>       Thus, 24 must be a winner.
    
    No; it means that either 24 is a winner, or that 24 is safe to play
    because it leads to cycles or unbounded growth in the numbers.
    
    Dan