Riddler Classic 2022-12-16

Can You Make It To 2023?

The question from fivethirtyeight.com:

Every Christmas, Gary’s family has a gift exchange. And every year, there is a big fight over how much folks should spend on the gifts. This year, they decided to pair up. So if Virginia gives Justin a gift, then Justin gives Virginia a gift. This way, while there will still be arguments, only two people will be involved in each argument.

There are 20 people in the gift exchange. In the first round, everyone writes down the name of a random person (other than themselves) and the names go in a hat. Then if two people randomly pick each other’s names out of that hat, they will exchange gifts, and they no longer participate in the drawing. The remaining family members go on to round two. Again, they write down the name of anyone left, and again, any two people who pick each other exchange gifts.

This continues until everyone is paired up. And yes, if exactly two people remain, they still go through the process of selecting each other, even though they know who their partner will be.

On average, what is the expected number of rounds until everyone is paired up?

Three R Functions to run the Sampling Scheme Described

This function iteratively selects \(n\) people (excluding self), and people could be selected more than once.

sample.everyone.else = function(n = 20){
  sample.others = vector(length = n)
  int.seq = 1:n
  for(i in int.seq) sample.others[i] = sample((int.seq)[-i], size = 1)
return(sample.others)
}

This function takes the bowl of names from sample.everyone.else, draws \(n\) names, checks whether two people got each other, and returns the number of matches.

party.sampler = function(n = 20){
  party = sample(x = sample.everyone.else(n), size = n, replace = FALSE)
  matches = (party[party] == 1:n) & (party != 1:n)
return(sum(matches))
}

This table demonstrates a small, four-person example of party.sampler where each person is represented by a number (1 through 4).

party is the the person someone else drew, party[party] == 1:4 checks whether the person someone got also got them while party != 1:4 checks that they didn’t get themselves, and matches checks whether both conditions are true.

In short, person 2 and 4 got each other (and should match), person 1 got themselves and should not match, and person 3 did not get matched with person 4. There should be two people removed from this round.

index	\(\texttt{party}\)	\(\texttt{party[party] == 1:4}\)	\(\texttt{party != 1:4}\)	\(\texttt{matches}\)
1	1	TRUE	FALSE	FALSE
2	4	TRUE	TRUE	TRUE
3	4	FALSE	TRUE	FALSE
4	2	TRUE	TRUE	TRUE

This function calls the party.sampler function until everyone has been selected. It is thus the main function that is called in the simulation.

party.time = function(guests = 20){
  i = 0
  while(guests > 0){
    matches = party.sampler(guests)
    guests = guests - matches
    i = i + 1
  }
return(i)
}

Run the Simulation

replicate repeats the party.time function one million times.

set.seed(538)
M = 10^6
counts = replicate(n = M, expr = party.time())
sim.results = counts |> table() |> as.data.frame()
names(sim.results) = c("turns", "freq")
sim.results = sim.results |> mutate(turns = as.integer(as.character(turns)))
# save(sim.results, file = "simresults.rda")

Simulation Results

Below, we see the distribution of turns until everyone has matched after a simulation with one million replications. The expected value is estimated to be \(24.02582\).