Alan Sagan schrieb: > email@example.com (Acid Pooh) wrote in message > > Suppose you're racking up 15 billiard balls in one of the standard > > configurations (I'm not going to try to typeset these, so just picture > > an equilateral triangle instead of a right one): > > > > S > > T S > > S E T > > T S T S > > S T S T T > > > > where S is a "solid," T is a stripe, and E is the eight ball. A > > configuration is also standard if every S is mapped to a T, or if the > > triangle is reflected across its verticle axis of symmetry. Anyway, > > so you're racking up and you dump 15 balls into the rack randomly. > > Assuming you don't make any mistakes, what's the maximum number of two > > ball permuations necessary to get to any of the 4 standard > > configurations?
> I get 4
a) You need at most 4 moves.
First place the eight-ball, using up one move. For each misplaced solid, there's a misplaced stripe now. Of the 7 solids and stripes each, there can be at most 3 such misplaced pairs; because if there were more wrong, you'd aim for a solution with solids and stripes exchanged, and have less wrong. Thus, you never need more than 4 moves.
b) You may need 4 moves.
Proof by example:
E T T S S S T T T T S S T S S
One move is needed to move the E inside. 2 moves are needed to rectify either the left or the right edge. Now the top and ball and the center ball in the bottom row are of different kinds, but they have to be the same, so a fourth move is needed to fix this. These same-same relations (between row endpoints and the top-bottom) are invariant under remapping T<->S and vertical mirroring, so there is no way to do it shorter.
Cheers Michael -- Still an attentive ear he lent Her speech hath caused this pain But could not fathom what she meant Easier I count it to explain She was not deep, nor eloquent. The jargon of the howling main -- from Lewis Carroll: The Three Usenet Trolls