How to assign seats to the passengers maintaining social distancing?

Question

Imagine there are 30 people in line to board a train that seats 100. However, per current

regulations there must be at least two empty seats between each pair of passengers. The

regulations are not particularly accurate in terms of actual physical distance: the authorities

based adjacency purely on the seat number (which go from 1 to 100). Seat 55 is considered to

be next to 56 and 57, seat 1 is next to just seat 2. Thus if someone is sitting in seat 2, no one

may sit in seats 1, 3 or 4; if someone is sitting in seat 33, no one may sit in 31, 32, 34 or 35; if

someone is sitting in seat 100, no one may sit in 98 or 99.

Passengers have tickets assigned to one of the seats and they board in random order. (Seat

assignments are chosen at random from the 100, and no two passengers have the same

assigned seat). If, when boarding, a passenger’s assigned seat is too close to an

already-seated passenger (or already occupied!) they choose a free seat at random that does

not violate the social distancing rules. When there are no more free, non-violating seats,

boarding is complete, and any remaining passengers must wait for the next train.

Implement a simulation in Python that models the boarding process, and use it to answer the

following questions.

1. What is the chance that all 30 passengers will be seated?

2. If the first and second passengers were told to take the first and last seats (1 and 100),

regardless of their tickets (and then everyone else chooses seats randomly), now what is

the chance that all 30 passengers will be seated?

3. On average, how many passengers do you expect to sit in their originally assigned

seats? (What is the expected value?) Assume the original configuration (not the change

added with question #2).

4. Suppose there are no more assigned seats from the start, and passengers pick one at

random as they enter the train (still following the social distancing rules). How does this

affect the expected number of passengers who will board?

Answer 1

create an array of 100 boolean vars...

TRUE means the seat is available

FALSE means the seat is taken or not available

because of social distancing

as soon as a seat is selected and taken, set it to FALSE

and the 2 neighbors BEFORE and AFTER to false as well...