Solution to fivethirtyeight Riddler’s puzzle, Can You Pass The Cranberry Sauce? (November 20, 2020).

To celebrate Thanksgiving, you and 19 of your family members are seated at a circular table (socially distanced, of course). Everyone at the table would like a helping of cranberry sauce, which happens to be in front of you at the moment.

Instead of passing the sauce around in a circle, you pass it randomly to the person seated directly to your left or to your right. They then do the same, passing it randomly either to the person to their left or right. This continues until everyone has, at some point, received the cranberry sauce.

Of the 20 people in the circle, who has the greatest chance of being the last to receive the cranberry sauce?

I will exploit the Markovian property of the random walk process.

The puzzle does not impose any constraints on second servings (i.e., plates remaining in the same position), and has an equal probability of passing the plate to either side. Therefore, the Metropolis algorithm would give us a generic solution to the problem independent of the starting position.

sim_passes <- function(num_passes = 1e5, start_position = 5, table_size = 20) {
  plate_position <- rep(0, num_passes)
  current <- start_position
  for (i in 1:num_passes) {
    plate_position[i] <- current
    # proposal to pass plate left or right
    proposal <- current + sample(c(-1, 1), size = 1)
    if (proposal < 1) proposal <- table_size
    if (proposal > table_size) proposal <- 1
    # decision to pass
    current <- ifelse(runif(1) < 0.5, proposal, current)
  }
  return(plate_position)
}

The proportion of plate visits for each member is reciprocal to the table size. For example, if there are 20 people at the table, each person would have a probability of 1/20 = 0.05.

plate_positions <- sim_passes(num_passes = 1e6, start_position = 6, table_size = 20)
plate_positions |> table() / 1e6
## plate_positions
##        1        2        3        4        5        6        7        8 
## 0.050938 0.050095 0.049163 0.049633 0.049815 0.049265 0.049571 0.050172 
##        9       10       11       12       13       14       15       16 
## 0.050531 0.050021 0.049605 0.049620 0.049308 0.049083 0.049847 0.050434 
##       17       18       19       20 
## 0.050910 0.050515 0.050504 0.050970

Answer

Since it is equally probable to end up anywhere, and exclude the start position (for a restricted number of passes), the answer to the puzzle is 1/19 (~0.052).

Additional Notes

set.seed(123)

tibble(table_size = sort(c(20, 10^(1:3)))) |>
  mutate(plate_position = map(.x = table_size, ~ sim_passes(num_passes = 1e6, start_position = 1, table_size = .x))) |>
  unnest() |>
  group_by(table_size) |>
  mutate(passes = row_number()) |>
  group_by(table_size, plate_position) |>
  mutate(
    y_int = 1 / table_size,
    visit_count = row_number(),
    convergence = visit_count / passes
  ) |>
  ungroup() |>
  sample_n(size = 1e6) |>
  arrange(passes) |>
  ggplot(aes(passes, convergence)) +
  geom_step(aes(alpha = 0.5)) +
  geom_hline(aes(yintercept = y_int)) +
  facet_wrap(~table_size) +
  guides(col = "none", alpha = "none") +
  coord_cartesian(ylim = c(0, 0.2)) +
  scale_x_log10() +
  labs(
    title = "Tables of Different Sizes",
    x = expression(log[10] ~ "(passes)")
  )

You could also modify this algorithm to use a hash table with neighbor preferences and exploit this information at the decision step.