問題（２）

2023/10/13 0:332023/10/31 3:30

⚠️先に問題（１）を解くことをお勧めします.

太郎くんと花子さんはそれぞれ整数を持っています.

この整数は であることが保証されています.（世界中の誰もがが成り立つことを知っていると考えて良いです）

二人は二つの数の大小関係が知りたいです.

ただし太郎くんはの大小関係を花子さんと共有することを除いて（が成立すること以外の） についての情報を花子さん含め他者に一切知られたくありません.

花子さんも同様に, の大小関係を太郎くんと共有することを除いて（が成立すること以外の） についての情報を太郎くん含め他者に一切知られたくありません.

二人の希望を実現するアルゴリズムを考えてください.

難しそうな不等式を簡単に翻訳すると「二人の持っている整数の差は100穣未満」という意味です。（100穣は1000兆と1000兆を掛け合わせた値で、要するにとんでもなく大きい数です）

実はこの100穣という数値に深い意味はなく「二人の持っている数が〇〇以上離れていることは絶対にない」という事実を全員が共有していれば、〇〇に入る具体的な値はいくつでも良いです。

例えば、二人の隠してる値が体重（kg）だった場合を考えてみましょう。

この場合問題の状況は「自分の体重は絶対に誰にも教えたくないけど、相手より重いのか軽いのかだけは知りたい」ということになります。

ここで私やあなたは二人の体重を一切知りませんが、人の体重はどんなに大きく見積もっても1000kgはないので「二人の持っている数が1000以上離れていることは絶対にない」という事実だけは知っていますね。

このように「二人の数の差の上限」だけはバレてしまっていますがそれ以外の情報は一切分からないなかで、誰にも自分の数を教えずにどっちの方が大きいのかだけを知る方法は？というのが本問題になります。