Author |
Topic: The Oddness of Oddness (Read 531 times) |
|
ziep
Newbie
Posts: 12
|
 |
The Oddness of Oddness
« on: Aug 13th, 2004, 6:35pm » |
 Quote  Modify
|
International checkers is played on 10x10 board, and like checkers, only half of the board is in use. When a man reaches the opposite side it automatically promotes to a king.
With four men against one, there are 6175015 possible positions. Why is this odd? Is one particular position reponsible for this oddness?
|
| « Last Edit: Aug 13th, 2004, 6:36pm by ziep » |
 IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
|
Re: The Oddness of Oddness
« Reply #1 on: Aug 13th, 2004, 8:41pm » |
Quote Modify
|
I'm not sure why it's surprising that the answer is odd ... but anyways here's how I computed 6175015 . This post is long because I'm often verbose in my humble pursuit of being comprehensible to a larger audience, but the actual solving process was very short.
(hidden below; highlight area with mouse to see)
::
Let us denote the colors of the two teams by red and black, where red has four pieces and black has one. Let us imagine looking at the board from black's perspective, such that row 10 is the far row where black is kinged.
Because half the board is in use, there are 50 playable squares in total, with 5 squares per row.
There are four red pieces and one black piece. Note that they are specifically "men" -- not kings. Thus none of the red pieces can be on row 1, and the black piece is not on row 10.
Phase 1
First we consider ways of placing the red pieces. Since the last row is off limits, there are 45 squares up for grabs. The number of ways to choose 4 of these squares is C(45,4).
Phase 2
Now we count the number of places P the black piece can reside, given that the red pieces have already been placed. Since the reds cannot have occupied row 1, P is at least 5. Also, row 10 is off limits. That leaves 40 squares in the middle. However, some of these 40 squares may be occupied by reds, depending on how the reds were placed in Phase 1.
Here I use a probabilistic argument. Rather than counting how many squares are left for black on a case-by-case basis, Imagine throwing 4 red pieces uniformly at random onto the squares of rows 2 through 10. What is the expected number of pieces that will fall in rows 2 through 9 inclusive? If we consider rows 2-9 as being the first "cell" and row 10 as being the second "cell", then this process follows a multinomial distribution with probability 40/45 of falling into the first cell, and probability 5/45 of falling into the second cell. The number of counts in a single multinomial cell then follows a binomial distribution, and the expectation of a binomial is given by np, where n is the number of trials and p is the probability of success. Thus we can expect 4*(40/45) = 32/9 = 3.55555555 red pieces to fall in rows 2-9 on average.
Thus the expected number of spaces available for black is 5 + (40 - (32/9)).
Finally we multiply the number of positions for red by the number of positions for black to get our total count:
C(45,4) * (5 + (40 - (32/9))) = 6175015
::
|
| « Last Edit: Aug 13th, 2004, 8:50pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
ziep
Newbie
Posts: 12
|
|
Re: The Oddness of Oddness
« Reply #2 on: Aug 14th, 2004, 2:16am » |
Quote Modify
|
That's an elegant way to calculate!
I should have stated that I don't know the why the number of positions is odd. I do know that all other constellations of 3 pieces, 4 pieces and 5 pieces yield an even number of positions. Incidently, with four red men and one black man, there are exactly two positions which are losing for the red player (red to play).
I formulated a Sherlock Holmes-like puzzle based on this. (Stating black played the only non-taking move, and I , playing red, forcibly lost a position with less than 6 pieces, I had more than one piece and the positioncount with these pieces was odd- what was the position?). I can't solve it myself without using these tables.
So I'm looking for a smart way to figure out if the positioncount of a constellation (f.i. two kings against one man and two kings) is even or odd.
|
| « Last Edit: Aug 14th, 2004, 2:17am by ziep » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print