組み込みエンジニアの現場力養成ドリル（15）
世界で最も難しい2進数パズル ～2進数の世界に住むことの不思議～（1/3 ページ）
今回は、プログラマーであればおなじみの「2進数」をテーマに、レベルチェック問題を幾つか出題します。中には“世界で最も難しい問題”も含まれます。この機会に、2進数の意外な性質や使い方に関する理解を深めてみてはいかがでしょうか？
はじめに
ここ数回は「ユーザーインタフェース」の在り方をテーマに、主に“不親切な駅の案内表示”について取り上げてきました。身近な話題とあって反響も大きく、読者の方から「大阪梅田の地下街はこんなもんじゃない！」といったコメントも寄せていただきました（機会があればぜひ体験してみたいと思います）。本連載で取り上げた京急蒲田駅やJR渋谷駅に負けず劣らずの不親切な案内表示は、日本中にあふれているようです。
2020年の東京オリンピック・パラリンピック開催に向けて、さまざまな駅で案内表示の見直しや増設が進められているようですが、そもそもの“分かりやすい案内表示”の基本思想が、適切な案内表示板がないと即死してしまう先天性方向音痴の筆者と駅担当者とでは全く異なるため、今後、手間とお金をかけて複雑な案内表示が量産される可能性も十分に考えられます。
そうなったらもう、「異国の地で迷うことも旅の喜びである」と感じてくれる寛大な外国人観光客が1人でも多くいることを祈るしかありません……。
12進数、31進数、24進数、60進数、10進数が混在する世界
今回も身近にある“良くないユーザーインタフェース”の続編をお届けしようと思いましたが、さすがに4回連続は重複感、マンネリ感が満載になってしまいます。
そこで、何か面白いネタはないかとWeb検索してみたところ……、本稿を執筆している日（3月14日）がちょうど「円周率の日」であることが分かりました。
確かにその通りですね。試しに米国Yahoo!（ヤフー）にアクセスしてみると、「3月14日15時9分26.53秒に円周率を祝う」というマニアックな人を発見！ どうやってお祝いするのか不思議に思っていたら、ケーキの中央に「Happy Birthday π」と大書し、周囲に円周率を20桁ほどチョコレートで書き、15時9分26秒にロウソクの火を吹き消すのだそうです。
この「3月14日15時9分26.53秒」を見て、筆者は不思議なことに気が付きました。「3月」は12進数、「14日」は31進数、「15時」は24進数、「9分」は60進数、「26秒」も60進数、「0.53」は10進数とバラバラなのです。
厳密には、どれも10進数なのですが、桁上がりのタイミングが異なるので、かなり複雑な形式といえます。特に「日」は、月によっては28進数、29進数、30進数、31進数になり、皆さんもプログラミングの際に「面倒だなぁ」と思っていることでしょう。そう、「面倒だなぁ」はバグの素です。
2進数の世界に住むということ
一方、皆さんが日頃プログラミングで使っている2進数は単純明快ですね。「0」と「1」だけで全ての数、文字、情報を表すのですから。プログラマーは、2進数を避けては通れません。ある意味、プログラマーは「2進数ワールドの住人」といえます。
今回は、どの程度、皆さんが2進数に馴染んでいるかのレベルチェックとして、幾つか問題を出します。中には「世界で最も難しい問題」もあります。解きながら、2進数の意外な性質や使い方をご理解いただければ幸いです。
2進数の特徴をきちんと把握できれば、データの設計（例えば、サイズを2ビットにするか1バイトにするか、形式を文字列にするかビット列にするか、浮動小数点にするかなど）や、処理のアルゴリズムを考える上で選択肢が大きく広がります。意外な処理方式や画期的なアルゴリズムを思い付くこともあるでしょう。では、始めます！
チェックリストと問題
（1）5級のチェックリスト：
（1101）2、（1011）2を見て、瞬時に10進数に変換して「13」「11」と分かる。また、16進数の「D」「B」に変換できる。
（2）3級のチェックリスト：
2の0乗（1）から2の16乗（6万5536）までを10進数で言える。
（3）初段の問題その1：【制限時間1分】
チョコレート工場に、1本10gのチョコレートバーが50ダース（600本）入ったダンボール箱が10個あります（総計6000本）。製造ラインのミスにより、ある1箱だけ、全てのチョコレートバーが9gになってしまいました。重さを正確に計測できるはかりを1回使うだけで、重量不足の箱を特定するにはどう量ればいいでしょうか？
この問題は非常に有名なパズルなので、知っている人も多いと思います。これは「問題その2」のためのウオーミングアップ問題です。
初段の問題その1の解答：
箱に1～10まで番号を付けます。そして、箱1からチョコレートバーを1本、箱2から2本、箱3から3本、……箱10から10本取り出して、それらをはかりの上に載せます。全てのチョコレートが正常ならば、10g＋20g＋30g＋……＋100g＝550gとなります。計量した結果が545gならば5g少ないので、箱5のチョコレートが重量不足であると分かります。
（4）初段の問題その2：【制限時間10分】
上記で、重量不足の箱の個数が不明の場合、どのように計ればいいでしょうか？ 全部の箱が正常だったり、全部が重量不足だったりする場合もあります。はかりを1回だけ使って、重量不足の箱を全て指摘してください。
初段の問題その2の解答
問題その1と同様、箱に1～10まで番号を付けます。そして、箱1からチョコレートバーを1本、箱2から2本（ここまでは「その1」と同じです）、箱3から4本、箱4から8本、……箱10から512本取り出して、それらをはかりに載せます（各箱から、2の累乗の本数を取り出すところがミソです）。全てのチョコレートが正常なら、10g＋20g＋40g＋80g＋……＋5120g＝1万230gとなるはずです。実際に計量して、例えば、1万125gならば105g少ないことになります。105gは、1g＋8g＋32g＋64gの組み合わせしかあり得ませんので、箱1、箱4、箱6、箱7が重量不足であると分かります。
この問題を別の表現で記すと、「幾つかの数字を加算した場合、どの数字を組み合わせた和であるかを1つだけに絞り込みたい。どのような数字の組み合わせにすればいいか？」となります。
箱1から1本、箱2から10本、箱3から100本、箱4から1000本、……箱10から10億本を選んでも構いません。これは10進法の考え方で、全部が正常なチョコレートなら、総重量は111億1111万1110gになるはずです。計量して111億1102万201gなら、9万909g不足していますので、1本取った箱1（全部で9g）、1000本取った箱4（全部で900g）、10万本取った箱6（全部で9万g）の3つの箱が重量不足です。
この10進法方式では、膨大な数のチョコレートバーが必要になります。では、これを最少本数にするにはどうすればいいのでしょうか？ ここで登場するのが2進数です。
各箱を以下のように、20から29まで対応付けます。箱1からチョコレートバーを1本、箱2から2本、箱3から4本、箱4から8本、……箱10から512本を取り出して、それらをはかりに載せます。全てのチョコレートが正常ならば、10g＋20g＋40g＋80g＋……＋5120g＝1万230gとなるはずです。仮に計量結果が1万125gであった場合、105g不足していることになり、この組み合わせは1g＋8g＋32g＋64gとなります。これをビット表現すると、（0001101001）2となり、ビットがONになっている箱（箱1、箱4、箱6、箱7）が重量不足となります。
| 箱の番号 | 箱1 | 箱2 | 箱3 | 箱4 | 箱5 | 箱6 | 箱7 | 箱8 | 箱9 | 箱10 |
|---|---|---|---|---|---|---|---|---|---|---|
| 2進表現 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
| 2進数値 | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 |
| ビットON／OFF | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
この問題は、1個、3個、9個、27個……の3進数でも解けますが、「1箱中のチョコレートバーの数が50ダース」という縛りがあるため、2進法を使わざるを得ませんでした。「最小の数で、数字の和の要素を1つだけに限定できる」ことは、2進数の大きな特徴です。この性質を使ったアルゴリズムは少なくありません。
実はこの問題には「上級バージョン」があります。それは「1箱のチョコレートバーの本数が512より少ない本数でも識別できるか？ 可能であるならば1箱の最少本数は何本か？」です。この解答は本稿の最後に示しますので、ぜひ考えてみてください。これはかなりの難問で、以下の「世界最難関のパズル、5段の問題」よりも難しいと思います。
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をフォロー