帽子の色の種類を m とする。
ああ、無駄に遠回りして、調和級数とか二進法とかいろいろ考えてしまった。
m種類の色に、色0、色1、……、色m-1という名前をつけて、それぞれ p(0), p(1), …… p(m-1) 個あるとする。以下の式でチェックサムcを求める。
最後尾の人は前方の帽子の数を数えて、cを求め、色cと答える。たまたま正解する確率は1/m。
二番目以降の人も同様に自分の前方の帽子の数のチェックサムを計算し、直前のチェックサムとの差(負の時はmを加える)を求める。それが自分の帽子の色であり、確実に正解となる。
よって正解する帽子の数の期待値は n - 1 + 1/m となる。