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.
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.
Introduction #
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:
- Is this card Red?
- Is this card a King?
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.
Cards: A♥ K♥ A♠ K♠ — two questions (red?, king?). Goal: identify the full arrangement in under 5 queries.
| Pos | Red? | King? |
|---|
[8-card variation](#explore-the-game-yourself)·
[16-card variation](#explore-the-game-yourself)
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:
16-card versionscales the opening 4-card puzzle to 16 cards and then states theopen mathematical question. - The bulk covers the search for optimal strategies: theLLM-agent execution setup, howperformance evolved across fifty iterations, and aplayable browser versionof the game (jump here to see themain result). - I close with
key learnings from the collaborationandconnections to related open conjectureby Donald Knuth that was recently disproved [5].
16-card puzzle
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).
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.)
An open question
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)$?
$\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?
Formal statement & open conjecture #
Let $n = 2^k$ and write each value $0 \le i < n$ as its $k$-bit string $b(i) \in \{0,1\}^k$. A permutation $\pi = (\pi_1,\dots,\pi_n)$ is encoded as the concatenation $E(\pi) = b(\pi_1)\,b(\pi_2)\cdots b(\pi_n) \in \{0,1\}^{nk}.$ A $\textbf{query}$ picks an index $t \in \{1,\dots,nk\}$ and returns the $t$-th bit of $E(\pi)$. Let $D(n)$ be the minimum number of queries that identifies $\pi$ uniquely in the $\textbf{worst case}$ (a query may depend on all previous queries and answers, i.e., queries can be $\textbf{adaptive}$). We know that $45 \leq D(16) \leq 64$. Determine $D(16)$.
**Open conjecture:** $D(16) = 46$.
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 connected to a different body of mathematics: as an adaptive bit-query optimal decision tree; as matchings in a bipartite graph, in turn connected to permanent computations; automorphisms to reduce the state-space size; and strategies around dynamic programming or brute-force traversal. Also, despite it being an open problem, I would classify it under the “attentionless” problems coined by Terence Tao.
The search for optimal strategies #
I approached computing the optimal strategy from two sides. First, the set of strategies I could reason out by hand (each strategy a provable upper bound) but there was only so far I could go by pen and paper. Then I started with the main exploration: an LLM agent, turned loose on the search with a meta-harness, grinding the best-known strategy. This section lays out the results of that exploration. Before any search, it’s worth walking down the ladder of things a careful human would try (I encourage you to try it yourself) – each strategy gives a provable upper bound. The rest of this post is about the exploration of using AI to attempt this puzzle and learnings along the way.
Human-derivable upper bounds #
- $\textbf{Read everything (64 uses).}$ Four properties × sixteen cards. Correct, exploits nothing.
- $\textbf{Skip the last card (60 uses).}$ Identify fifteen cards fully; the sixteenth is whatever’s left. \(15 \times 4 = 60\).
- $\textbf{Recursion (49 uses).}$ Check property 3 on 15 out of the 16 cards and infer the last card’s MSB. That creates two smaller groups of 8 each (15 uses). For each one, check property 2 on all but 1 and infer the last one (7+7 uses). Repeat the same for property 1 among the 4 smaller sub-groups (3+3+3+3 uses), and finally property 0 on one card of each pair across the 8 sub-groups (1+1+$\dots$+1 = 8). For a total of 49 uses.
- $\textbf{Human+computer (47 uses).}$ Here’s an improvement on the previous one. Check the top property of every card as before and split into two sub-problems of 8 cards each. A few different strategies settle that $D(8) = 16$ and use this to complete the 16-card problem in 15+16+16 = 47 queries. - Note that it might seem like entropy splitting (like the game of 20 questions) might be optimal but simple experiments over the 8-card game show that it does not reach optimality. However, variants like entropy splitting with a bias towards unqueried blocks does achieve the optimal bound.
The execution setup
I built a meta-harness and let an LLM agent run the research loop itself: propose an idea, implement it, run it, read the numbers, propose the next idea — across dozens of iterations. Rules and constraints that were integral in this exploration:
- $\textbf{Resource constraints.}$ All experiments were run on a single MacBook with no clusters/GPU farms on tap. A strategy has to earn its keep inside what a single box can spare which, as we’ll see, is exactly what makes the problem so stubborn. The longest runs were big exhaustive searches run unattended over weekends (and then some).
- $\textbf{One idea, one folder.}$ Every attempt (
v1
,v2
, …v50
) is a self-contained directory with its own solver, verifier, and notes. Results are isolated and reproducible; nothing leaks between versions. The failures are kept next to the wins. Only major optimizations and programming efforts spill as dependencies into other directories. - $\textbf{Strategic steers.}$ Initially the agent required directional guidance and manual steer which eventually reduced with appropriate harness guardrails.
Agent performance vs time
Here’s the whole campaign at a glance – we’ll unpack what the numbers mean below. Each point is one idea the agent tried. A solid dot is a proven worst case – an exhaustive minimax search that finished inside the budget. An error bar is a sampled heuristic: the average over 1000 random shuffles, with a whisker up to the worst case actually observed. The bold staircase is the best guaranteed strategy known at each stage – it only steps down when a new method proves it can always do better. The dashed line is the information floor, 45. Hover a point (tap on mobile), or use ← / →.
The shape of the story: the staircase drops fast through the human-reachable strategies (64, 60, 49, 47), then stalls at 46 – where an exact, structured solver finally proves a guarantee. While the heuristics swarm below it on typical shuffles (averaging ~44.5) yet can never promise it. There’s an independent problem of finding strategies that are good on average (but not worst case). But in this case, I focused on the worst case, i.e., guaranteeing that a certain bound suffices.
Explore the game yourself
I built the actual game in the browser so you can try the strategies yourself. Surprisingly – given how large the exhaustive searches were for the 16 card variant – all of them fit inside this single browser tab without noticeable performance issues. Be sure to explore the Learned policy (a small NN distilled from an expert) and the 3+1 quotient decomposition for the 16 card game.
Notes on how to use the interactive game. #
- Use the Non-abstract tab for the card game: drag properties onto cards to ask yes/no questions, or pick a strategy and hit Run. Switch toAbstract for the binary-grid view where rows are cards and columns are properties. I recommend abstract for the 8, 16 card variants. - You can play the game yourself:
How to play (card game). Drag a property chip onto a face-down card to reveal one bit; the counter tracks queries used. When every card is identified, it flips face-up automatically. HitReveal at any time to peek. ChooseGreedy from the Strategy menu and pressRun to watch the algorithm play – use the Speed slider to control pacing. -
How to play (abstract grid). Click any?
cell to probe that property of that card. The consistency count shows how many arrangements still match all answers (computed live as a permanent). When it drops to1, all cards are identified.
- Or look at a strategy in action (the strategies change with the game size):
4 cards (k=2):- Play it yourself– probe by hand. - Optimal (5)– meets the information floor exactly.
8 cards (k=3):- Play it yourself. - Optimal decision tree (16)– provably best; sits right on the floor. - Fixed opening → optimal (16)– six blind, non-adaptive probes, then optimal play. -
Recursion / layer-by-layer (17)– one probe above the floor. #
16 cards (k=4):- Play it yourself. - Exact-permanent greedy– the strongest heuristic (~45 typical, 46 worst). - Learned policy– a neural-net stand-in that imitates greedy. - 3+1 quotient decomposition– the proven 46-query policy. -
*MSB split*– the 47-query idea (solve two 8-card halves). -
*Layer-by-layer*– the ≤49 baseline.
| Pos | Red? | King? |
|---| | # | Red | King | Maj |
|---| | # | Fc | Od | Rd | Mj |
|---| Two things tend to jump out once you play. First, a typical shuffle collapses to a single answer well before 45 queries. It is useful to remember here that the floor is a worst-case promise, not an average. Second, the greedy strategy is eerily good on average yet still trips into 46 on the nastiest shuffles, which is the whole reason “prove 45” is hard and “prove 46” needed a weekend search. I encourage you to try all the different strategies of the 16-card game (despite their complexity, they run in your browser).
Learnings from LLM-assisted solving #
Here are a few learnings from it, each tagged + for an upside or − for a limitation.
The hand-holding fades, and your harness is probably folded into next-gen models or training data. Across the roughly fifty iterations of this project and a year of frontier releases (Anthropic Opus 4.5 through 4.8, OpenAI ChatGPT 5.2 through 5.6), the amount of directional steering the agent needed dropped visibly. Early on I had to nudge it at almost every turn; by the end, the guardrails I had hand-built (one idea per folder, a mandatory sanity check before any long run) were increasingly things the model did on its own. This is partly explained by the context and structured storing of knowledge, but it does feel like the scaffolding you build around a model today is exactly the behaviour that gets absorbed into the next generation, so the harness feels like a temporary crutch, not a long-term asset. - −
The agent will write an evaluation, but rarely proposes one. Trust in a result comes from evaluations and sanity checks, and the agent was reliably willing towritethem but it almost neversuggestedthem. Two of the most important pivots had to come from the top. First, the shift fromsolving exactlytosampling: it took an explicit directive to get the agent to stop chasing exact worst cases everywhere and start reporting distributions over a thousand random shuffles (the error bars in the chart up top). Second, and more telling, it never grasped on its own that an optimal-decision-tree problem is a poor target for machine learning. It threw six independent ML tracks at it (AlphaZero self-play, adaptive MCTS, value- and GNN-distillation, expert iteration); every onematchedthe exact-permanent policy and not onebeatit – even after distilling a 1.1 GB expert into under 1 MB at 90%+ fidelity, it stalled at a ~10% error floor. It was like the network was trying to learn a hash function (ML is probably excellent at the average behaviour but structurally blind to problems that require such an exact global optimum). However, with appropriate contextual steer, some interesting strategies emerged out of this exploration. - +
Language choice stops being a constraint. Writing in a language the user does not know is no longer a real barrier in this research-style loop: if speed is critical it reaches for C++, if memory safety matters most, Rust. This quietly removes a whole class of engineering constraints that normally dictate design choices. This is particularly relevant for exploratory study where with appropriate evaluations and checking, the actual choice of langugage is largely immaterial. - −
Left alone it will explore, but exploration has a cost. Turned loose, the agent tries many things to varying depths and often does eventually arrive at a good answer – but the wandering is expensive. The lower-bound hunt – “can weprove45 is impossible?” – sprawled across more than a dozen versions (v22, v29, v31–v43) of slack certificates and dead-state barriers; the full-game exact solve ran a forward frontier out to 27.85 GB (growing ≈ 2.5× per layer) before conceding the honest framing: this wants a cluster or a genuinely new lemma. Each detour was defensible on its own, yet together they burn real wall-clock and compute. So the question may not always be whether the agentcanget there, but whether it is worth letting it roam to find out. Often the better move is to bring your own line of attack and solve the problemwithit, rather than around it – steered, it is a superb collaborator; unsupervised, an expensive one. - −
Results scale; insights don’t (yet). The agent was good at producing results. Each version came with a clean, measurable “answer”, but it was notably poor at producinginsight. When it abandoned a line of attack (say the dead-state-barrier proofs of v32–v33), it rarely left a transferable lesson behind; more often a vague residue of “this didn’t look promising.” When I compare this with manual research experience, it usually leaves an “experience” behind (something like: X is hard to do in Y, Z reaches fundamental limits, etc.). I suspect this asymmetry has real consequences for research: we may see an explosion of new “results” and problems declared “settled,” alongside a quieter decline in the number of genuinely novel insights a field accumulates. This sentiment is probably better expressed by other mathematicians. - +
Give it a crisp target and it is superhuman. The clearest example of this is the permanent (the exact count of still-consistent permutations to a partial state) which has been a critical primitive for this problem. Computing a permanent is #P-complete in general [7], but at a fixed size (16-card game where $k = 4$) the right algorithms make it tractable, and it is the bottleneck: even a single greedy game fires on the order of a thousand permanent evaluations (for every possible probe, compute 2 permanents). The agent optimised it to be over $1,000\times$ faster over the course of the project – from a Python reference down through C++, hand-written ARM NEON and x86 SSE4.1 vectorised Gray-code Ryser kernels, multiset-DP permanents with component caching, and automorphism-based state canonicalisation. - −
At the frontier, watch for unearned leaps. Especially at the edge of what is known, the agent will make logical jumps that are not fully substantiated. “The gap of one” is the cleanest example: after a handful of attempts failed to close it, the agent was quick to treat $D(16) = 46$ as settled and the +1 gap asstructural. The pattern is real and certified on many sub-games – a universal +1 across every residual boundary the search could reach – but “we couldn’t beat it in a few tries” is not a proof, and the full 45-vs-46 question remains open. Trust the results; verify the leaps.
Related work #
A very closely related problem was originally proposed as a conjecture by Knuth and disproved by Florian Stober and Armin Weiß in 2022 [5].
The problem is for comparison-based sorting (excluding sorts such as radix sort that require no comparisons). Questions ask what is the minimum number of comparisons required to sort a group of $n$ elements. They call this number $S(n)$, and fun puzzles along the way involve showing $S(4) = 5$ and $S(5) = 7$. In general, though, $S(n)$ has no known closed form. The best general algorithm is merge-insertion sort (Ford & Johnson, 1959 [2]), whose comparison count $F(n)$ exactly matches the information-theoretic floor $\lceil \log_2 n! \rceil$ for every $n \le 11$ – which is what might have led Knuth to conjecture it might be optimal for all $n$ [1]. It is not: Manacher [3] showed merge-insertion is beaten for large $n$, and the counting floor itself first falls short at $n = 12$, where $F(12) = 30$ but $\lceil \log_2 12! \rceil = 29$. The smallest genuinely stubborn case was $n = 16$: the floor is $45$, merge-insertion spends $46$, and for decades nobody could prove which was right. Stober and Weiß settled it – $S(16) = 46$ – with an exhaustive bidirectional search on a single workstation, using an incomplete backward search as pruning advice for a complete forward one [5]. (That backward-as-advice trick is the closest thing to a lit exit sign our own $D(16)$ campaign has found; it is exactly what v48
executes.)
Sorting is not (obviously) our problem. It is tempting to reduce one to the other – both identify a hidden permutation of $n$ items through binary, adversarial queries against the very same $\lceil \log_2 n! \rceil$ counting floor. But they reason about different objects. Comparison sorting lives on posets: each comparison refines a partial order, and the adversary’s remaining freedom is the number of linear extensions still consistent with it. Our bit-query game lives on bipartite compatibility: each probe pins one coordinate of one value, and the number of arrangements still consistent is the permanent of a $0/1$ matrix. I could not find a correspondence that carries a bound from one problem to the other – a comparison is not a coordinate reveal, and a permanent is not a count of linear extensions – so the numerical similarity/connection below is, as far as I can tell, two problems related but unrelated at the same time. If anyone can find a real connection between them, I am sure it will make for some insightful new mathematical work.
Here are both sequences against their shared floor. Every $S(n)$ is known; $D(n)$ is settled through $n = 12$, still open for $n = 13, 14, 15$, and conjectured at $n = 16$: n | ⌈log₂ n!⌉ | sorting | bit-query | ||
|---|---|---|---|---|---|
S(n) | gap | D(n) | gap | ||
| 2 | 1 | 1 | 0 | 1 | 0 | | 3 | 3 | 3 | 0 | 3 | 0 | | 4 | 5 | 5 | 0 | 5 | 0 | | 5 | 7 | 7 | 0 | 8 | +1 | | 6 | 10 | 10 | 0 | 11 | +1 | | 7 | 13 | 13 | 0 | 14 | +1 | | 8 | 16 | 16 | 0 | 16 | 0 | | 9 | 19 | 19 | 0 | 20 | +1 | | 10 | 22 | 22 | 0 | 24 | +2 | | 11 | 26 | 26 | 0 | 27 | +1 | | 12 | 29 | 30 | +1 | 31 | +2 | | 13 | 33 | 34 | +1 | ? | ? | | 14 | 37 | 38 | +1 | ? | ? | | 15 | 41 | 42 | +1 | ? | ? | | 16 | 45 | 46 | +1 | ? | ? |
green = a gap above the floor · red = a bit-query gap that *differs* from sorting's. Every settled $D$ gap is red; whether the still-open $n = 16$ entry matches sorting as we conjecture or rather surprisingly, 45 is sufficient is the whole question now.
Read down the columns and the two problems part ways and then meet again. Sorting hugs the floor: $S(n)$ equals $\lceil \log_2 n! \rceil$ for every $n \le 11$, first steps above it at $n = 12$, and famously stalls one probe over at $n = 16$. The bit-query game leaves the floor almost immediately (a $+1$ gap already at $n = 5$) and then wanders, even reaching $+2$ at $n = 10$. But at $n = 8$ the gap snaps back to $0$. In fact the bit-query game hits the floor exactly at every power of two below sixteen ($n = 2, 4, 8$), because $2^k$ values tile the $k$-bit cube with no wasted codewords and nothing is ever half-asked.
The wandering in between is worth a caveat. When **$n$ is not a power of two**, the values ${0, \dots, n-1}$ only partly fill the $k$-bit cube: $2^k - n$ codewords go unused, so the game there is lumpier, far less symmetric, and its gaps are tangled up with that encoding waste rather than with anything fundamental. Those **non-power-of-two gaps therefore say little about the clean powers-of-two cases**: a $+2$ at $n = 10$ signals nothing for $n = 16$. Restricted to the powers of two (2, 4, 8, and 16), the only honest reading of the $D$ column is $0, 0, 0, \, ?$.
While that makes $n = 16$, the next power of two, look like it should land right on the floor at $45$ (the very same “surely it’s tight here” intuition Knuth probably had about sorting). Both intuitions appear to break at sixteen: the best strategy I have found proves the upper bound of $D(16) \leq 46$, one probe above the floor – and *if* that is optimal, it closely echoes the proven $S(16) = 46$. For me, it would be very surprising if $D(16)$ happens to be 45. Anyway, whether this relation is a coincidence, or the shadow of a deeper mathematical connection I simply couldn’t find, is the question this whole exercise left me with.
Summary #
A quick summary of the proble so far. Note that $D(16)$ is the worst case queries to identify a permutation uniquely using bit-queries):
- Proved: $45 \leq D(16) \leq 46$
- Proved: The 3+1 decomposition requires exactly 46 in the worst case.
- Not proved: $D(16)=46$ (alternative open question: whether a fully interleaved 45-query strategy exists).
- Empirical: greedy typically finishes around 45, but this is not a guarantee.
- There are some interesting ML based approaches which approach the problem from an empirical angle (as opposed to provably X questions are required in the worst case).
References #
- D. E. Knuth. The Art of Computer Programming, Vol. 3: Sorting and Searching(2nd ed.), §5.3.1 (minimum-comparison sorting; the merge-insertion conjecture). Addison-Wesley, 1998. - L. R. Ford Jr. and S. M. Johnson. “A tournament problem.”
*The American Mathematical Monthly*66(5): 387–389, 1959.[doi:10.2307/2308750](https://doi.org/10.2307/2308750) - G. K. Manacher. “The Ford–Johnson sorting algorithm is not optimal.”
*Journal of the ACM*26(3): 441–456, 1979.[doi:10.1145/322139.322145](https://doi.org/10.1145/322139.322145) - M. Peczarski. “The Ford–Johnson algorithm still unbeaten for less than 47 elements.”
Information Processing Letters101(3): 126–128, 2007.doi:10.1016/j.ipl.2006.09.001 - F. Stober and A. Weiß. “Lower bounds for sorting 16, 17, and 18 elements.” arXiv:2206.05597, 2022. Proves $S(16) = 46$. arxiv.org/abs/2206.05597 - H. J. Ryser. Combinatorial Mathematics(Carus Mathematical Monographs 14). Mathematical Association of America, 1963. Ryser’s inclusion–exclusion formula for the permanent – used throughout the interactive game to count consistent arrangements. - L. G. Valiant. “The complexity of computing the permanent.” Theoretical Computer Science8(2): 189–201, 1979. Proves computing the permanent is #P-complete.doi:10.1016/0304-3975(79)90044-6