Ponder This Challenge - August 2024 - Playing blind the set-matching game

This month’s challenge was inspired by the New York Times game, Connections. In our version of this popular game, players are presented with 16 items and asked to split them into 4 sets of 4 items each, where the elements of each set have something in common. For example, consider the following elements:

The intended way to split them into sets can be demonstrated using the following coloring:

where the sets are mathematical constants, non-abelian groups, number-theoretic functions, and asymptotic notations.

Suppose a player has no idea what the elements mean and simply categorizes the 16 elements into 4 sets at random. If the player guessed a set correctly, it is marked and removed from the game, and the player keeps guessing at random (and may even repeat previous failed guesses) until all the correct sets were guessed. We call each time the player chooses a random partition and receives a feedback on the choice "a step".

Note: unlike the original game, in this game the player chooses a full partition of all the remaining elements into sets, not just choosing elements for one set. So in the beginning the player is making 4 guesses at once.

Your goal: Find the expected number of steps in such a blind game, given a player's totally random behavior. You can round to the nearest integer.

A bonus "*" will be given for solving the same problem, but for a game consising of 50 items, categorized into 10 sets of 5 elements each.

Solution

• Click here to view the solution

  August 2024 Solution:

  The answers are 205 and 60694.

  This problem is a relativly simple case of a Markov chain: Assume for the general case we have $n$ sets with $k$ elements each (for our problem we have $n=k=4$ for the standard and $n=10, k=5$ for the bonus).

  We have a state $Q_{i}$ for every number $0\le i\le n$ of sets we already guessed, and we compute the transition probability between states: $p_{ij}$ is the probability of transition from $Q_i$ to $Q_j$. Denote the expected time to hit $Q_n$ starting from $Q_i$ by $h_i$, then (as a special case of the general theorem about hitting times in Markov chains) we have the following equations:

  • $h_n = 0$
  • $h_i = 1 + \sum_{j=0}^{n} p_{ij} h_j$

  This is simplified by noting that $p_{ij} = 0$ for $j<i$ since we cannot "unguess" a set. So we can write:

  $h_i =1+p_{ii}h_i+\sum_{j=i+1}^n p_{ij}h_j$

  Leading to the solution

  $h_i = \frac{1+\sum_{j=i+1}^n p_{ij}h_j}{1-p_{ii}}$

  We are interested in the expected time to reach $Q_n$ from $Q_0$, hence we iteratively compute $h_n, h_{n-1}, \ldots, h_0$ with $h_0$ being our result.

  It remains to compute the transition probabilities $p_{ij}$, i.e. to solve the combinatorial problem "Given n-i sets to guess, each with k elements, what is the probability of guessing exactly $j-i$?"

  The combinatorial object being counted is the number of ways to partition $\{1,2,\ldots, n\cdot k\}$ into $n$ sets, with no order between the sets. If we do consider the order between sets, this is the standard problem of permutations with repetition (we permute the set designations - the "colors"), which is solved by the formula $\frac{(nk)!}{(k!)^n}$ We divide it by $n!$ to accomodate for the lack of order between sets and obtain the value $F(n,k)=\frac{(nk)!}{n!(k!)^n}$.

  Given at least $j$ correct "guesses" it means there remain $n-j$ sets whose elements are freely distributed, hence there are $F(n-j,k)$ partitions which guess specific $j$ sets. To count the number of guesses where exactly $j$ correct guesses were made we use the inclusion-exclusion principle:

  $G(n,k,j) = {n\choose j}\sum_{r=0}^{n-j}(-1)^{r}{n-j\choose r}F(n-j-r,k)$

  Where ${n\choose j}$ is the number of ways to choose the specific $j$ sets correctly guessed, and the sum is a standard use of inclusion-exclusion to find the number of guesses (for the remaining $n-j$ sets) where no correct guess was made.

  This gives us the probability of guessing exactly $j$ of the $n$ possible sets: $\frac{G(n,k,j)}{F(n,k)}$ and hence, $p_{ij} = \frac{G(n-i,k,j-i)}{F(n-i,k)}$, with the above hitting expectation time equations giving the solutions.

  The following (inefficient) code immediately solves both the standard and the bonus problems:

  from math import factorial, comb
  
  
  def F(n, k):
      return factorial(n*k) // (factorial(k)**n * factorial(n))
  
  
  def G(n,k,j):
      return comb(n,j)*sum([(-1)**r*comb(n-j,r)*F(n-j-r,k) for r in range(n-j+1)])
  
  
  def p(i,j, n, k):
      return G(n-i,k,j-i)/F(n-i,k)
  
  
  def h(i, n, k):
      return (1+sum([p(i,j,n,k)*h(j,n,k) for j in range(i+1,n)]))/(1-p(i,i,n,k))
  
  
  print("(4,4) problem:", float(h(0,4,4)))
  print("(10,5) problem:", float(h(0,10,5)))
  

