Can LLMs identify 16 cards in 45 bit-queries?

An LLM agent solved an open combinatorial problem by finding a strategy to identify 16 shuffled cards using only 45 binary property queries, beating the previous best known bound of 50. The agent, built on a frontier model, iteratively improved its query strategy over 50 generations, ultimately discovering a decision tree that always identifies the full permutation in 45 queries in the worst case. The result closes a gap in the literature and provides a playable browser version of the puzzle.

Can an LLM solve this combinatorics problem? 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 version 16-card-puzzle scales the opening 4-card puzzle to 16 cards and then states the open mathematical question an-open-question . - The bulk covers the search for optimal strategies the-search-for-optimal-strategies : the LLM-agent execution setup the-execution-setup , how performance evolved across fifty iterations agent-performance-vs-time , and a playable browser version explore-the-game-yourself of the game jump here to see the main result agent-performance-vs-time . - I close with key learnings from the collaboration learnings-from-llm-assisted-solving and connections to related open conjecture related-work by 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 explore-the-game-yourself 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 to Abstract 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. Hit Reveal at any time to peek. Choose Greedy from the Strategy menu and press Run 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 to 1 , 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 to write them but it almost never suggested them. Two of the most important pivots had to come from the top. First, the shift from solving exactly to sampling : 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 one matched the exact-permanent policy and not one beat it – 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 we prove 45 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 agent can get 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 problem with it, 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 producing insight . 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 as structural . 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 Letters 101 3 : 126–128, 2007. doi:10.1016/j.ipl.2006.09.001 https://doi.org/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 https://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 Science 8 2 : 189–201, 1979. Proves computing the permanent is P-complete. doi:10.1016/0304-3975 79 90044-6 https://doi.org/10.1016/0304-3975 79 90044-6