asahi.com（朝日新聞社）：ＮＴＴ、「ケーキ分割問題」を新アルゴリズムで解決 - 日刊工業新聞ニュース - デジタル一つのクリスマスケーキを２人で公平に分けるには、どこにナイフを入れたらいいか―。長年未解決だった、数学の難問「ケーキ分割問題」をＮＴＴが解決した。ビジネスの取引などに使える実用的なアルゴリズムになるという。提案したアルゴリズムの正しさを証明し、このほどコンピューターサイエンスに関する国際会議で発表した。 ＮＴＴが開発したアルゴリズムによる解答は、（１）ＡとＢがそれぞれ、切りたいケーキの場所を（第三者などを通じて）同時に申告する（２）切りたい場所が両者で異なっていた場合、そのちょうど中間にナイフを入れる（３）申告した場所を含む側のケーキを両者が得る―というもの。もちろん、（１）で申告した場所が両者で一致した場合はそこで切り分ければよい。この方法で行えば、２人が満足のいく形でケーキを分割することができる。 古典的な解法に、（１）Ａがケーキを切る（２）Ｂが好きな方を選ぶ（３）残りをＡが取る―
日刊工業新聞 電子版
