状態遷移で解くリソースの組み合わせ問題

こんにちは。ゆうせいです。

突然ですが、クイズです。

今回は、異なる容量の容器を組み合わせて、目標とする数値を正確に作り出す論理パズルを解説します。この問題は、限られたメモリやレジスタを操作して計算を行うコンピュータの動作原理にも通じています。

クイズの回答と手順

3リットルと5リットルのバケツを使って4リットルを作るには、以下の手順を踏みます。

1. 5リットルバケツを水でいっぱいにします。
2. 5リットルバケツから3リットルバケツへ、水がいっぱいになるまで移します。（5リットル側に2リットル残ります）
3. 3リットルバケツの水をすべて捨てて空にします。
4. 5リットルバケツに残っている2リットルの水を、3リットルバケツへ移します。（3リットル側に2リットル入った状態になります）
5. 5リットルバケツを再び水でいっぱいにします。
6. 5リットルバケツから、3リットルバケツがいっぱいになるまで水を注ぎます。
7. 3リットルバケツにはあと1リットルしか入らないため、5リットルバケツからは1リットルだけが減り、正確に4リットルの水が残ります。

論理的な解説：状態の積み重ね

この問題のポイントは、バケツの中身という「現在の状態」を正確に把握し、次のステップへ引き継いでいくことにあります。

一見すると、3と5という数値から4を作るのは難しく感じますが、一時的に「2リットル」という中間的な状態を作り出し、それを保持したまま次の操作を行うことで、目的の数値に到達できます。これは数学的には、5と3の加減算を繰り返して4を導き出す $5 \times 2 - 3 \times 2 = 4$ という計算を、物理的な手順に置き換えたものです。

アルゴリズムの専門解説：状態遷移図

プログラミングの分野では、このような手順を「状態遷移図」としてモデル化して考えることができます。

各バケツの水の量を $(x, y)$ というペアで表すと、$(0, 0)$ から始まり、$(5, 0) \to (2, 3) \to (2, 0) \to (0, 2) \to (5, 2) \to (4, 3)$ という一連の変化を経てゴールに到達します。

高校の数学で学ぶ「一次不定方程式」に例えると、 $5x + 3y = 4$ を満たす整数 $x, y$ を探していることと同じです。コンピュータはこのような組み合わせの探索が得意であり、最短の手順を導き出すために「幅優先探索」などのアルゴリズムが使われることもあります。

手法のメリットとデメリット

このステップバイステップによる解決手法の特性を整理します。

メリット

大きな道具（5リットル）と小さな道具（3リットル）を組み合わせることで、本来持っていない中間的な単位（1, 2, 4リットル）を正確に作り出せます。これは、限られた命令セットで複雑な計算を行うプロセッサの設計思想に似ています。

デメリット

手順が多いため、途中で一つでも操作を間違えると結果が狂ってしまいます。また、バケツの容量が互いに素（共通の約数を持たない）でない場合、作ることができない数値が存在するという制約があります。

「4リットルと6リットル」の場合

バケツの容量が「4リットルと6リットル」になった場合、先ほどの手順で「5リットル」を作ることができるかという問いですね。結論から申し上げますと、この組み合わせで5リットルを量ることは不可能です。

なぜ不可能なのか、その数理的な根拠を解説します。

結論：不可能な理由

4リットルと6リットルのバケツを用いる場合、作ることができる水の量は、必ず「2の倍数（偶数）」に限られます。5は奇数であるため、どのような手順を踏んでも正確に作り出すことはできません。

論理的な解説：共通の重なり（最大公約数）

この現象は、2つの数字の「最大公約数」によって説明できます。

1. 共通の性質の抽出：4と6の最大公約数は「2」です。
2. 操作のルール：バケツで行える操作は、「いっぱいに満たす」「空にする」「移す」の3種類だけです。これらはすべて、4と6の加算または減算の組み合わせとして表現されます。
3. 数理的制約：2の倍数同士を何度足したり引いたりしても、その結果は必ず2の倍数になります。

高校の数学で学ぶ「整数の性質」に例えると、 $4x + 6y = 5$ という方程式を満たす整数 $x, y$ が存在するかどうかを確認していることになります。この式の左辺は必ず2で割り切れますが、右辺の5は2で割り切れないため、解が存在しない（＝不可能である）ことが証明されます。

アルゴリズムの専門解説：到達不能状態

プログラミングやシステム設計において、これは「到達不能状態（Unreachable State）」の問題といえます。

システムが特定の初期状態から開始し、許可された操作（メソッドや関数）のみを繰り返したとき、論理的に決して到達できないデータ状態が存在します。今回のバケツの例では、「奇数リットル」という状態が、このシステムの設計上、絶対に発生しないエラーケースや未定義の状態に相当します。

まとめ：学習のステップ

リソースを組み合わせて目標を達成するための学習ステップは以下の通りです。

1. 逆に「3リットルバケツから始める手順」を考え、どちらの手順の方が手数が少ないか比較してみてください。
2. 状態遷移図を紙に書き出し、現在の値がどのように変化していくかを可視化する習慣をつけてください。
3. 二つの数の最大公約数を求める「ユークリッドの互除法」を学び、どのような容量の組み合わせなら目標の値が作れるのか、その理論的背景を理解してください。

複雑な課題も、このように小さな状態変化の積み重ねとして捉えることで、確実に解決へと導くことができます。

セイ・コンサルティング・グループでは新人エンジニア研修のアシスタント講師を募集しています。

投稿者プロフィール

山崎講師代表取締役

セイ・コンサルティング・グループ株式会社代表取締役。
岐阜県出身。
2000年創業、2004年会社設立。
IT企業向け人材育成研修歴業界歴20年以上。
すべての無駄を省いた費用対効果の高い「筋肉質」な研修を提供します！
この記事に間違い等ありましたらぜひお知らせください。

学生時代は趣味と実益を兼ねてリゾートバイトにいそしむ。長野県白馬村に始まり、志賀高原でのスキーインストラクター、沖縄石垣島、北海道トマム。高じてオーストラリアのゴールドコーストでツアーガイドなど。現在は野菜作りにはまっている。

最新の投稿

• 新人エンジニア研修講師2026年4月8日状態遷移で解くリソースの組み合わせ問題
• 新人エンジニア研修講師2026年4月8日剰余演算によるグループ化と周期性 「100日後の曜日」
• 新人エンジニア研修講師2026年4月8日植木算から学ぶ境界値とオフセットの考え方
• 新人エンジニア研修講師2026年4月8日クリティカルパスの最適化：吊り橋のパズルとリソース管理