Solvers

• *Daniel Chong Jyh Tar (29/7/2024 1:38 PM IDT)
• *Lazar Ilic (29/7/2024 5:56 PM IDT)
• *King Pig (29/7/2024 10:43 PM IDT)
• *Jared Kittleson (30/7/2024 1:56 AM IDT)
• Guglielmo Sanchini (30/7/2024 5:14 PM IDT)
• *Thomas Egense (30/7/2024 10:21 PM IDT)
• *Todd Will (30/7/2024 11:55 PM IDT)
• *Dieter Beckerle (31/7/2024 1:37 PM IDT)
• Guillaume Escamocher (31/7/2024 8:36 PM IDT)
• *Bertram Felgenhauer (31/7/2024 9:00 PM IDT)
• *Sanandan Swaminathan (31/7/2024 10:37 PM IDT)
• *Alper Halbutogullari (1/8/2024 2:11 PM IDT)
• Daniel Bitin (1/8/2024 5:17 PM IDT)
• *Bert Dobbelaere (1/8/2024 7:14 PM IDT)
• *Yan-Wu He (1/8/2024 7:17 PM IDT)
• *Robin Guilliou (1/8/2024 11:16 PM IDT)
• *Vladimir Volevich (2/8/2024 4:22 PM IDT)
• Noam Zaks (2/8/2024 4:43 PM IDT)
• *John Spurgeon (3/8/2024 3:44 AM IDT)
• *Yi Jiang (3/8/2024 11:19 AM IDT)
• Suus Brommer (4/8/2024 11:51 AM IDT)
• *Latchezar Christov (4/8/2024 12:47 PM IDT)
• Shouky Dan & Tamir Ganor (4/8/2024 4:03 PM IDT)
• Reiner Martin (5/8/2024 1:25 AM IDT)
• *Victor Chang (5/8/2024 7:48 AM IDT)
• *Guangxi Liu (5/8/2024 2:00 PM IDT)
• James Dow Allen (5/8/2024 9:09 PM IDT)
• *Amos Guler (6/8/2024 9:56 PM IDT)
• Julian Ma (6/8/2024 10:23 PM IDT)
• *Nolan Jiang (7/8/2024 1:53 AM IDT)
• *Jenna Talia (7/8/2024 7:54 AM IDT)
• *Lawrence Au (7/8/2024 8:09 PM IDT)
• Hakan Summakoğlu (7/8/2024 8:35 PM IDT)
• *Kipp Johnson (8/8/2024 12:12 AM IDT)
• Nivrutti Tambe (8/8/2024 12:06 PM IDT)
• Gary M. Gerken (8/8/2024 1:34 PM IDT)
• *Joaquim Neves Carrapa (8/8/2024 1:52 PM IDT)
• *Mark Pervovskiy (8/8/2024 6:30 PM IDT)
• *Motty Porat (9/8/2024 12:36 AM IDT)
• *Daniel Copeland (9/8/2024 1:17 AM IDT)
• Marco Bellocchi (9/8/2024 2:01 AM IDT)
• Paul Revenant (10/8/2024 2:48 PM IDT)
• Piyush Agrawal (10/8/2024 2:58 PM IDT)
• Stefan Wirth (11/8/2024 3:41 AM IDT)
• Shirish Chinchalkar (11/8/2024 6:05 AM IDT)
• *Asaf Zimmerman (11/8/2024 1:14 PM IDT)
• *Juergen Koehl (11/8/2024 9:31 PM IDT)
• Evan Semet (12/8/2024 7:42 PM IDT)
• *Andrew Gauld (13/8/2024 1:05 AM IDT)
• *Blue Lagoon (13/8/2024 2:20 AM IDT)
• Mark J. Murphy (13/8/2024 3:29 AM IDT)
• Fabio Michele Negroni (13/8/2024 3:10 PM IDT)
• *Arthur Vause (13/8/2024 7:22 PM IDT)
• *Dan Dima (13/8/2024 8:19 PM IDT)
• *Dejan Stakic (14/8/2024 9:43 AM IDT)
• Fakih Karademir (15/8/2024 10:47 AM IDT)
• Adrian Neacsu (15/8/2024 6:32 PM IDT)
• *Sri Mallikarjun J (15/8/2024 7:01 PM IDT)
• *Lorenz Reichel (16/8/2024 9:21 AM IDT)
• *Sanjay Rao (16/8/2024 2:00 PM IDT)
• John Tromp (16/8/2024 5:44 PM IDT)
• *K S (17/8/2024 6:04 AM IDT)
• Paul Lupascu (18/8/2024 8:54 AM IDT)
• Ethan (EJ) Watkins (19/8/2024 5:12 PM IDT)
• *Christoph Baumgarten (19/8/2024 11:10 PM IDT)
• *Harald Bögeholz (20/8/2024 2:15 PM IDT)
• Andreas Eisele (20/8/2024 3:46 PM IDT)
• *T Cyclone (21/8/2024 5:06 AM IDT)
• *Victor Cai (22/8/2024 6:14 AM IDT)
• *Anton Sjöstrom (22/8/2024 10:22 PM IDT)
• *Nyles Heise (23/8/2024 5:25 AM IDT)
• *David Greer (23/8/2024 3:48 PM IDT)
• *Kang Jin Cho (24/8/2024 11:48 AM IDT)
• Dusan Drobnjak (24/8/2024 6:22 PM IDT)
• *Justin Snopek (24/8/2024 7:38 PM IDT)
• Gyozo Nagy (24/8/2024 8:12 PM IDT)
• *Dillon Davis (24/8/2024 11:08 PM IDT)
• *Guy Daniel Hadas (25/8/2024 11:26 AM IDT)
• *David F.H. Dunkley (26/8/2024 10:18 AM IDT)
• Aviv Nisgav (26/8/2024 12:04 PM IDT)
• Kasi Ravinder (27/8/2024 6:54 PM IDT)
• Ido Meisner (30/8/2024 12:52 AM IDT)
• *Andrea Andenna (31/8/2024 2:03 AM IDT)
• *Hugo Pfoertner (31/8/2024 11:00 PM IDT)
• *Nathan Salo (1/9/2024 7:02 AM IDT)
• *Griffin Pinney (1/9/2024 8:46 AM IDT)
• *Avi Levin (1/9/2024 2:29 PM IDT)
• Alex Izvalov (1/9/2024 6:07 PM IDT)
• *Radu-Alexandru Todor (1/9/2024 8:48 PM IDT)
• *Aaditya Raghavan (2/9/2024 5:49 PM IDT)
• Tim Walters (3/9/2024 12:02 AM IDT)
• Blaine Hill (4/9/2024 7:22 AM IDT)
• Erik Wünstel (4/9/2024 11:30 AM IDT)
• *Li Li (4/9/2024 5:15 PM IDT)