IBM Ponder This #316 · August 2024

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

Best opened after a real attempt

To be added.