Research game 01 · 4–7 min
Signal Club
Local sight. Collective success.
Optional advanced workshop: The pentagon C₅ · two coins per player ↓
Optional advanced workshop · The pentagon C₅ · two coins per player
What is happening? · The idea and the research
Every player receives a hidden bit and sees only the bits indicated by incoming sight lines. The team chooses its rules before testing. A win means all players guessed correctly.
Coordination does not let one player predict an independent fair bit better than chance. It correlates their successes: on the two-player graph, copying makes both right on 00 and 11. On the complete three-player graph, parity gives four winning configurations.
Mathematical model and exact verification
For fixed local rules f, the successful assignments are their fixed points Fix(f). The achieved value is log₂|Fix(f)|, with −∞ for no fixed points. The binary guessing number g(G,2) is the maximum of that value over all admissible rules.
The main game enumerates all 2ⁿ assignments, with n ≤ 3. The optional C₅ workshop separately enumerates 4⁵ = 1,024 two-coin assignments for the chosen local rule. For the main game only (at most three binary players), an independent optimum calculation examines every subset of the at most eight assignments. The C₅ workshop counts the chosen strategy’s wins; it does not search all C₅ strategies. A subset is compatible precisely when no player receives identical visible inputs in two assignments that require different guesses. Every compatible subset extends to local truth tables. Thus the largest compatible subset certifies the optimum, not merely a lower bound.
Independent fair guesses win with probability 2⁻ⁿ. Constant blind rules also succeed on one assignment. Uniform assignments make a strategy’s exact success fraction |Fix(f)| / 2ⁿ. No simulation is used.
Research connection and credits
Søren Riis introduced the information-flow connection. Maximilien Gadouleau and Riis developed the guessing-graph formulation and graph constructions for network coding. The small puzzles here are elementary teaching cases, not their sparse high-guessing-number constructions.
- Riis, Information Flows, Graphs and their Guessing Numbers, Electronic Journal of Combinatorics 14, R44 (2007).
- Gadouleau & Riis, Graph-Theoretical Constructions for Graph Entropy and Network Coding Based Communications, IEEE Transactions on Information Theory 57, 6703–6717 (2011). Earlier preprint.