[Edu-sig] casino math (unit three)

[Gregor Lingl]

Laura Creighton schrieb:
> In a message of Wed, 02 Sep 2009 03:29:36 +0200, Gregor Lingl writes:
>   
>> Laura Creighton schrieb:
>>     
>>> In a message of Mon, 31 Aug 2009 22:23:55 PDT, kirby urner writes:
>>>
>>> <snip>
>>>
>>>   
>>>       
>>>> On break, we encourage playing with Pysol maybe...
>>>>
>>>> http://www.pysol.org/
>>>> http://pysolfc.sourceforge.net/
>>>> http://tktable.sourceforge.net/tile/
>>>> http://pygames.sourceforge.net/
>>>>
>>>> Kirby
>>>> 4D
>>>>     
>>>>         
>>> 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, 
>>>       
>
>   
>> Hi Laura,
>> I fear that this is not  practicable.  There are 52! =
>> 80658175170943878571660636856403766975289505440883277824000000000000
>> permutations of 52 cards. If one considers the permutations of the 13 pil
>> es
>> as equivalent and also the permutations of the four suits one still 
>> arrives at a number
>> of possible Pile On games that exceeds by far the number of nanoseconds 
>> that passed
>> since the beginning of the universe.
>>     
>
> I don't think that it is quite as bad as all that, given that all we
> really have is a set of 52 cards which are 4 sets of 13 cards with
> different marks on them.  Thus there is a significant reduction you
> can make at the start because an initial set where all the 8s are
> swapped for all the 4s are equivalent.
>   
Yes, you are certainly right. Nevertheless, if I take 52!,
- divide it by (4!)**13 accounting for the not-distinguishability of the 
four sorts of a suit
- divide this by 13! accounting for the interchangability of the ranks 
(your suggestion)
- divide this by 13! accounting for the permutations of the 13 piles
I arrive at 2373239768247142364082899540328 which is still
approx. 3.7 e+12 times the age of the universe in seconds.

May be there are still more symmetries to be considered. For me 
combinatorics
is an unstable ground :-(

> 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.
>
>   
Yes, I understood. An elegant mathematical proof for this would be 
interesting. I'd like
to see one. But what if the conjecture is wrong?

My ugly little backtracking program could not solve the following 
configuration:
(
(8, 4, 10, 4),
(9, 3, 2, 10),
(11, 6, 3, 9),
(8, 7, 1, 13),
(6, 8, 7, 12),
(5, 9, 12, 1),
(13, 3, 2, 1),
(13, 4, 6, 3),
(12, 6, 7, 7),
(11, 4, 10, 9),
(12, 5, 11, 11),
(2, 1, 5, 13),
(5, 8, 2, 10),
(),
()
)

Although out of of a series of 100 randomly generated start situations 
this is the
only one it could not solve, I fear chances are much higher, that my 
program has a bug
than that this is indeed not solvable. However I'd be very glad to see a 
solution for this
configuration. (Do you have a deck of cardes at hand?)

I for my part cannot check this, because there are many configurations I 
cannot solve
by hand that *are* solvable by my script. So, if I cannot mange it, that 
means nothing.

(Indeed originally I started to write this script because I tought
it might find a counterexample).

Best wishes (for finding the proof, and more)

Gregor


>> Yes, I would also be interested in such a proof. I for my part learned 
>> to know Pile On
>> only today and I find it rather difficult to play. So from my own very 
>> irrelevant
>> experience would expect that there are start configurations which might 
>> not be solvable -
>> --- at least for me :-(
>>     
>
> Don't believe the strategy that pysol gives about not stacking 3 cards
> of a same rank on a single.  As far as I can tell that is nonsense.  But
> do keep track of what cards are on the bottom.
>
>   
>> Thanks for the deverting hint
>> Gregor
>>     
>
> You are most welcome. :-)
>
> Laura
>
>
>