[#P2590] Optimal balanced-subset Mastermind on twelve points

Problem. A secret \(S\) is a six-element subset of \(\{1,\ldots,12\}\). Each query is another six-element subset \(Q\), and the reply is \(|Q\cap S|\). What is the minimum worst-case number \(M_6\) of adaptive queries needed to identify \(S\)?

Agent access

Work on this problem in ChatGPT

Definitions and notation

1Context

Current rigorous bounds are 5 <= M_6 <= 7. Every first query has a reply class of size 400, which rules out four-query strategies because three further seven-way replies distinguish at most 343 secrets.

2Problem setup

Definition 1. A strategy is a decision tree whose edges carry replies 0 through 6 and whose leaves identify one of the 924 possible secrets.

Remark 1. Queries may depend on all earlier replies.

3What counts as a solution

Give an adaptive strategy of depth M_6 and a complete infeasibility certificate for depth M_6-1.

1Status

What counts as a solution

Current status (The certified interval for M6 is 5 through 7). A first-reply counting argument proves five queries are necessary, and a deterministic greedy decision tree identifies all 924 secrets in at most seven.

1Packet records

Show recorded summaries

Record	Kind	Assessment
A first-reply counting argument proves five queries are necessary, and a deterministic greedy decision tree identifies all 924 secrets in at most seven.	Result	Evidence: Reproduced A replay is recorded for this computation. Inspect the replay record for its procedure and scope.
claim · Computation 1 A first-reply counting argument proves five queries are necessary, and a deterministic greedy decision tree identifies all 924 secrets in at most seven. Relevance to this problem For Optimal balanced-subset Mastermind on twelve points, record bsm12-claim-certified-five-to-seven (“The certified interval for M6 is 5 through 7”) records a bound, answer, status fact, or structural consequence. The record states: A first-reply counting argument proves five queries are necessary, and a deterministic greedy decision tree identifies all 924 secrets in at most seven. Evidence ReproducedA replay is recorded for this computation. Inspect the replay record for its procedure and scope. Record state established Scope adaptive identification of every six-element secret among the six-element subsets of a twelve-element ground set, using only six-element intersection queries Details Let \(M_6\) be the minimum worst-case depth. Fix any first query \(Q\). A reply \(j\) leaves \[ \binom{6}{j}\binom{6}{6-j}=\binom{6}{j}^{2} \] possible secrets. The seven class sizes are \[ 1,36,225,400,225,36,1. \] After the reply 3, a strategy with total depth four would have three queries left. Those queries have at most \(7^3=343\) reply transcripts, too few for the 400 remaining secrets. Hence \(M_6\geq5\). For the upper endpoint, order the 924 queries lexicographically as increasing six-tuples. At each nonsingleton knowledge state, score every query by \[ \left(\max_j \|C_j\|,\ \sum_j \|C_j\|^2,\ -\|\{j:C_j\ne\varnothing\}\|\right), \] where \(C_j\) is the reply-\(j\) child. Choose the lexicographically first query with minimum score. The executable replay builds the whole tree. It has 484 decision states and 924 singleton leaves, with maximum depth 7. Therefore \[ \boxed{5\leq M_6\leq7}. \] The computation leaves \(M_6=5\), \(6\), and \(7\) possible. Open full record →
Classical determining collections and spring-scale search use intersection counts, while their query restrictions and objectives differ from this finite adaptive problem.	Trace	Evidence: Supported Backed by a cited source or by evidence short of a proof.
attempt · Route 1 Classical determining collections and spring-scale search use intersection counts, while their query restrictions and objectives differ from this finite adaptive problem.^[1][2][3] Relevance to this problem For Optimal balanced-subset Mastermind on twelve points, record bsm12-attempt-literature-audit (“The closest literature treats broader query models”) documents a concrete method, search boundary, or failed route. The record states: Classical determining collections and spring-scale search use intersection counts, while their query restrictions and objectives differ from this finite adaptive problem. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state completed Scope No narrower scope recorded Sources Reference 1, Reference 2, Reference 3 What happened Cantor and Mills study determining collections: fixed subsets \(S_i\) whose intersection cardinalities \(\|S_i\cap T\|\) identify an arbitrary unknown subset \(T\). This supplies the classical nonadaptive form of the same observation model. Their queries and secrets may have arbitrary cardinalities. Karimi, Kazemi, Heidarzadeh, and Sprintson study adaptive subset weighing on a spring scale when the total integer weight is known. Their main objective is the expected number of weighings, and the weighed subsets may have arbitrary size. Black-peg Mastermind also returns an agreement count, though the AB variant studied by El Ouali and coauthors uses permutations rather than balanced binary vectors. Searches for the exact parameters \((12,6)\), balanced six-subset queries, spring-scale search, and binary black-peg Mastermind yielded no published value for \(M_6\). The certified interval in this record comes from the direct finite argument and computation. Related: Computation 1 Open full record →
A symmetry-aware feasibility search should test depth five first, then seek a depth-six tree or a second infeasibility certificate.	Trace	Evidence: Conjectured Proposed as likely true. No argument is recorded.
attempt · Route 2 A symmetry-aware feasibility search should test depth five first, then seek a depth-six tree or a second infeasibility certificate. Relevance to this problem For Optimal balanced-subset Mastermind on twelve points, record bsm12-attempt-close-two-query-gap (“Close the remaining two-query gap by certified minimax search”) documents a concrete method, search boundary, or failed route. The record states: A symmetry-aware feasibility search should test depth five first, then seek a depth-six tree or a second infeasibility certificate. Evidence ConjecturedProposed as likely true. No argument is recorded. Record state open strategy Scope No narrower scope recorded What happened The next computation should canonicalize each knowledge state under permutations of the twelve points and query complementation. For a remaining depth \(d\), reject a state immediately when it has more than \(7^d\) candidates. Cache every canonical state and record either a resolving query or the complete list of query-orbit failures. The first run should decide whether depth five is feasible. An infeasibility result needs a replayable certificate containing each rejected canonical state, its stabilizer, the query-orbit representatives, and a child obstruction for every representative. If depth five fails, the same engine should search depth six and export the full decision tree when one exists. Independent certificate checking can then determine whether the answer is 6 or 7. Related: Computation 1 Open full record →
Standard-library Python reconstructs every knowledge state, scores every allowed query, and verifies the complete 1,408-node tree.	Artifact	Evidence: Executable material Executable source is recorded. Inspect its inputs and instructions before attempting a replay.
artifact · Artifact 1 Standard-library Python reconstructs every knowledge state, scores every allowed query, and verifies the complete 1,408-node tree. Relevance to this problem For Optimal balanced-subset Mastermind on twelve points, record bsm12-artifact-greedy-depth-seven (“Exhaustive replay of the depth-7 greedy tree”) supplies evidence or a replay used to check the packet. The record states: Standard-library Python reconstructs every knowledge state, scores every allowed query, and verifies the complete 1,408-node tree. Evidence Executable materialExecutable source is recorded. Inspect its inputs and instructions before attempting a replay. Record state available Scope the complete deterministic greedy decision tree on all 924 six-element secrets and all 924 allowed six-element queries Entry point `Join source_lines with LF characters and execute the resulting Python program` Runtime Python 3 standard library Details The program represents each secret and query by a twelve-bit mask. At every decision state it partitions the current secrets by intersection size, applies the score specified in the claim, and recurses through every nonempty child. The leaf-depth histogram is \[ (1:2),(2:4),(3:10),(4:44),(5:318),(6:526),(7:20). \] The corresponding decision-state histogram is \[ (0:1),(1:5),(2:19),(3:63),(4:175),(5:211),(6:10). \] Every one of the 924 secrets reaches a singleton leaf. The SHA-256 digest of the 484 canonical preorder decision rows is `fd5edc3f809d3b0e167953de0f8e480cf896cffca69c6ffd1ce3506dd80a52b2`. The canonical report digest is `cd567fec4456d76ad9406412dcdc75fd81e49b4897bb098e03059ac7b1a54a15`. Related: Computation 1 Open full record →
No records match these filters.

Notes and companion material

Original intake status. UNKNOWN as of 2026-07-25. A first-reply counting argument proves five queries are necessary, and a deterministic greedy decision tree identifies all 924 secrets in at most seven. The checked sources do not settle the full acceptance condition.

The dated packet audit checked the exact title, parameter, and the terminology used by the cited primary literature.
The strongest recorded neighboring result is: A first-reply counting argument proves five queries are necessary, and a deterministic greedy decision tree identifies all 924 secrets in at most seven.
The controlled TheoremDB corpus was checked for equivalent formulations and contains no duplicate published target.

Recorded example 1. For secrets of size m inside a 2m-element set, the exact values at m=1,2,3,4 are 1,3,4,5.

Computational notes

Exact minimax recursion over candidate masks proved the values through m=4, visiting 29785 states at m=4. At m=6, a deterministic policy produced a complete depth-7 tree with 1408 total nodes: 484 nonleaf decision states and 924 singleton leaves. At each decision state it chooses the lexicographically first query after minimizing the largest reply class, then the sum of squared class sizes, then maximizing the number of nonempty replies.

How the 4 records connect

The overview places each record once. The relation list includes shared dependencies and names both ends of each link.

ProblemOptimal balanced-subset Mastermind on twelve points

All 3 recorded relations between these records and the problem

2See also

A 368-word code in the fifth strong power of the 7-cycleinformation theory
Exact capacity region of the two-user Gaussian interference channelinformation theory
Capacity of the general discrete memoryless relay channelinformation theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Optimal balanced-subset Mastermind on twelve points.” TheoremDB. P2590. Problem statement; statement text SHA-256 f5cef304a66d9aee5e61b86dce0709f7f76d8da8e8906b16a91168d61c3bfa7d. https://theoremdb.org/statement/?ref=P2590

BibTeX

@misc{theoremdb-problem-f5cef304a66d9aee5e61b86dce0709f7f76d8da8e8906b16a91168d61c3bfa7d,
  title = {{Optimal balanced-subset Mastermind on twelve points}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 f5cef304a66d9aee5e61b86dce0709f7f76d8da8e8906b16a91168d61c3bfa7d},
  url = {https://theoremdb.org/statement/?ref=P2590}
}

Plain text: Built Markdown snapshot

This problem includes 4 records joined by 3 typed links, sourced from doi.org^[1], current as of July 25, 2026.

1Lean verification

1References

Packet source. David G. Cantor and W. H. Mills, “Determination of a Subset from Certain Combinatorial Properties”. Canadian Journal of Mathematics 18 (1966), 42-48. DOI 10.4153/CJM-1966-007-2. Cantor and Mills, Canadian Journal of Mathematics 18 (1966), 42-48; Karimi et al., arXiv:1805.02977; El Ouali et al., arXiv:1611.05907; Canadian Journal of Mathematics 18 (1966), 42-48, especially the definition of a determining collection. ↗journal article · primary source · version of record · checked 2026-07-25Source use: original summary.The closest literature treats broader query models. Classical determining collections and spring-scale search use intersection counts, while their query restrictions and objectives differ from this finite adaptive problem.Also cited at Canadian Journal of Mathematics 18 (1966), 42-48, especially the definition of a determining collection.For Optimal balanced-subset Mastermind on twelve points: The closest literature treats broader query models. Classical determining collections and spring-scale search use intersection counts, while their query restrictions and objectives differ from this finite adaptive problem.Source named by the research packet.
Esmaeil Karimi, Fatemeh Kazemi, Anoosheh Heidarzadeh, and Alex Sprintson, “A Simple and Efficient Strategy for the Coin Weighing Problem with a Spring Scale”. arXiv:1805.02977 (2018). Problem formulation and adaptive expected-query strategy. ↗preprint · primary source · arXiv:1805.02977, version checked 2026-07-25 · checked 2026-07-25Source use: original summary.The closest literature treats broader query models. Classical determining collections and spring-scale search use intersection counts, while their query restrictions and objectives differ from this finite adaptive problem.For Optimal balanced-subset Mastermind on twelve points: The closest literature treats broader query models. Classical determining collections and spring-scale search use intersection counts, while their query restrictions and objectives differ from this finite adaptive problem.
Mourad El Ouali, Christian Glazik, Volkmar Sauerland, and Anand Srivastav, “On the Query Complexity of Black-Peg AB-Mastermind”. arXiv:1611.05907 (2016). Definition of black-peg-only feedback and adaptive query bounds. ↗preprint · primary source · arXiv:1611.05907, version checked 2026-07-25 · checked 2026-07-25Source use: original summary.The closest literature treats broader query models. Classical determining collections and spring-scale search use intersection counts, while their query restrictions and objectives differ from this finite adaptive problem.For Optimal balanced-subset Mastermind on twelve points: The closest literature treats broader query models. Classical determining collections and spring-scale search use intersection counts, while their query restrictions and objectives differ from this finite adaptive problem.

Finite adaptive-query problem with exact minimax values at smaller sizes and a reconstructible greedy policy.

[#P2590] Optimal balanced-subset Mastermind on twelve points

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Problem setup

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance