組み込みエンジニアの現場力養成ドリル（15）
世界で最も難しい2進数パズル ～2進数の世界に住むことの不思議～（2/3 ページ）
（5）5段の問題（世界最難関のパズル）：【制限時間240時間】
アリスとサラの2人と、気まぐれな女王さまが1人います。また、3つの部屋、A、B、Cがあり、アリスはA室、女王さまはB室、サラはC室にいます。B室にはチェス盤があり、8×8のマス目に気まぐれな女王さまがデタラメにポーン（歩）を置きます。全部のマス目にポーンが置いてあったり、1つもなかったりする場合もあります。この状態で以下を実施します。
1．アリスがA室からB室に入ります。
2．気まぐれな女王さまは、チェス盤の8×8のマス目にデタラメにポーン（歩）を並べます。全部のマス目にポーンが置いてあったり、1つもなかったりする場合もあります。
3．女王さまは、「0」から「63」までの数字から1つをランダムに選び、アリスに伝えます。
4．その数字を聞いたアリスは、それをサラに伝えるため、チェス盤に対して、以下のいずれかの操作を1回だけ実施します。
（a）ポーンのないマス目にポーンを置く。
（b）ポーンのあるマス目からポーンを取り除く。
5．アリスはB室を出てA室に戻り、代わってサラがB室に入ります。
6．サラはチェス盤のポーンの配置を見て、女王さまがアリスに言った数字を当てます。
あらかじめ、アリスとサラは、「このようにして、『0』から『63』までの数字をチェス盤で表現するよ」と打ち合わせをしていました。どのように打ち合わせをして、相手に数字を伝えたのでしょうか？
ヒント：コンピュータ的に表現すると、次のようになります。
「64ビットのデータがあり、ビットはランダムにON／OFFになっています。この状態で、1ビットだけON／OFFを反転させて、『0』から『63』までの任意の数字を表すには、どうすればいいでしょうか？」
5段の問題の解答
この問題は「最難解パズル」として、世界のパズルマニアの間で有名な問題です。10日間かけて解ければ世界トップレベルの頭脳を持っていると自信を持ってください。
原題は、IBM ResearchのWebサイトで毎月掲載している論理数学パズル、「Ponder This（これを考えてみよう）」の過去問です。「Ponder This」は、1998年5月から、IBM Researchの以下のWebサイトで出題している論理数学パズルです。
⇒ https://www.research.ibm.com/haifa/ponderthis/index.shtml
このWebサイトには、コンピュータに関連する論理パズルや数学の超難問が毎月1問掲載され、世界の腕自慢が挑戦しています。解答は翌月に掲載され、正解者全員の名前が載ります（毎回、50人程度が正解しますが、日本人の名前は見たことがありません。腕自慢の方はぜひ挑戦してみてください）。
この「チェス盤」の問題も「チョコレートバー」と同様、2進法の応用です。「0」から「63」と聞いて、26＝64と考えた人は鋭い！ 20ビット（＝1）、21ビット（＝2）、22ビット（＝4）、23ビット（＝8）、24ビット（＝16）、25ビット（＝32）を64個のビットでどう表せば、1ビットの反転で「0」から「63」までの任意の数を表現できるのか？
では解答です。「0」から「63」までの数の表し方は以下の通りです（何通りかあり、ここではその一例を示します）。まず、チェス盤を横に分割します。図1の黄色い部分のポーン数（ビットがONの数）が奇数なら、20ビットは「1」、偶数なら「0」、図2の黄色い部分のポーン数が奇数なら21ビットは「1」、偶数なら「0」を表すこととします。図3の22ビットでも同様です。
図1（左） 20ビット（＝1）／図2（中央） 21ビット（＝2）／図3（右） 22ビット（＝4）
次は、チェス盤を縦に分割します。図4の黄色い部分のポーン数が奇数なら、23ビットは「1」、偶数なら「0」、図5の黄色い部分のポーン数が奇数なら24ビットは「1」、偶数なら「0」を表します。図6の25ビットでも同様です。
図4（左） 23ビット（＝8）／図5（中央） 24ビット（＝16）／図6（右） 25ビット（＝32）
以上により、（000000）2から（111111）2まで、「0」から「63」までを表します。この表記法で数字を表すと、ランダムな状態から、1ビットだけON／OFFを反転することで、「0」から「63」までの任意の数字に変換できます。例えば、全てのビットがOFFの場合、0を表すには「7」をON、1を表すには「39」をON、2を表すには「23」をONにすれば表現できます。以下のようなランダムな場合でも同じです。
図7 ランダムな状態
この状態で黄色いマスの数を数えると、20が14個（偶数なので0）、21が13個（奇数なので1）、22が10個（偶数なので0）、23が10個（偶数なので0）、24が11個（奇数なので1）、25が15個（奇数なので1）となります。（110010）2となり、54を表しています。
ただし、現状が54であっても、どんな数字であっても、1ビットを反転するだけで、「0」から「63」までの任意の数になります。例えば、「0」にするには「20」をOFFにし、「1」にしたいなら「52」をONに、「63」にしたいなら「43」をONにすれば変更できます。
Copyright © ITmedia, Inc. All Rights Reserved.
組み込みエンジニアの現場力養成ドリル
このコラムでは、組み込みエンジニアが日々の開発で実際に遭遇する「小さなトラブルを」取り上げ、演習形式で解説します。
この記事の著者
新着ホワイトペーパー PR
-
製品資料
[株式会社 Green AI] AIで脱炭素計画を最適化、初年度からエネルギーコストとCO2を削減する方法 -
市場調査・トレンド
[スマートジャパン編集部] 「ペロブスカイト太陽電池」の普及戦略が公表 政府が目指すコスト・導入量のロードマップを解説 -
市場調査・トレンド
[スマートジャパン編集部] 導入が加速する再エネ・系統向け蓄電システム コスト・収益性の現状分析 -
技術文書・技術解説
[スマートジャパン編集部] いまさら聞けない「ペロブスカイト太陽電池」の基礎知識と政策動向 -
技術文書・技術解説
[スマートジャパン編集部] 「ペロブスカイト太陽電池」の開発動向、日本の投資戦略やコスト目標の見通しは？
関連記事
こんなメディアも見られています
TechFactoryに関連する情報をお探しであれば、こちらのメディアもお役に立てるかもしれません。
特集
- マテリアルズ・インフォマティクスの動向調査
- 研究・開発職のデジタル活用調査
- 設計・解析業務におけるAI活用
- 3Dプリンタ利用動向調査
- CAD利用動向調査
- つながる工場の現状と課題
- 製造業におけるAI開発および活用の実態
- 設計・製造現場における品質管理
ホワイトペーパーランキング PR
-
1
EE Times Japan×EDN Japan 統合電子版：フィジカルAIが生み出す新たな「設計思想」――電子版2026年8月号
-
2
半導体装置メーカー 業績まとめ【2027年3月期第1四半期】
-
3
新入社員に読んで欲しい鉄鋼材料の基礎知識まとめ（Part4）
-
4
一時は時価総額トヨタ超え キオクシア2026年度の動向
-
5
微細配線間の絶縁劣化をどう捉える？ 先端パッケージ評価の最前線
-
6
新入社員に読んで欲しい鉄鋼材料の基礎知識まとめ（Part1）
-
7
EE Times Japan×EDN Japan 統合電子版：2026年上半期の半導体業界を振り返る――電子版2026年7月号
-
8
新入社員に読んで欲しい鉄鋼材料の基礎知識まとめ（Part3）
-
9
CADツールの見直しは本当に必要？ 切り替えの理由と効果を7つの質問で検証
-
10
新入社員に読んで欲しい鉄鋼材料の基礎知識まとめ（Part2）
TechFactory SNS
@techfactory_itmをフォロー
インフォメーション
注目情報をチェック
TechFactoryをフォロー