wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Not following suit.
        
(Message started by: Aryabhatta on Oct 30th, 2004, 1:34pm)
Title: Not following suit.
Post by Aryabhatta on Oct 30th, 2004, 1:34pm
There are N people, playing a game with a deck of kN cards. That deck has N different suits, each suit having k cards.

The game is played as follows.

The N people sit around a circle and the cards are distributed randomly among the N people, each getting k cards. Everyone knows what cards the other players have.  The game is played in rounds.

In each round, the player in the first seat plays a card. The other players then take turns playing a card, going clockwise around the circle till N-1 more cards are played. The players should follow the rule: any player should not play a suit previously played in that round. i.e if we collect the N cards played in a round, each card must be of a different suit.

Show that for any initial distribution of cards, the game can be played in such a way as to complete k rounds.

Do these type of questions appear in the Putnam Exam?
Or are these not considered 'pure' math?
Title: Re: Not following suit.
Post by Obob on Oct 31st, 2004, 5:51pm
Something like this could certainly appear on the Putnam.

Here's a stab at a solution:

Say that an initial configuration of cards is "winnable" if there is some way to win the game.  I claim that the class of winnable games is invariant under the following transformation: if player j plays a card of suit 1 in the pth round, then swap the card that player 1 plays in round p with player j's card of suit 1.  But it is clear that this trade does not change the winnability of the game: simply have player 1 play what used to be player j's card of suit 1 in round p, and have player j play player 1's old card (all other players proceed as before).  Player 1's old card is not of suit 1, because otherwise the original strategy would not have been winning, so a complete set of suits will appear in the pth round.

By repeatedly applying this principal, we may assume that player 1 possesses all the cards of suit 1.  In essence we can remove player 1 from the game, as his moves have no relevance on the outcome of the game anymore.  But then by induction on N (the number of players and suits), together with the trivial base case N=1, we are done.
Title: Re: Not following suit.
Post by Aryabhatta on Nov 1st, 2004, 1:17pm

on 10/31/04 at 17:51:51, Obob wrote:
Something like this could certainly appear on the Putnam.

Here's a stab at a solution:

Say that an initial configuration of cards is "winnable" if there is some way to win the game.  I claim that the class of winnable games is invariant under the following transformation: if player j plays a card of suit 1 in the pth round, then swap the card that player 1 plays in round p with player j's card of suit 1.  But it is clear that this trade does not change the winnability of the game: simply have player 1 play what used to be player j's card of suit 1 in round p, and have player j play player 1's old card (all other players proceed as before).  Player 1's old card is not of suit 1, because otherwise the original strategy would not have been winning, so a complete set of suits will appear in the pth round.

By repeatedly applying this principal, we may assume that player 1 possesses all the cards of suit 1.  In essence we can remove player 1 from the game, as his moves have no relevance on the outcome of the game anymore.  But then by induction on N (the number of players and suits), together with the trivial base case N=1, we are done.



What you have shown is that we can go from one winning position to the other by a sequences of swaps. We need to show a way of going to *any* position from a winning position by a squence of swaps... That this can be done, is not very clear.

Title: Re: Not following suit.
Post by John_Gaughan on Nov 1st, 2004, 1:53pm
I think induction is the way to go. I can figure out the inductive step, but wording the base case correctly proves to be elusive...
Title: Re: Not following suit.
Post by Obob on Nov 1st, 2004, 2:43pm
You're completely right, Aryabhatta.  My reasoning was backwards.  Suppose that every game with N-1 players is winnable (1-player games are winnable).  Then the game with N players where the Nth player has all the cards of suit N is clearly winnable.  Suppose that in the final desired configuration with N players, the jth player has gained a card of suit N in exchange for his card of suit m which he played during round p in the winning game with N-1 players.  Now (back in the game where player N has all the cards of suit N) have player N give his pth copy of the card of suit N to player j in exchange for his card of suit m.  By having player j play the card of suit N in the pth round and having player N play the card of suit m in the pth round, while having all other players proceed as in the N-1 case, the new game is still winnable.  Have player N distribute all of his cards of suit N to the appropriate players so that the players 1,2,...,N-1 all have the appropriate cards to achieve the desired final configuration.  As these trades preserve the winnability of the original winnable game and player N has all the cards which are remaining, we have obtained the desired final configuration, and it is winnable.
Title: Re: Not following suit.
Post by Aryabhatta on Nov 2nd, 2004, 10:09am

