IBM Research | Ponder This | August 2024 Challenge

August 2024 - Challenge

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:

$A 4x4 grid of rectangles, each containing a mathematical symbol. From left to right and top to bottom: \Theta(R), \pi(n), GL_n(R), e, \mu(n), \varphi, O(n), Q_8, D_{2n}, \Omega(n), \pi, o(n), \sigma(n), S_n, \gamma, \phi(n)$

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

$The same 4x4 grid as before, with the rectangles colored to reflect the various groupings of the symbols. The four groups are: 1) \Theta(R), O(n), \Omega(n), o(n) in cyan (asymptotic notations) 2) \pi(n), \mu(n), \sigma(n), \phi(n) in green (number-theoretic functions) 3) GL_n(R), Q_8, D_{2n}, S_n in yellow (non-abelian groups) 4) e, \varphi, \pi, \gamma in red (mathematical constants)$

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.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Challenge: 29/07/2024 @ 12:40 PM EST
Solution: 09/09/2024 @ 11:00 AM EST
List Updated: 12/09/2024 @ 11:30 AM EST

*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)