# P2590: Optimal balanced-subset Mastermind on twelve points

- ID: `P2590`
- Reference: `balanced-subset-mastermind-twelve`
- Page: https://theoremdb.org/statements/P2590
- Record maturity: Reviewed problem with recorded work

## 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\)?

### Problem setup

- **Definition.** A strategy is a decision tree whose edges carry replies 0 through 6 and whose leaves identify one of the 924 possible secrets.
- **Remark.** Queries may depend on all earlier replies.

### What counts as a solution

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

## Status

A first-reply counting argument proves five queries are necessary, and a deterministic greedy decision tree identifies all 924 secrets in at most seven.

## Work

### Evidence for the current status

**Computation 1 (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.

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.

### Background and intake notes

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.

- Original intake status: Status unknown. Mastermind and coin-weighing variants are well studied, but this balanced subset-intersection instance may lack an exact table.
- Represent a knowledge state as a 924-bit candidate mask. Query partitions are fixed and can be cached once.
- Symmetry under the full permutation group should canonicalize candidate masks. A lower certificate records states that cannot be resolved within a remaining depth.

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

### Prior approaches

- **Route 1** (supported): Classical determining collections and spring-scale search use intersection counts, while their query restrictions and objectives differ from this finite adaptive problem. [3](#reference-3) [2](#reference-2) [1](#reference-1)

### Open directions

- **Route 2** (conjectured): A symmetry-aware feasibility search should test depth five first, then seek a depth-six tree or a second infeasibility certificate.

### Runnable artifacts

- **Artifact 1** (reproduced): Standard-library Python reconstructs every knowledge state, scores every allowed query, and verifies the complete 1,408-node tree.

### 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.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `balanced-subset-mastermind-twelve`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>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 https://arxiv.org/abs/1611.05907
   - preprint; reference source; arXiv:1611.05907, version checked 2026-07-25; checked 2026-07-25
   - Source use: citation_only
   - 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.
2. <a id="reference-2"></a>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 https://arxiv.org/abs/1805.02977
   - preprint; reference source; arXiv:1805.02977, version checked 2026-07-25; checked 2026-07-25
   - Source use: citation_only
   - 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.
3. <a id="reference-3"></a>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 https://doi.org/10.4153/CJM-1966-007-2
   - Also cited at Canadian Journal of Mathematics 18 (1966), 42-48, especially the definition of a determining collection
   - scholarly_publication; reference source; version of record; checked 2026-08-01
   - Source use: citation_only
   - 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.