on 11/01/04 at 14:43:00, Obob wrote:
You're completely right, Aryabhatta.  My reasoning was backwards.  Suppose that every game with N-1 players is winnable (1-player games are winnable).  Then the game with N players where the Nth player has all the cards of suit N is clearly winnable.  Suppose that in the final desired configuration with N players, the jth player has gained a card of suit N in exchange for his card of suit m which he played during round p in the winning game with N-1 players.  Now (back in the game where player N has all the cards of suit N) have player N give his pth copy of the card of suit N to player j in exchange for his card of suit m.  By having player j play the card of suit N in the pth round and having player N play the card of suit m in the pth round, while having all other players proceed as in the N-1 case, the new game is still winnable.  Have player N distribute all of his cards of suit N to the appropriate players so that the players 1,2,...,N-1 all have the appropriate cards to achieve the desired final configuration.  As these trades preserve the winnability of the original winnable game and player N has all the cards which are remaining, we have obtained the desired final configuration, and it is winnable.


I am sorry. I must be missing something. It still looks backwards to me. Could you please explain it a little more clearly?
Title: Re: Not following suit.
Post by Obob on Nov 2nd, 2004, 11:56am
Consider only the cards of the first N-1 players in an N player game.  At most N of their cards are of suit N.  Moreover, there are at most N cards missing from being able to form a complete set of k cards of each suit 1,...,N-1, and this number is exactly equal to the number of cards of suit N among players 1,...,N-1.  Replace each of the cards of suit N with the missing cards bijectively (and arbitrarily).  When we consider only the players 1,...,N-1, we have a game with N-1 players.  Hence it is winnable.  Induce the game on N players with the same configuration for the first N-1 players, and so that the Nth player has all the cards of suit N.  Now we can induce a solution on the original N player game as follows: if a player plays a card in round p which corresponds to a card of suit N in the original game, have this player trade his card with the pth copy of N that the Nth player possesses.  Have the Nth player play this card in the pth round, and have the pth copy of N also be played in the pth round.  By doing this, we obtain that the original configuration of cards is winnable (in particular, note that if we know the cards of the players 1,...,N-1, then the cards of player N are uniquely determined).
Title: Re: Not following suit.
Post by Aryabhatta on Nov 2nd, 2004, 3:12pm

on 11/02/04 at 11:56:16, Obob wrote:
When we consider only the players 1,...,N-1, we have a game with N-1 players.  Hence it is winnable.  Induce the game on N players with the same configuration for the first N-1 players, and so that the Nth player has all the cards of suit N.  Now we can induce a solution on the original N player game as follows: if a player plays a card in round p which corresponds to a card of suit N in the original game ...,


Aren't you are assuming here that original game can be played, which is what we wanted to show in the first place?
Title: Re: Not following suit.
Post by Obob on Nov 2nd, 2004, 3:48pm
No.  I'm assuming that the game with N-1 players obtained by swapping out the cards of suit N to complete a set of k(N-1) cards of suits 1,...,N-1 can be played.  But the inductive hypothesis demonstrates this.
Title: Re: Not following suit.
Post by Obob on Nov 2nd, 2004, 3:51pm
In your underlined segment, "in the original game" is referring to the correspondence between cards of suit N owned by players 1,...,N-1 and the cards which are missing from a complete set of k(N-1) cards of suits 1,...,N-1.  "Round p" in the underlined portion refers to the pth round of play in the game obtained by swapping out the cards of suit N and then playing with only N-1 players.
Title: Re: Not following suit.
Post by Aryabhatta on Nov 2nd, 2004, 8:46pm

on 11/02/04 at 15:51:10, Obob wrote:
In your underlined segment, "in the original game" is referring to the correspondence between cards of suit N owned by players 1,...,N-1 and the cards which are missing from a complete set of k(N-1) cards of suits 1,...,N-1.  "Round p" in the underlined portion refers to the pth round of play in the game obtained by swapping out the cards of suit N and then playing with only N-1 players.


As I understand it, it looks like the swapping solution will not work.

Suppose we are given an original distribution for N people.
Colour the Nth person's cards red and colour the Nth suit green (overpaint the red if required).

Now when we do a reshuffle, write the same number on the red and the green which correspond in the bijection. After reshuffle, all the (green) cards of the Nth suit are with the Nth person.

Now we look at the game for the N-1 people.
By induction hypothesis, the distribution which we obtained has a k-round game say R1,R2,...,Rk.

For each Ri, we look at a red card which has been played and swap it with the corresponding green card to get a new round R'i. i.e. in R'i the Nth person plays the red card and the person who played the red card plays the green which corresponds to the red (and hence plays a card which he was dealt originally).

You claim that R'1,R'2,...,R'k is a valid game for the original distribution.

This claim is not true, as we could have _more than one_ red card played in some round Rj. How do you do the swap for this round?  Swapping just one red card won't give us our original distribution back. (Note that In the original distribution the Nth player had all the red cards and no other colour except possibly green).
Title: Re: Not following suit.
Post by Aryabhatta on Nov 10th, 2004, 4:14pm
Hint:
[hide]

