!Lets Get Deranged!

Imagine a movie show is sold out. The viewers don't sit in the seats indicated by the tickets, but chose their seats randomly. What is the probability that atleast one guy sits on the correct seat?

For that we need to first know what is the total number of permutations possible ( which is N! ), and what is the total number of permutations where none of the viewers take their designated seats, i.e. the number of derangements.

A derangement is a permutation of the elements of a set such that none of the elements appear in their original position. For example, the derangements for set { 1, 2, 3 } are { 3, 1, 2 } and { 2, 3, 1 }.  Number of derangements is called subfactorials. Subfactorial of N is represented as !N.

We start with counting the number of derangements. Suppose there are 'n' seats, the viewer with ticket number i takes seat j. There are (n-1) ways of doing it. Now, the viewer with ticket j has two options - he can either take seat i or leave it. If he takes seat i the case reduces to solving the problem for (n-2) people with (n-2) seats, where each has a forbidden choice. If he does not take the seat, the case reduces the problem of (n-1) people with (n-1) seats. Therefore, we get a recurring equation:-

!n = ( n - 1 ) ( !( n - 1 ) + !( n - 2 ) )

Thus, the probability is !n/n!


Now, imagine some of the viewers sat in their allotted seat. Such a configuration can be referred to as partial derangement. Let the number of viewers who take their correct place be k. Therefore, the number of such permutations can be given by R( n, k ) where, 

R( n, n ) = 1

R ( n, n-1 ) = 0

R ( n, k ) = ⁿC_k.!(n-k)

Algorithmic Games - Part 1 of N

Hello again, 

If I had to say one thing I learned most from my school pal Mridul, I would say it was his way of keeping an organised record of things that were important to him. He maintained a journal of all the bikes and cars he dreamed of owning, all pens he had (there were 100s of them), B'days, tele. no. and address of his all his classmates .......

He was referred to as the most neat and meticulous person in our batch and this inspired me towards keeping records and writing blogs or as I see it my taking a step into being a less messy me.

This post is my first attempt towards organizing the details of Game-Theory that I have come across till now. Someone who's just introduced to Game-theory may refer to this for more info and to those who have spent some time with it may refresh there basics as they go throug this.

So here we go:

First of all we define the basic properties of the games that we will be looking at, and they are :

1. There are two players.
2. There is a set, usually finite, of possible positions of the game.
3. The rules of the game specify for both players. If rules make no distinction between the players i.e. if players have same options of moving from each position, the game is called impartial :otherwise its called partial.
4. The players alternate moving.
5. The game ends when a position is reached from which no moves are possible for the player whose turn it is to move. Under the normal play rule, the last player to move wins. Under the misere play rule the last player to move loses.
6. The game ends in a finite number of moves no matter how it is played.

Simplest of such games are the Take away games. Here is an example explaining what a Take-away game is:

1. There are two players.
2. There is a pile of chips in the center of a table (say 30).
3. A move consists of removing one, two, or three chips from the pile. At least one chip must be removed, but no more than three may be removed.
4. Players alternate moves with Player I starting.
5. The player that removes the last chip wins.

We analyze this game from the end back to the beginning. This method is sometimes called backward induction.

We note that when there are no chips left its the loosing position for the person who's turn it is now. When there are 1,2 or 3 chips left, the person who's turn is next will definitely will (since he can take all the coins that are left). Now if we look at the situation where 4 chips are left, it appears to be a loosing one for the person who's turn is next, because no matter how many chips the player (who's turn it is) take away from the pile (he can take either 1,2 or 3 chips), he always ends up giving the other player a position from where we found he would win. Similarly we find that 5,6 and 7 are all winning positions for the person who's  turn is next.
Thus we see that the Take-away game ends up with a pattern of winning and loosing positions.
More elaborately, we define these winning positions and loosing positions as N positions and P positions respectivly.



P-positions and N-positions are defined recursively by the following three statements.
(1) All terminal positions are P-positions.
(2) From every N-position, there is at least one move to a P-position.
(3) From every P-position, every move is to an N-position



There  are innumerable games based on the above mentioned P-position N-position logic.
Describing each of them would make this reminder node too long, hence i have just mentioned their names.


Some Games based on P-position N-position logic are:

1. The Subtraction Game: This is a modified Take-away Game where the number of chips that can be removed from the pile of coin, is taken from a given set.
2. The Thirty-one Game:  Another modified Take-away Game where the number of times that a particular number can be subtracted from the pile is restricted to a given value.
3. Empty and Divide: In this there are two boxes containing (m,n) coins. at each turn a player needs to empty one box and divide the content of the other between the two boxes according to his wish.
4. Chomp: This game involves removing squares from a rectangular board (m*n) A move consists in taking a square and removing it and all squares to the right and above. The player who takes square (1, 1) loses.
5. Dynamic subtraction: Another modified Take -away Game with restriction on the subtracting numbers varying dynamicly.
6. The SOS Game: This consist of a square (n*n), initially empty, where player write S or O alternately. The first person who completes the word SOS wins.