Sunday, September 21, 2008

Up's & Down's Game

Players (2) take turns, each playing m rounds where they are offense
and each playing m rounds where they are defense. A player's grand
score is the sum of the player's scores for rounds where they played
offense.
Both players on a round *take turns* adding one number at a time to a
list.
The number should be from 1 to n (where n is, say, 20) and must not
have
been already put in the list by either player.
After n turns the list is complete and represents a permutation of the
integers 1 through n.
Scoring (by the offensive player) is as follows.
Write below the list of integers (if the integer list was made from
left to right) a list of (n-1) U's and D's, placing each letter between
and below each pair of neighboring integers, a U for up if the
right-most element of the pair above the letter is greater than the
left-most element, or put a D for down if the right-most element of the
pair above the letter is less than the left-most element of the pair.
(See example below.)
The offensive player gets a point for each element in the *longest*
sequence of U's and D's that occurs somewhere else in the U/D list.
And it is possible that a particular U/D sub-sequence shares specific
elements with its duplicate.
For example:
If we have the 10-integer game:
1, 7, 3, 5, 2, 9, 10, 4, 6, 8,
(Player 1 added the 1, 3, 2, 10, and 6 to the list;
Player 2 added the 7, 5, 9, 4, and 8 to the list)
we would have the U/D sequence:
U, D, U, D, U, U, D, U, U.
Now the sub-sequence U, D, U, U occurs twice in the sequence
(with the pair sharing one of their U's).
So the offensive player gets 4 points.
If the finished game looked like:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ,
then we would have the U/D sequence of only U's (9 in number),
U, U, U, U, U, U, U, U, U.
And what would the score be here?
8 points, because the subsequence which equals another subsequence
is made up of 8 U's, and the two subsequences each share the middle 7
U's.
So, as I have implied, the two equal subsequences can share any
number of common elements but not share every element --
they must terminate at different locations in the U/D sequence.
thanks,
Leroy Quet