Can an LLM solve this combinatorics problem? | Sameer Wagh %F0%9F%94%90"><br>The intersection of LLMs and mathematical research is a fascinating one. Mathematics is objective and verifiable, and today’s frontier models have been trained extensively on its concepts and methods. There is a particular sense of joy and wonder in watching LLMs solve previously unsolved (and genuinely difficult problems), while knowing that their capabilities emerge from mechanisms that are, at their core, surprisingly simple.<br>To me, this is an extraordinary testament to what humans can achieve collectively through ingenuity, hard work, and engineering. Like many others working in this space, I became interested in testing the limits of LLMs on open mathematical problems through my own lens. This post tells the story of that process.<br>Introduction<br>You have 4 cards from a standard deck of cards: Ace, King of Hearts and Spades (A♥, K♥, A♠, K♠). You can point to a card and ask one of two possible questions:<br>Is this card Red?<br>Is this card a King?<br>These 4 cards are now shuffled. It is easy to find which card is which by asking 8 questions (each question on each card). However, your goal is to come up with a strategy for asking questions such that you can always find which card is which in under 5 questions. Try your hand at the interactive media below. Drag a question from the right onto any card to learn one fact about it, then click “I know it!” once you know for sure the full arrangement.<br>24arrangements left<br>0queries used<br>5information floor
Cards: A♥ K♥ A♠ K♠ — two questions (red?, king?).<br>Goal: identify the full arrangement in under 5 queries.
Shuffle & Play I know it!
Questions · drag to a card<br>Red suit? (♥♦)<br>Is this card a King?
Query log<br>Pos Red? King?
Also try: 8-card variation · 16-card variation
This post is about a using an AI to solve an open question posed around a scaled version of this simple puzzle. The rest of the post is organized into these sections:<br>16-card version scales the opening 4-card puzzle to 16 cards and then states the open mathematical question.<br>The bulk covers the search for optimal strategies: the LLM-agent execution setup, how performance evolved across fifty iterations, and a playable browser version of the game (jump here to see the main result).<br>I close with key learnings from the collaboration and connections to related open conjecture by Donald Knuth that was recently disproved [5].<br>16-card puzzle<br>This small problem can be extended to larger space and things get interesting there. You have sixteen unique cards (each encoding a 4-bit value \(0,1,\dots,15\)) and four binary properties . When you check property \(b\) of a card, you learn a single bit: bit \(b\) of that card’s hidden value. For instance, property $3$ reveals the most significant bit (MSB) of the card whereas property $0$ reveals its least significant bit (LSB).<br>It is easy to see that four property checks fully determine any given card. The catch: the cards are all shuffled face-down, so you don’t know which card is which. You can trivially do this in 64 checks (each property check on each card). The puzzle is to recover the whole arrangement (which card is which) in under 50 queries in the worst case. Can you do it? (You can play with smaller variants of the problem below.)<br>An open question<br>Underneath the story is an interesting permutation-based puzzle. A hidden permutation $\sigma$ scrambles ${0,\dots,15}$; a query names a (card, property) pair and returns that bit of that card’s hidden value $\sigma(\text{card})$. You stop the instant only one permutation is still consistent with every answer so far. Let $D(16)$ be the $\textbf{fewest number of queries that always suffice}$ even against an adversary who answers every query as unhelpfully as the facts still allow. The question I ask is: what is the exact value of $D(16)$?<br>$\textbf{Information-Theoretic Analysis.}$ Counting sets a floor. There are \(16!\) possible arrangements and each answer is one bit, so no strategy can ever beat $D(16) \ge \lceil \log_2 16! \rceil = 45.$ And the lazy strategy — check all four properties of all sixteen cards — uses $16 \times 4 = 64$. Somewhere in $[45, 64]$ sits the true answer, but where?<br>Formal statement & open conjecture Let $n = 2^k$ and write each value $0 \le i Open conjecture: $D(16) = 46$.<br>Why this problem? The adaptive, sequential nature of the puzzle maps naturally onto how an LLM agent operates: propose a query, observe the answer, update beliefs, repeat. Furthermore, as an independent researcher working under real resource constraints: no GPU clusters, a single MacBook, a finite token budget, I needed a problem where meaningful progress was possible without industrial-scale compute. Computing $D(16)$ fits: it is cleanly stated, objectively verifiable, and sits outside what brute force can reach on a single machine, which makes every algorithmic improvement count. Note that there are many ways to formulate this problem, each...