One run (show hats & guesses)
—
—
Each vertex i is assigned a hat value xᵢ ∈ {0,…,s−1}. On K5 each player sees all other hats. The (standard) sum strategy is: guess x̂ᵢ = −∑ⱼ≠ᵢ xⱼ (mod s). This succeeds iff ∑ᵢ xᵢ ≡ 0 (mod s), so the success probability is 1/s.
—
—
Estimate success probability by Monte Carlo.
—
Runtime: ready.
| Result | Count | Estimated P |
|---|---|---|
| All correct | — | — |
| At least one wrong | — | — |
Click to expand. Auto-opens the relevant one for the selected graph.
Upper bound (Shannon): In the entropy formulation, K5 imposes H(Xᵢ | X_{V\{i}})=0 for every i. In particular, H(X₅ | X₁,X₂,X₃,X₄)=0, so H(X₁,…,X₅)=H(X₁,…,X₄) ≤ 4·log s. Hence g ≤ 4.
Lower bound (explicit strategy): The sum strategy x̂ᵢ = −∑ⱼ≠ᵢ xⱼ (mod s) succeeds iff ∑ᵢ xᵢ ≡ 0 (mod s), which happens for exactly s⁴ assignments. Therefore g = logₛ(s⁴)=4, and P(success)=s⁴/s⁵=1/s.
Upper bound (Shannon / LP outer bound): For bidirected C5 the constraints are H(Xᵢ | X_{i−1},X_{i+1})=0 (indices mod 5). The standard Shannon outer bound for this system yields H(X₁,…,X₅) ≤ (5/2)·log s, hence g ≤ 2.5.
Lower bound (pairing strategy for s=t²): Write each symbol as a pair (L,R)∈{0,…,t−1}². Each player guesses Lᵢ = R_{left(i)} and Rᵢ = L_{right(i)}. This partitions the 10 coordinates into 5 matched pairs; all guesses are correct iff all 5 matches agree, which occurs with probability 1/t⁵ = 1/s^{2.5}. Thus g = 2.5 for square s=t².