Number of ways a certain event will occur in a game

[JimBob81345]

Each of 2n people are assigned a number from 1 to x so that every number is assigned to exactly 2 people. The people are then arranged randomly in a line. Every round of the game, the person at the front of the line goes to the corner. If two people with the same number are in the corner, both people immediately exit the place and DO NOT go to the end of the line. The round ends after the two people exit the corner. Out of all the possible orderings of the people in a line, how many have the following property: After every round, the corner consists of at most 2 people.

My Work:
- If there are two people of the same number next to each other in the line, then the permutation of people cannot satisfy the previous condition unless one person is already in the corner.
- If there are 2 people of the same number one person apart, then the condition is not satisfied if a person is already in the corner.

 

[mfb]

What can you say about the numbers in the row if the corner is empty after 2m people?
How many patterns can you find such that the corner is empty after 2m people but not before?

 

[scottdave]

Start with some simple examples of the game and work through them. First with 2 people and 1 number (seems trivial but may give you some insight into a pattern for higher numbers), then with 4 people and 2 unique numbers. Then 6 people and 3 numbers. See if you can then figure out a general case.