あの人の誕生日を(数学的に)上手く聞き出したい！！！！

今日12/13は、実は私の誕生日です。ということで、誕生日関連の記事を書いてみたいと思います。

誕生日を知りたい！！

皆さんは、知り合いの誰かの誕生日を知りたいと思ったことがありませんか？そんな時に、普通に何月何日か聞くのはちょっと味気ないかも知れません。そこで、ちょっと変わった方法で誕生日を聞き出す方法を提案してみたいと思います。

その1 二部探索を用いた方法

競プロをやっている人ならおそらく聞いたことがある方法。候補を半分ずつに絞って特定する方法です。候補がn個の場合、log_2(n)回くらいのYesかNoで答えられる質問で特定できます。

例

B君は1以上8以下の整数を思い浮かべている。A君はB君の思い浮かべている整数を以下のようにして特定した。

A:5以上？
B:Yes
A:7以上？
B:No
A:6以上？
B :Yes
A:思い浮かべているのは6ですね？
B:Yes

誕生日への応用

相手の誕生日は閏年を考えると366通りあります。2^8(=256)<366<2^9(=512) なので、二部探索を行うと9回の質問で特定できます。1年の最初から数えて何日目がどの日に対応するかをまとめた表を用意しておいて二部探索を行うと良いでしょう。

例

誕生日が12/13の場合の例です
7/2以降？→Yes
10/1以降？→Yes
11/16以降？→Yes
12/9以降？→Yes
12/21以降？→No
12/15以降？→No
12/12以降？→Yes
12/13以降？→Yes
12/14以降？→No
12/13ですね？→Yes

その2 中国剰余定理を用いた方法

中国剰余定理とは

整数が2個の場合は次のような定理です。

与えられた二つの整数 m, n が互いに素ならば、任意の整数 a, b に対し、連立合同式
x ≡ a (mod m)
x ≡ b (mod n)
を満たす整数 x が mn を法として一意に存在する。このときのxの値は、mu + nv = 1となる整数u,vを用いて、x = anv + bmuで求められる。

証明は割愛します。中国剰余定理で検索すれば出てくるので調べてみてください。

誕生日への応用

a,bをそれぞれ相手の誕生月,誕生日として、m=12,n=31とした場合を考えれば良いです。12u+31v=1となる整数u,vの組はu=-18,v=7などが存在するので、x≡217a-216b(mod 372)と求められます。マイナスを消すために右辺に372bを足してx≡217a+156b(mod 372)とも表せます。
したがって、次のようにすれば誕生日を当てられます。

1. 相手に電卓などを用意してもらう

2. (誕生月×217)+(誕生日×156)を計算してもらい、計算結果を聞く

3. 計算結果を12,31で割った余りがそれぞれ誕生日、誕生月になっている(誕生月が0になった場合は12月、誕生日が31になった場合は31日)

例

実際に12/13で計算してみると計算結果は4632となり、12で割ると余り0、31で割ると余り13となり、上手く特定できていることがわかります。
普通の電卓で余りを求めるのは難しいですが、可能であれば計算結果を372で割った余りを聞いてみても良いかも知れません。同じ計算で誕生日を特定できます。
よくわからない計算をしたら誕生日が当てられるの、相手は不思議に感じるのでは無いでしょうか？

計算を減らしてあげたい場合

3桁×2桁の掛け算2回は辛いかも知れないと思ったなら、x≡217a-216b(mod 372)であることを用いて掛け算を1回に減らすこともできます。相手にはa-bを計算して216倍させた後、aを足して貰えば良いです。ただし、この場合は計算結果が負の数になるかもしれないので余りの計算には気をつけましょう。

終わりに

今回は数学的に相手の誕生日を特定する方法を紹介してみました。機会があればぜひ使ってみてください。最後まで読んで頂きありがとうございました。