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
_______________________________________________
Edu-sig mailing list
Edu-sig@python.org
http://mail.python.org/mailman/listinfo/edu-sig
