[Edu-sig] casino math (unit three) (Saturday night fever)

[Gregor Lingl]

Laura Creighton schrieb:
> In a message of Wed, 02 Sep 2009 03:29:36 +0200, Gregor Lingl writes:
>   
>> Laura Creighton schrieb:
>>     
>>>
>>> I think that the pysol game 'Pile On' is always solvable.
>>> Anybody know for sure?  Writing a program that exhaustively creates
>>> all the possible layouts and then solves them seems possible, 
>>>       
...
> But then, I wasn't really looking for the brute-force proof, but the
> elegant one.  I was hoping for an induction proof for 4 sets of 4
> cards, n cards, and n + 1 cards, but so far I haven't managed it.
>   
Hi all,

1) this approach reminds me of Paul Halmos' saying:

Computers are important, but not to mathematics.

2) If this is considered to be true - or at least to be reflecting some 
essential
features of mathematics, I'd understand why the problem is not dicussed more
deeply on this list. On the other hand this is a real life *casino math* 
problem,
at least for solitaire lovers.

What would your answer or advice be if some of your students asked you
how to treat this problem?

3) I, for my part, felt uneasy with the fact, that the problem was set,  
but not treated at all.
In a previous posting I had supposed, that Laura's proposition might be 
false.
I consider it very unsatisfying to have a proposition, which to treat 
seems not
to be far beyond my abilities and not to know the *truth*

My approach was like this:

I  wrote a little backtracking script that solves Pile On configurations 
and I
found some unsolvable ones. But I did (and do) not know if the script is 
correct -
which means, that I do not have a proof of its correctness. But I used it to
create a small collection of unsolvable  Pile On layouts, wrote some 
tiny utilities
and tried to find some patterns in the unsolvable configurations.

Finally I created a configuration by hand - wou will immediately see 
below that
this is not a random configuration - and I think I have a proof of its 
unsolvability.

Configuration:

      (   (11,  6,  2,  1),
          (11, 10,  4,  1),
          ( 9,  2,  6,  3),
          ( 9,  4,  8,  3),
          ( 7, 12, 10,  5),
          ( 7, 12,  2,  5),
          ( 5,  8,  4,  7),
          ( 5,  6, 12,  7),
          ( 3, 10,  8,  9),
          ( 3,  2,  6,  9),
          ( 1,  4, 10, 11),
          ( 1,  8, 12, 11),
          (13, 13, 13, 13),
          (),
          ()    )

Proof (sketchy):

The investigation of the game-tree takes advantage of the symmetries of 
the configuration.
Odd ranks occur only in the first and the last place of a pile.

You can start to fill the two empty piles essentially in two ways:

(1) - Put two cards with equal odd ranks on pile 14  (e. g.: 1, 1)
    - put one of the freed cards with even ranks on pile 15  (e. g.: 2)
      Now pile 14 is locked and the also the piles you have taken the 
odd cards from. (in my example piles 1 + 2) 
      These now have even topmost cards ( 6 and 4) but those also do not 
match,
      because the four even ranked cards belonging to those piles have 
different ranks.

(2) - Put two cards with equal odd ranks on pile 14  (e. g.: 3, 3)
    - Put two more cards with equal odd ranks on pile 15  (e. g.: 11, 11)
    - Now you have freed four even ranked  cards. If these are pairwise 
different, you are done:
      everything is blocked, that means no solution on this path.
    Remark: there are only 15 pairs of pile-pairs like ((3,3), (11,11))

(3) Now you have to investigate those situations, that arise from doing 
the (2)-procedure but
    do not result in four different even cards on top of the piles. 
These belong to the following pairs
    of piles (named after their topmost odd rank):

    (1,5), (1,7), (3,9), (5,11), (7, 11)

    Most of them can be completed very quickly similar to (1,5) as example:

    11, 6, 2
    11,10, 4
    ..
     7,12,10
     7,12, 2

    by putting one of the twos on top of the other and everything is 
blocked again.

    Only one sitiatuaton leads to a branch which has a few more 
branching steps: (5, 11)

    7, 12, 10
    7, 12,  2
    ...
    1, 4, 10
    1, 8, 12

    Putting first 10 on second one and first 12 upon last 12 frees 7. 
Now for the first
    and only time you can use two more piles with 7 as topmost cards but 
that also blocks
    immediately.

    This is the only case, which uses one of the odd ranked cards in the 
first column.

Should I now consider the problem as solved? I tend to:

   
Proposition: ...

             pysol game 'Pile On' is *not* always solvable.


Of course I might have overlooked something and my proof is incomplete. I'd be very
glad to have someone checked it. Moreover there might be configurations, that have
an even smaller game tree.

...

Are you convinced now, that the proposition ist true?
Or do you know that it is false?
Perhaps you don't care if its true or false?

Can you do something with this as a teacher of mathematics?
Or as a teacher of computer science?
And what if you were an employee of a casino company?

Regards,
Gregor

P.S.: Analysis of solitaire games seems to be not an easy task in general,
despite of the fact that Laura might be right that Pile On is a particularly 
simple variant.

See, for instance:
http://www.stanford.edu/~xyan/papers/solitaire.pdf



>> Thanks for the deverting hint
>> Gregor
>>     
>
> You are most welcome. :-)
>
> Laura
>
>
>