If the game can be played for a round, it can be played for k rounds.

[/hide]
::
Title: Re: Not following suit.
Post by asterix on Nov 12th, 2004, 12:59pm
Suppose you play the game and you reach an unwinnable position. N-1 players have played N-1 different suits, and the last player is missing the last suit. Have him play any card he has and the person who played that suit must pick up his card and play a different suit (that can't be the only suit he has, because if it was, he would be the only one who has that suit). That person will do the same, pickup his card and play a different suit. Eventually one of two things must happen, either you reach a person who holds the missing suit and the position becomes winnable, or you go into a cycle of the same few players swapping over and over again. One of the people in that cycle must have a card of a suit played by somebody not in that cycle, because the players not in the cycle have one extra card of the missing suit, so in their gamut of suits they must be missing a card that is held by one of the cyclists. If players 1-4 only had cards of suits 1-4, for example, then someone outside of that cycle could not have played a card that would have forced them to double up a suit. The cycle will always be expandable until it finds the person with the missing suit, and the play becomes winnable.
Title: Re: Not following suit.
Post by Aryabhatta on Nov 13th, 2004, 1:20pm

on 11/12/04 at 12:59:20, asterix wrote:
Suppose you play the game and you reach an unwinnable position. N-1 players have played N-1 different suits, and the last player is missing the last suit. Have him play any card he has and the person who played that suit must pick up his card and play a different suit (that can't be the only suit he has, because if it was, he would be the only one who has that suit). That person will do the same, pickup his card and play a different suit. Eventually one of two things must happen, either you reach a person who holds the missing suit and the position becomes winnable, or you go into a cycle of the same few players swapping over and over again. One of the people in that cycle must have a card of a suit played by somebody not in that cycle, because the players not in the cycle have one extra card of the missing suit, so in their gamut of suits they must be missing a card that is held by one of the cyclists. If players 1-4 only had cards of suits 1-4, for example, then someone outside of that cycle could not have played a card that would have forced them to double up a suit. The cycle will always be expandable until it finds the person with the missing suit, and the play becomes winnable.



Why can we assume that N-1 people of the N people can play cards without a hitch? Why not 3N/4 or something like that?

The assumption that no person has cards of the same suit is OK as we can assume as a induction hypothesis that the game can be played when there are exactly N-1 people.

The cycle can be made different, but why 'expandable' ?
Title: Re: Not following suit.
Post by asterix on Nov 13th, 2004, 2:34pm
The method works no matter at what point the problem crops up. Just substitute in my explanation "For any player P the players before him have successfully played P-1 different suits."
And I am defining the "cycle" here as all those players who can take part, not just those who will in fact take part if the active players are too dumb to actually pick his suit. Reaching any new player expands the cycle, it doesn't just make it a different cycle, because every player reached so far is still reachable.  
If any subset of players C ever are truly stuck, then that would have to mean that those C players only have C-1 suits between them, because one suit is constantly doubled up. If there are 4 people in the cycle, the reachable group, then each person, on his turn sees 3 suits on the table from the other three players, and since he can't play a new suit, his hand must only contain those 3 suits or a subset of them. So all 4 people in the cycle have only those 3 suits. That is obviously not possible, since at any point in the game each player has k cards and there are k cards available in each suit. Together they hold Ck cards while there are only (C-1)k cards that could prevent them from either playing an unplayed suit or playing a suit that was played by someone not yet in the cycle. The cycle must expand until a new suit can be played.
Title: Re: Not following suit.
Post by Aryabhatta on Nov 15th, 2004, 1:54pm
Asterix's solution, though not very clear to me seems right at the first glance. Maybe if asterix would be kind enough to present a clearer proof...

Anyway, here is one solution.

It is enough if we can prove that, no matter what the value of k is, we can play a round. Then by induction on k, the playability of the game follows. (k=1 is trivial)


Consider an nxn matrix with the rows for suits and columns for people. The ijth (= aij) entry corresponds to number of cards person j has of suit i.  Note the each row sums to k and each column sums to k.

For showing that one round can be played, we are looking for n non-zero entries of the matrix such that there is exactly one entry in each row and one in each column. (basically a permutation... )

We can apply Hall's marriage theorem here.

For each Row Ri define Si = {j | aij > 0}

We want to show that S1, ... , SN has a system of distinct representatives.

Suppose for some t, there are t rows for which the Halls marriage theorem condition does not apply i.e

|S1 U ... U St| < t  -- ( 1 )

Counting the sum of positive entries of the t rows, we find that the sum is tk. But counting the same sum using the columns based on ( 1 ), the sum is < tk. A contradiction.

Thus a round can be played, and by induction on k, the game can be played.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board