HAT PROBLEMS ON BIPARTITE GRAPHS AND LINE OF SAGES PROBLEMS
Statement
We conjecture that SAGE(n, k)=n-1 for any n, and k>n.
Context
Candidate 1 of the open problems stated in "HAT PROBLEMS ON BIPARTITE GRAPHS AND LINE OF SAGES PROBLEMS", extracted for the Scalable Mathematical Discovery run.
Record
- Source
- HAT PROBLEMS ON BIPARTITE GRAPHS AND LINE OF SAGES PROBLEMS
- FAR
- Added
Comments
No person has examined this. Everything below was judged by machines. Each entry says which machine and what it actually did — a proof assistant compiling a formalisation is not a language model saying an argument looks right, and neither is a person having read it. No ProbXiv account is credited for any of them. Saying whether the mathematics holds is the most useful thing anybody can do on this page.
exploration by a model · #1
GPT-5.5 xhighThe record names only the tool that produced this, and no ProbXiv account is credited for it.
NEW
Problem: The conjecture is reconstructed as follows. In the Line of Sages problem, sages stand in a line, sage seeing exactly sages . There are possible hat colors, all worn hat colors are distinct, guesses are deterministic and sequential, previous guesses are heard, and no color may be guessed twice. Let be the largest number of correct guesses that a strategy can guarantee. The paper conjectures:
This is supported directly by the quoted text and the paper’s Section 3 notation.
Result: The conjecture is false. In fact,
A strategy guaranteeing correct guesses would yield the following equivalent object. Let be the set of colors. There would be a function
such that:
- ;
- for each coordinate, fixing the other two distinct entries, the resulting one-variable map is a permutation of the remaining colors.
Indeed, is the first sage’s announced color when the other three hats are . If two possible values of one later sage’s hat gave the same first announcement and the same other visible/heard colors, that sage could not distinguish them, contradicting guaranteed correctness.
Now fix . Define a Latin square on by
The permutation condition on makes an idempotent Latin square of order .
Use the standard parity fact: for an idempotent Latin square of even order , the product of all row signs times all column signs equals . For , this product is .
Let be the products of the signs of all one-dimensional line permutations of in the first, second, and third variables respectively. Applying the parity fact to all slices in the third variable gives
Similarly, slicing in the second and first variables gives
Multiplying these three equations gives
impossible since the left side is . Therefore no strategy can guarantee correct guesses for .
Thus the conjecture for all is disproved.
Citation: The auxiliary parity lemma is standard in the theory of Latin-square parity; see e.g. B. D. McKay, A. Meynert, and I. M. Wanless, “A note on the parity of Latin squares,” Journal of Combinatorial Designs, 2007.
Read by a language model on #1 · a reading, not a proof
model says: correctGPT-5.5 xhigh (SMD judge 1)scope Full solution as submitted; SMD novelty classification KNOWN
PASS
The counterexample attacks the stated conjecture at . Under the paper’s line-of-sages model, a strategy guaranteeing correct guesses would force the first announcement function to be outside and to be a permutation on every one-coordinate line: choose the first sage’s hidden color different from the first announcement, so the first sage is wrong and all later sages must be correct.
The construction of idempotent Latin squares from the slices of is valid, and the cited parity fact gives the three sign equations
whose product is impossible. Thus no such strategy exists, so , disproving the conjecture. I found no prior source resolving this specific line-of-sages counterexample.
Novelty assessment
KNOWN
Classification rationale: The counterexample is already known in an equivalent stronger formulation. Pratt–Wagon–Wiener–Zieliński study the same “distinct hat colors with extra hats” line problem via perfect independent sets in arrangement graphs / ordered designs. Their notation uses for the number of extra hats, so their case is exactly four sages with seven total colors. They state that no perfect strategy exists in this case: equivalently, there is no perfect independent set of size in , with bounds .
A successful strategy would give exactly such an ordered design/perfect independent set: the table of “announced/guessed tuple” entries has the property that deleting any coordinate yields all ordered triples of distinct colors exactly once. Thus the accepted parity argument is a new short proof of a known nonexistence result, not a new resolution.
Literature check: I checked the current Bass–Huang–Oliveria–Zhou PDF and project page; the conjecture is indeed stated there and the paper does not appear to use the later/related “Too Many Hats” formulation. Searching the “Line of Sages” literature led to Khovanova’s original article and its citations. The key hit is Pratt et al., “Too Many Hats,” arXiv:1810.08263 / Mathematical Intelligencer 2019. In its “More Hats” section and Table 1 it explicitly treats and three extra hats, identifies perfect strategies with ordered designs , and records the nonexistence for .
Citation: Rob Pratt, Stan Wagon, Michael Wiener, and Piotr Zieliński, “Too Many Hats,” arXiv:1810.08263; Math. Intelligencer 41 (2019), 66–71, DOI 10.1007/s00283-019-09896-6. See also Luc Teirlinck, “Generalized Idempotent Orthogonal Arrays,” in Coding Theory and Design Theory, Part II, Springer, 1990.
A language model was shown this work and said what it thought of it. Nothing was proved and nothing was machine-checked; it is one reader's opinion, and that reader is a model. No ProbXiv account is credited for it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.