2014/04/06 SGK通信（2014-13）数学で心を読む

2014/04/06
SGK通信（2014-13）数学で心を読む

数学で心を読む
http://www.mathaware.org/mam/2014/calendar/mind-reading.html
Richard Wiseman
James Grime
チェッカー板を１つづつ進むのだが行き先が決まってしまっている．
基礎となる数学
ここで用いた原理はパリティ(偶奇性)拘束．これは，グラフ理論や組み合わせ論に属する数学で，多くの数学の分野’（例えば，代数的トポロジー）などにも係るものです．
オイラーのケーニヒスベルク橋問題の解は，１８世紀のパリティ論の顕著な例，騎士のツアーの問題は，グラフにハミルトン閉路を見つける問題でした．
握手の補題やSpernerの補題のような基本的な組み合わせ論の結果も，パリティ拘束に基づいています．

パリティ拘束が働いている複雑な問題例に、ランプの点灯問題（All Ones Problem)があります．管理人は，朝，博物館中を歩いて，すべての部屋の電燈をオンにする．すべての部屋に電燈ボタンが１つあり、ボタンを押すと，その部屋だけではなく，隣接するすべての部屋の電燈もオン/オフされてしまう．管理人は，博物館内のすべての部屋を点灯することができますか？
驚くべきことに，その答えは博物館のレイアウト（フロアプラン）に依存しない．博物館がいくつの部屋を有するかやレイアウトに依存しない．