藤原進之介のゼロから始める情報Ⅰ 無料プリント｜慶應義塾大学 SFC 環境情報学部 2019 全15問 解答解説

この設問で使う道具

なぜ情報に権利を設定する必要があるのか。 その理由は、情報が持つ2つの性質から説明できる。

非競合性 — 情報は形のない存在なので、複数の人が同時に使っても減らない。土地や物なら誰かが使えば他の人は使えないが、情報にはその制約がない。物理的に占有するという考え方が当てはまらない。

非排除性 — 一度公開されると、作った側が他人の利用を締め出すことが難しい。塀で囲うこともできず、複製すれば同じものが手に入る。

この2つが揃うと、次の連鎖が起きる。

1. 他人の成果をまねること自体は、新たな進歩や文化の発展にも寄与するので、常に規制すべきものではない

2. しかし、まねが完全に自由なら、作った費用を負担していない者が同じ品質のものをより安く流通させられる

3. すると作る側の意欲が失われる

4. 結果として、社会全体で情報が必要な量より少なくしか作られない状態に陥る

まねを禁じることが目的なのではなく、作る意欲を保つことが目的である。この順序を押さえると、知的財産制度が「保護と利用の両立」を狙う理由が見えてくる。

検算 — 別の道すじで確かめる

語を当てはめ直すのではなく、繰り返しの3箇所すべてで成立するかを確かめる。

主体を表す空欄に「消費」を入れて読むと、「消費費用・開発費用が転嫁されていない」「消費インセンティブが減退する」となる。開発費用を負担するのは作る側であって使う側ではないし、意欲が減退して困るのも作る側である。3箇所のうち2箇所で意味が通らない。

「所有」でも同様で、所有費用という言い方は開発費用と並ばない。繰り返し箇所を全部確認すれば、候補は1つに絞られる。

帰結の空欄も、逆から確かめる。 作る意欲が減退すれば、作られる情報は減る。したがって「過剰」は逆である。もし過剰生産に陥るなら、そもそも制度で保護する必要がない。制度が存在する理由と矛盾する。

模倣の空欄も検査する。 「窃盗」や「諜報」を入れると、それ自体が違法な行為を指すことになる。しかし本文は「常に規制すべきものではなく、原則自由である」と述べている。違法な行為が原則自由であるはずがないので、中立的な語でなければならない。

性質の空欄も対比から確かめる。 有体物は占有できるが情報はできない。両者を分けるのは形の有無である。「精神」や「審美」では、有体物と無体物を分ける基準にならない。

ここで効く一般則・学問的背景

同じ空欄が繰り返し登場したら、そこから埋める。 情報量が最も多く、しかもすべての箇所で成立する語という強い制約がかかる。

知的財産制度の目的は「まねの禁止」ではなく「作る意欲の維持」。 目的と手段を取り違えると、制度の設計思想を誤解する。

非競合性と非排除性は別の性質。 減らないことと、締め出せないこと。両方が揃うことが問題の根にある。

「原則自由」と書かれた行為に、違法性を前提とする語は入らない。 文中の評価と語の含意を照合する。

論の帰結は、直前の因果から導く。 意欲が減退すれば生産は減る。文脈が答えを決める。

情報Ⅱでは、この論点がオープンな共有との緊張関係として扱われる。権利を強めれば作る意欲は保たれるが、その情報を土台にした次の創作が難しくなる。逆に自由を広げれば利用は進むが、作る側の回収が難しくなる。どちらに寄せても失うものがあるという構造の中で、保護期間や例外規定の設計がなされている。制度を「正解」ではなく「調整の産物」として捉える視点が、そこで身につく。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第1章 情報社会の問題解決 に対応します。この設問でつまずいたら，まず該当章を読み直してください。

この設問で使う道具

名誉やプライバシーをめぐる法制度は、誰を規律する法かという観点で整理すると混乱しない。

憲法 — 本来は国家権力を縛る規範である。私生活上の自由が公権力の行使に対して保護されることを定めており、私人どうしの関係には直接には適用されない（民法の規定を通じて間接的に及ぶと考えられている）。「国家に対しては保護しない」という理解は、憲法の性格を逆に取っている。

個人情報保護法 — 事業として個人情報を扱う者を規律する法律である。一般の個人が私生活の中で行う行為は、原則として対象外になる。罰則も限定的で、不注意による公開が直ちに刑事罰につながる仕組みではない。

刑法 — 名誉毀損については、事実を摘示した場合でも罪が成立しうる。真実であることは、それだけでは免責の理由にならない（公共性・公益目的・真実性がすべて揃った場合に限って免責される仕組みになっている）。民事責任だけで刑事罰はない、という理解は誤り。

情報公開法 — 行政文書の開示を請求する制度を定める法律である。自分に関する情報の削除を求める制度ではない。

そのうえで、プライバシー侵害には具体的な損害が必須ではないという重要な考え方がある。任意に提供した情報が適切に管理されるという期待を裏切られた場合、実害が確認できなくても賠償責任が生じうる。

検算 — 別の道すじで確かめる

判定を読み返すのではなく、各法律の性格から逆に確かめる。

個人情報保護法について。 もし個人の私生活上の行為がすべて対象になるなら、友人の連絡先を手帳に書くことすら規律されることになる。規律の範囲が現実的でなくなる。 事業として扱う者に絞られているからこそ、制度として機能する。

名誉毀損について。 もし刑事罰がないとすれば、公然と事実を摘示して他人の社会的評価を落とす行為に対し、金銭の賠償しか対応がないことになる。実際には刑事の規定が置かれている。「事実だから許される」という理解も誤りで、真実性だけでは免責されない。

憲法について。 憲法が私人向けの規範だとすると、国家が私生活に踏み込む場面を誰も止められないことになる。憲法が想定する最も重要な場面が空白になる。 向きが逆であることが、この背理から確認できる。

情報公開法について。 名称は「公開」であり、開示を求める側の制度である。削除を求める権利とは方向が逆になる。名称と内容が食い違っていないかを確かめれば分かる。

正答についても逆から確かめる。 もし具体的な損害が必須なら、情報を渡された側は「実害が出ていない」と言えば責任を免れる。しかし情報が一度出れば回収できず、実害が現れるのは後になってからかもしれない。実害の立証を要件にすると保護が空洞化する。要件を緩めることに合理性がある。

ここで効く一般則・学問的背景

法律は「誰を規律するか」で整理する。 憲法は国家、個人情報保護法は事業者、刑法は個人の行為。対象がずれた記述は誤りである。

憲法は国家権力を縛る規範。私人間には直接適用されない。 この向きを逆にした記述は頻出の誤りである。

名誉毀損は事実を摘示しても成立しうる。 真実であることだけでは免責されない。

法律の名称と内容を対応させる。 「公開」を定める法は、削除を定める法ではない。

プライバシー侵害には具体的な損害が必須ではない。 適切な管理への期待を裏切ること自体が侵害になりうる。

情報Ⅱでは、この考え方がデータを預かる側の責任として実務に接続する。利用者から任意に提供された情報は、提供された目的の範囲で扱うことが期待されている。目的外に流用すれば、実害が出ていなくても期待を裏切ったことになる。「漏れていないから問題ない」では済まないという点が、情報を扱う組織の設計思想を左右する。

本解説は入試問題の解答解説であり、法的な助言ではありません。実際の事案については専門家にご相談ください。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第1章 情報社会の問題解決 に対応します。この設問でつまずいたら，まず該当章を読み直してください。

この設問で使う道具

分散台帳の仕組みを、要素ごとに分解して押さえる。

中央の管理者を置かず、ネットワーク上の端末どうしが直接つながって記録を処理・保持する。この構成が、従来の中央集権的なデータベースとの最大の違いになる。

支える技術は2つある。

電子署名 — 記録が正当な当事者によるものだと確かめる。秘密鍵で署名し、公開鍵で検証する仕組みで、なりすましを防ぐ。

ハッシュポインタ — 前の記録の要約値を次の記録に含める。こうすると、過去のどこか1箇所を書き換えれば、それ以降の要約値がすべて食い違う。改ざんがあれば直ちに露見する構造になる。

この2つを組み合わせると、改ざんの検出が容易なデータ構造ができる。

さらに、同じ記録を多数の端末に持たせることで別の性質が生まれる。一部の端末が停止しても他が保持しているので、使いたいときに使える状態が保たれる。同時に、すべての端末が同じ内容を持つことで記録の同一性も担保される。

この技術が最初に広く知られたのは、中央の発行主体を持たない電子的な通貨の基盤としてであった。

検算 — 別の道すじで確かめる

語を当てはめ直すのではなく、その仕組みを外したら何が失われるかで確かめる。

ハッシュポインタを外した場合。 各記録が独立して並ぶだけになり、過去の1件を書き換えても他に影響しない。書き換えを検出する手がかりが消える。 したがって、この構造が担っているのは改ざんの検出である。

分散保持をやめた場合。 記録は1箇所にしかないので、その端末が停止すれば誰も使えなくなる。改ざんの検出自体は連鎖構造で可能なままだが、使えなくなるという別の問題が生じる。改ざん検出と可用性が別の仕組みに支えられていることが、この対比で確認できる。

最後の空欄に機密性を入れて読むとどうなるか。多数の端末に同じ記録を持たせれば、むしろ多くの参加者が内容を見られる状態になる。分散保持は機密性を高める方向には働かない。 誤りだと分かる。

応用先も逆から確かめる。 前払式の支払手段やデビットカードには発行者や決済機関が存在し、中央で記録を管理している。分散台帳を必要としない。 中央の管理者を置かない仕組みだからこそ、この技術が意味を持つ。

基盤技術も検査する。 人工知能や深層学習を入れると、記録の正当性をどう確かめるのかが説明できない。署名も要約値も、数学的な変換に基づく技術である。

ここで効く一般則・学問的背景

ハッシュポインタの連鎖＝改ざん検出、電子署名＝正当性の確認、分散保持＝可用性。 3つの性質が3つの別々の仕組みに対応する。 どれか1つで全部を説明しようとしない。

「〜を外したら何が失われるか」で役割を特定する。 仕組みと性質の対応が明確になる。

分散して保持することは機密性を高めない。 むしろ見られる範囲は広がる。ここを取り違えやすい。

中央の管理者がいる仕組みには、分散台帳は要らない。 技術が必要になる前提条件を押さえる。

情報Ⅱでは、この技術の限界も論点になる。改ざんが困難なのは記録された後の話であって、最初に誤った内容を記録すれば、それが改ざんされにくい形で残り続ける。また、多数の端末が同じ記録を保持することは、電力や通信の負担を伴う。強固さと引き換えに何を払っているかを見る視点が、技術を評価する際には欠かせない。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第4章 情報通信ネットワークとデータの活用 に対応します。この設問でつまずいたら，まず該当章を読み直してください。

この設問で使う道具

インターネット上の有害な情報への対処には、誰が、どの段階で、利用者の同意を得ているかによって性質の異なる手法がある。

フィルタリング — 利用者やその保護者があらかじめ同意して導入する。閲覧先を制限する仕組みだが、選択したのは利用者側である。

ブロッキング — 接続を仲介する事業者が、利用者の閲覧先を機械的に検知し、対象として登録されたものであれば通信そのものを遮断する。フィルタリングと違い、利用者の同意なく行われる点が決定的に異なる。

この違いが法的な論点を生む。通信の内容や相手を仲介者が把握して遮断する行為は、通信の秘密との緊張関係に立つ。したがって、実施するには相応の正当化が必要になる。

日本では2011年から、接続を仲介する事業者による自主的な措置として、ある特定の類型のサイトに限ってブロッキングが始まった。対象を極めて限定したのは、被害が重大で、かつ違法性の判断に争いが生じにくい類型に絞ることで正当化の余地を確保するためである。

誰が行うかも重要である。国家機関が命じる形ではなく、事業者の自主的な判断として始まった点に、この措置の性格が表れている。

検算 — 別の道すじで確かめる

語を当てはめ直すのではなく、それぞれの主体に実行できるかを検査する。

検索を提供する事業者の場合。 検索結果から特定のサイトを外すことはできる。しかし利用者がアドレスを直接入力すれば到達できてしまう。「閲覧のための通信を遮断する」ことにはならない。

捜査機関や行政機関の場合。 通信設備を保有していないので、自ら遮断することができない。仮に命令を出す立場だとしても、本文は「自主的な措置として」開始したと述べている。命令ではなく自主的な措置という記述と噛み合わない。

接続を仲介する事業者の場合。 利用者の通信はこの事業者を経由するので、閲覧先を検知して遮断できる。技術的に実行可能なのはここだけである。

対象の類型も逆から確かめる。 もし表現の当否に議論の余地がある類型を対象にすれば、何を遮断するかの判断自体が争いになる。同意なく通信を遮断する措置の対象としては正当化が難しい。実際に対象が極めて狭く限定されているのは、この難しさの裏返しである。

手法の名称も対比から検算する。 監視を意味する語を入れると、「監視のための通信を遮断する」という不自然な文になる。隔離を意味する語も、通信を止める動作を直接には表さない。遮断という動作に対応する語でなければならない。

ここで効く一般則・学問的背景

フィルタリングとブロッキングは「同意の有無」で分かれる。 利用者が選ぶか、仲介者が一方的に行うか。この一点が法的な扱いを分ける。

主体を問われたら「技術的に実行できる立場か」を検査する。 遮断できるのは通信を仲介している者だけである。

同意なく行う措置は、対象が狭く限定される。 被害の重大さと違法性の明確さの両方が求められる。限定の狭さ自体が、正当化の難しさを物語っている。

「自主的な措置」という記述は主体を絞る手がかり。 命令する立場と、自ら実行する立場は違う。

動作を表す語は、動詞と対応するかで確かめる。 「遮断する」なら遮断を意味する語が入る。

情報Ⅱでは、この論点が通信の秘密と公共の利益の調整として扱われる。仲介する事業者が通信の内容や相手を把握して遮断する行為は、原則として認められない。それでも一部が実施されているのは、被害の重大さが例外を正当化しうると考えられているからである。対象を広げれば正当化が崩れるという構造上、この措置は本質的に拡大しにくい。技術的に可能であることと、制度的に許されることは別だという典型例になっている。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第1章 情報社会の問題解決 に対応します。この設問でつまずいたら，まず該当章を読み直してください。

この設問で使う道具

何通りを区別できるかと、それを表すのに何ビット要るかは、指数と対数の関係で結ばれる。

$n$ 種類のものを $k$ 個並べる場合、同じものを何度使ってもよく、順序に意味があるなら、組み合わせの総数は

$$n^k$$

になる。各位置が独立に $n$ 通りずつ選べるからである。

「同じものを使ってよい」ことと「順序に意味がある」ことの両方が条件になる。どちらか一方でも欠ければ、この式は使えない。 順序を区別しないなら組み合わせの数え方が変わり、同じものを使えないなら選択肢が1つずつ減っていく。

必要なビット数は、この総数を表しきれる最小の桁数である。

$$2^b\ge （\text{総数}）$$

を満たす最小の $b$ を求める。総数がちょうど2の累乗なら、その指数がそのまま答えになる。

検算 — 別の道すじで確かめる

計算をやり直すのではなく、小さな場合で式を検証する。

2種類の旗を2つ並べる場合を考える。手で書き出すと、同じもの2つが2通り、異なるものの並びが2通りで、合計4通りになる。式では $2^2=4$ で一致する。式の形が正しいことが、数え上げで確認できる。

ビット数も両端で確かめる。 7ビットでは $2^7=128$ 通りしか表せず、256には足りない。9ビットなら512通りで足りるが、8ビットでちょうど収まるので過剰である。足りない側と過剰な側の両方を見れば、最小の桁数が確定する。

条件を外した場合も試す。 もし同じ色を使えないなら、選べる数は $4\times 3\times 2\times 1=24$ 通りになる。順序を区別しないなら、さらに少なくなる。得られる値が大きく変わるので、条件の読み取りが答えを左右することが分かる。

桁数との照合。 総数の解答欄が3桁なので、答えは100以上999以下でなければならない。256はこの範囲に収まる。もし24や1024と計算していれば、桁数が合わずに気づける。

ここで効く一般則・学問的背景

重複を許し順序を区別するなら、総数は（種類）の（個数）乗。 2つの条件が揃っていることを必ず確認する。

$4^4=2^8=256$。 4種類を4つ並べると、ちょうど1バイトに収まる。覚えておくと速い。

必要なビット数は $2^b\ge$ 総数 を満たす最小の $b$。 総数が2の累乗ならその指数がそのまま答えになる。

小さな場合で式を検証する。 2種類2個なら4通り。手で書き出せる規模で確かめれば、式の形の誤りが分かる。

解答欄の桁数を検算に使う。 3桁指定なら答えは100〜999の範囲にある。

情報Ⅱでは、この関係が符号化の効率につながる。256通りを区別するのに8ビット必要というのは、すべての並びが等しく起こる場合の話である。もし特定の並びが頻繁に現れるなら、それに短い符号を割り当てることで平均の長さを8ビット未満にできる。一様なら固定長、偏りがあれば可変長という使い分けが、圧縮の出発点になる。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第3章 コンピュータとプログラミング に対応します。この設問でつまずいたら，まず該当章を読み直してください。

この設問で使う道具

生成規則は、変数を別のものに置き換える手続きの集まりである。変数がすべて具体的な記号に置き換わったとき、その並びが「生成できる列」になる。

記法の意味を整理する。

再帰があるかどうかが決定的である。右辺に自分自身が現れれば、置き換えを何度でも繰り返せるので、無限に多くの列が生成できる。現れなければ有限個で止まる。

本問の要点は、再帰の形が生成される列の形を決めることにある。

ある変数が「記号1・自分自身・記号2」という形に置き換わるなら、置き換えを繰り返すたびに前後に1と2が1つずつ増える。最後に再帰を止める側の選択肢を選べば、真ん中にその記号が残る。

$$\underset{n\text{個}}{\underbrace{1\cdots 1}}◻\underset{n\text{個}}{\underbrace{2\cdots 2}}$$

1と2の個数が必ず等しく、真ん中に停止用の記号が1つだけ入るという形に限られる。

もう一方の変数が「記号1のあとに前の変数」という形なら、上の形の先頭に1が1つ足される。したがって1の個数が2の個数より1つ多くなる。

検算 — 別の道すじで確かめる

一般形を導き直すのではなく、生成できると判定したものを実際に展開して確かめる。

短いほう。 再帰を1度も使わずに停止側を選ぶと、真ん中の記号だけが残る。これに先頭の1を足せば、2文字の列になる。候補と一致する。

次に短いほう。 再帰を1回使うと、前に1、後ろに2が付いた3文字の列になる。これに先頭の1を足せば4文字になる。候補と一致する。

外したものも個別に確かめる。 1と2の個数が同じ候補について、先頭の1を取り除いた残りが再帰の形に合うかを見る。前と後ろに同数の1と2があり、真ん中に停止用の記号が入る形でなければならないが、この候補は前の1が足りない。再帰の途中で止まった形になっており、生成できない。

真ん中の記号が2個ある候補も、再帰の形では真ん中に1個しか置けない。停止側を2度選ぶことはできないので生成できない。

個数の関係を一般形から検算する。 生成できる列では、1の個数から2の個数を引くと必ず1になる。生成できると判定した2つはいずれもこの差が1であり、外した候補はいずれも差が1でないか、そもそも停止用の記号を欠いている。差が1であることが必要条件として機能している。

ここで効く一般則・学問的背景

右辺に自分自身があれば再帰。繰り返し適用できる。 なければ有限個で止まる。再帰の有無が生成できる列の広がりを決める。

「記号A・自分自身・記号B」の形なら、AとBが同数ずつ増える。 前後に同じ回数だけ足されるからである。

一般形を先に求めてから照合する。 候補を1つずつ展開するより速く、確実である。

必要条件を検査に使う。 先頭の記号、停止用の記号の個数、前後の個数の差。1つでも外れれば展開を試すまでもない。

外れる理由が候補ごとに違う。 4種類の落ち方が用意されているので、1つの基準だけで判定しない。

情報Ⅱでは、この仕組みが言語の定義として扱われる。プログラミング言語の文法は、こうした規則の集まりとして定義される。ある文字列がその言語として正しいかどうかは、規則から生成できるかどうかで決まる。同じ個数だけ対応させるという構造は、括弧の対応やタグの入れ子と同じ形であり、単純な照合では扱えない性質として知られている。

📘 この設問は情報Ⅱ「情報システムとプログラミング」の範囲です。『藤原進之介の ゼロから始める情報I』(KADOKAWA) には該当章はありませんが，第3章 コンピュータとプログラミング の内容がそのまま土台になります。先にそこを固めてから取り組んでください。

この設問で使う道具

ペンを進める動作と向きを変える動作を組み合わせ、その並びを繰り返して図形を描く。動作の並びが図形を決めるという考え方で、亀を動かして描く方式として知られる。

図形が閉じるための条件を、2つの軸で押さえる。

角の条件 — 多角形を一周すると、向きの変化の合計はちょうど1回転になる。頂点が $n$ 個の正多角形なら、各頂点で

$$\frac{{360}^{\circ }}{n}$$

だけ向きを変える。したがって、使える回転の組み合わせでこの角度が作れるかが問われる。

本問で使える回転は3種類だけである。何度でも重ねてよいので、作れる角度は

$$30a+45b+72c(a,b,c\text{は0以上の整数})$$

の形に限られる。この形で表せない角度は作れない。

辺の条件 — 進む動作は「1単位」に固定されている。したがってすべての辺の長さは整数でなければならない。辺の比に無理数が含まれる図形は、どれだけ拡大しても整数にそろわない。

角と辺の両方を確認する必要がある。片方だけを見ると判定を誤る。

検算 — 別の道すじで確かめる

判定を見直すのではなく、描ける図形について実際に動作の並びを作れるかで確かめる。

正方形。 1単位進んで90°回転する、を繰り返せばよい。90°は30°を3回重ねても、45°を2回重ねても作れる。4回で一周して閉じる。実際に並びが書ける。

星型。 1単位進んで144°回転する、を繰り返す。144°は72°を2回で作れる。5回で一周し、頂点を1つ飛ばしに結んだ形になる。こちらも並びが書ける。

描けないものについては、作れない理由を数値で示す。 30、45、72をどう足しても36にはならない。0から始めて足せる値は30、45、60、72、75、90…と続き、36が現れることはない。36より小さい正の値は30しかなく、そこから36へは届かない。

辺の条件も逆から確かめる。 もし斜辺を整数にそろえたとすると、他の2辺が $1/\sqrt{2}$ 倍となって無理数になる。どの辺を整数にしても、他が無理数になる。 3辺すべてを整数にできないことが確認できる。

繰り返し回数との整合も見る。 動作セットを10回繰り返す設定だが、正方形は4回で閉じる。5回目以降は同じ線をなぞるだけで、図形は変わらない。閉じた後の繰り返しは結果に影響しないので、閉じるかどうかだけを判定すればよい。

ここで効く一般則・学問的背景

閉じた多角形は、向きの変化の合計が1回転。 正 $n$ 角形なら各頂点で $360/n$ 度回る。

使える回転の和で作れる角度だけが実現できる。 3種類しか使えないなら、その非負整数結合に限られる。

角だけでなく辺も確認する。 進む単位が固定なら、辺の長さは整数に限られる。辺の比に無理数があれば描けない。

「大きさは任意」でも比は変わらない。 拡大縮小で無理数は消せない。

閉じた後の繰り返しは結果を変えない。 同じ線をなぞるだけなので、判定は「閉じるか」に絞ってよい。

情報Ⅱでは、この考え方が手続きによる図形生成として扱われる。少数の基本動作の組み合わせだけで、どこまでの形が作れるか——これは表現できる範囲がどう決まるかという問いである。動作を1つ増やすだけで描ける図形が大きく広がることもあり、道具の設計が表現の幅を決めるという関係が見えてくる。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第3章 コンピュータとプログラミング に対応します。この設問でつまずいたら，まず該当章を読み直してください。

この設問で使う道具

並べ替えてできる文字列を辞書順に並べたとき、ある文字列が何番目に来るかを求める問題である。全部を書き出すのではなく、先頭から桁を確定させながら、前に来るものを数える方法を使う。

手順は次のとおり。

1. 1文字目に注目し、それより小さい文字を置いた場合の並べ方をすべて数える

2. その文字を確定させ、残りの文字で同じことを2文字目について行う

3. 最後まで繰り返し、数えた総数に1を足す

同じ文字が複数ある場合は、並べ方の数え方が変わる。$n$ 個の文字のうち同じものが $k$ 個あるなら、並べ方は

$$\frac{n!}{k!}$$

になる。重複を割り落とさないと、実際より多く数えてしまう。

最後に1を足すのは、自分より前にあるものの個数を数えているからである。前に3つあれば自分は4番目になる。

検算 — 別の道すじで確かめる

数え方を繰り返すのではなく、その付近を実際に書き出して確認する。

先頭3文字を固定すると、残るのは3文字（うち2つが同じ）である。この3文字の並べ方は

$$\frac{3!}{2!}=3\text{通り}$$

しかない。辞書順に並べると、小さい文字を先頭に置いたものが1番目、次が2番目、最後が3番目になる。対象の文字列は2番目に位置する。

先頭3文字より前に来る文字列が存在しないことも確かめる。1文字目に置かれているのは全体で最小の文字であり、2文字目・3文字目もそれぞれ残りの中で最小である。辞書順で最も小さい並びから始まっているので、前に来るものはない。

重複を無視した場合も試す。 残り3文字がすべて異なると誤って数えれば、並べ方を $3!=6$ 通りとしてしまう。すると4桁目で前に来る個数を2と数え、答えが3番目になる。重複を割り落とすかどうかで順位が変わる。

全体の総数とも整合を見る。 全体で360通りある中の2番目なので、極めて先頭に近い。先頭3文字が最小の並びであることと矛盾しない。もし100番台などと出ていれば、どこかで数え違えている。

ここで効く一般則・学問的背景

順位は「前に来るものの個数＋1」。 全部書き出さず、桁ごとに数え上げる。

同じ文字があれば階乗を割り落とす。 $n$ 個中 $k$ 個が同じなら $n!/k!$。割り落とさないと多く数えてしまう。

桁ごとに「残りの中で小さい文字」を探す。 なければ0を加えて次の桁へ進む。

先頭が最小の並びなら、順位は極めて小さい。 求めた値が大きすぎないかを、この感覚で確かめられる。

近くを書き出して検証する。 順位が小さい場合は、周辺を数個書き出せば直接確認できる。

情報Ⅱでは、この数え上げが組み合わせの探索につながる。すべての並びを生成してから探すのではなく、順位から直接その並びを構成する、あるいはその逆をたどる手続きが作れる。全体を展開せずに目的のものだけを扱えるので、対象が膨大でも計算が現実的な範囲に収まる。列挙せずに数えるという発想が、そこで身につく。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第3章 コンピュータとプログラミング に対応します。この設問でつまずいたら，まず該当章を読み直してください。

この設問で使う道具

文字を0と1の列に置き換えることを符号化という。1文字あたり平均で何ビット使うかを平均符号長といい、

$$\text{平均符号長}={\sum }_i{p}_i{\ell }_i$$

で求める。$p_i$ は出現確率、${\ell }_i$ はその文字の符号の長さである。確率で重み付けした平均であって、単純な平均ではない。

出現確率がすべて等しいときだけ、長さの単純平均と一致する。

符号長を短くする原則は1つに尽きる。

出現確率の高い文字に短い符号を、低い文字に長い符号を割り当てる。

これを機械的に実行するのがハフマン符号である。手順は次のとおり。

1. 全文字を重み（出現回数や確率）とともに並べる

2. 最も小さい2つを選んで合体させ、和を新しい重みとする

3. 1つになるまで繰り返す

4. 合体のたびに枝を0と1に分け、根から葉までの枝数がその文字の符号長になる

合体で作った新しい重みの総和が、そのまま「全文字の符号長の総和（重み付き）」になる。これを使うと、木を描かずに答えが出せる。

検算 — 別の道すじで確かめる

3つ目を、まったく別の方法で確かめる。 合体の総和ではなく、木を組み立てて符号長を直接数える。

根の下は、重み6の枝と重み9の枝に分かれる。

• 重み6の側 → 重み3の枝と、比3の文字（長さ2）

– 重み3の枝 → 比1の文字（長さ3）と比2の文字（長さ3）

• 重み9の側 → 重み4の枝と、比5の文字（長さ2）

– 重み4の枝 → 比2の文字（長さ3）と比2の文字（長さ3）

符号長は、長さ2が2文字（比3と比5）、長さ3が4文字（比1・比2・比2・比2）となる。

$$\frac{1·3+2·3+2·3+2·3+3·2+5·2}{15}=\frac{3+6+6+6+6+10}{15}=\frac{37}{15}$$

合体の総和と一致した。

符号として成立するかも確かめる。 長さ $\ell$ の符号が全体に占める割合を足すと1になるはずである（枝が余りなく使い切られている条件）。

$$4\times \frac{1}{2^3}+2\times \frac{1}{2^2}=\frac{1}{2}+\frac{1}{2}=1$$

ちょうど1なので、無駄な枝がなく最適に組めている。

原則との整合。 最も出現の多い文字（比5）と次に多い文字（比3）が長さ2、最も少ない文字（比1）が長さ3になっている。多いものが短いという原則を満たす。

大小関係の確認。 3つ目は6種類あるのに、5種類の2つ目（2.50）より短い。種類が増えたのに平均が縮んだのは、符号を設計し直したためである。1文字を等分に区別するなら ${\log }_{2}6\approx 2.58$ ビット必要なので、2.47はそれより短い。偏りを利用した分だけ得をしていると読める。

ここで効く一般則・学問的背景

平均符号長は確率で重み付けした平均。 単純平均になるのは等確率のときだけである。

出現の多い文字に短い符号。 これが圧縮の唯一の原則である。

ハフマンは「小さい2つを合体」を繰り返すだけ。 合体で生じた新しい重みの総和が、符号長の重み付き総和になる。木を描かずに答えが出る。

比の合計を取り違えない。 1:2:2:2:3 は10、1:2:2:2:3:5 は15。ここを誤ると全部ずれる。

$\sum 2^{-{\ell }_i}=1$ で符号を検査できる。 1未満なら枝が余っており、まだ縮められる。1を超えれば符号として成立しない。

種類が増えても平均は縮みうる。 偏りが大きければ、そのぶん短い符号を活かせる。

情報Ⅱでは、この考え方が圧縮の限界につながる。偏りの大きさは平均情報量として数値化でき、平均符号長はそれを下回れないことが知られている。本問の設定でその値を計算すると2.4付近になり、求めた2.47はごくわずかに上回るだけである。ハフマン符号が理論的な限界にほぼ届いていることが確認できる。整数ビットしか使えない以上、この差は原理的に埋めきれない。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第2章 情報デザイン に対応します。この設問でつまずいたら，まず該当章を読み直してください。

この設問で使う道具

状態遷移図は、いくつかの「状態」と、入力によって状態がどう移るかを矢印で表した図である。今どの状態にいるかだけを覚えておけば、それまでの入力を全部覚えなくても処理が進む。

本問では、2進法の数を上位の桁から1桁ずつ入力し、そこまでの数を割った余りを状態として持つ。

鍵になるのは、桁が1つ増えたときに値がどう変わるかである。2進法で末尾に1桁付け足すことは、

$$(\text{新しい値})=2\times (\text{今までの値})+b$$

を意味する（$b$ は付け足した桁）。10進法で末尾に桁を足すと10倍して足すのと同じ理屈である。

余りだけを見ればよいので、$m$ で割った余りを $r$ とすると、

$$r_{\text{新}}=(2r+b)modm$$

今の余りと今の桁だけで、次の余りが決まる。 元の数の大きさは一切関係しない。これが、桁数がどれだけ多くても状態をたどるだけで余りが分かる理由である。

検算 — 別の道すじで確かめる

状態をもう一度たどるのではなく、まったく別の方法で余りを求める。

2の累乗を3で割った余りは、$1,2,1,2,\dots$ と交互に現れる。下から数えて偶数番目の桁は余り1、奇数番目の桁は余り2、すなわち $-1$ と同じ働きをする。したがって、

下の桁から順に $+1,-1,+1,-1,\dots$ の重みを付けて足した値

が3で割った余りと一致する。

この数は1が3つ並んで0が1つ入る形が6回繰り返される。1が並ぶ3桁は、いずれも上から $-1,+1,-1$ の重みになるので、1組あたり

$$-1+1-1=-1$$

これが6組で $-6$。3の倍数なので余りは0。 状態をたどった結果と一致する。

遷移表そのものも別経路で検算する。 「余り1の数を2倍すると余り2、余り2の数を2倍すると余り4すなわち余り1」——2倍するだけで余りは $1\to 2\to 1$ と入れ替わる。ここに桁の1を足すかどうかで行き先が決まる。表の各行が、この2段階で説明できる。

図の矢印の本数も検算になる。 R0・R1・R2から出る矢印は各2本で計6本、Sから出るのが2本、合わせて8本が実在する遷移である。図には12本あるので、9になるのはちょうど4本。 T3・T10・T11・T12の4本と一致する。

前半の偶奇の例とも整合する。 状態が2つの場合、余り1の数を2倍すると余り0になる。だから入力0では必ず偶数側へ移り、入力1では奇数側へ移る。行き先が今の状態によらないのが2の場合の特徴で、3ではこの単純さが失われる。

ここで効く一般則・学問的背景

桁を1つ足すことは「2倍して足す」。 だから $r_{\text{新}}=(2r+b)modm$。これが遷移表のすべてである。

今の状態だけで次が決まる。 元の数を覚える必要がない。桁数が何万桁でも同じ手間で処理できる。

図を読む前に表を作る。 表にない矢印は9。図から読み取ろうとすると、引っかけの矢印に惑わされる。

出る矢印は1状態につき2本。 本数を数えれば、9がいくつあるかを先に見積もれる。

3で割った余りは、2進法なら交互和。 $2^k$ の余りが $1,2,1,2,\dots$ と交互になるので、$+1,-1$ の重み付き和で求まる。検算に強い。

情報Ⅱでは、この仕組みが有限オートマトンとして扱われる。状態の数だけ記憶を持つ機械で、どこまでの判定ができるか——これが計算の限界を考える出発点になる。「3で割り切れるか」は状態3つで判定できるが、括弧の対応のように深さを数える必要があるものは、状態が有限では扱えない。 何が有限の記憶で済み、何が済まないか。その線引きが見えてくる。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第3章 コンピュータとプログラミング に対応します。この設問でつまずいたら，まず該当章を読み直してください。

この設問で使う道具

平面を2つの領域に分け、与えられた点がどちらに属するかを判定する問題である。判定を式で書くには、次の形にそろえるのが基本になる。

$$f(x,y)\le 0⟹\text{領域A},\text{それ以外}⟹\text{領域B}$$

境界の式を「＝0」の形に移項するのが出発点である。

符号がどちら側を指すかは、代表点を1つ入れて確かめる。 原点や、明らかに領域内にある点を代入すればよい。

本問の解答欄は3つの項の和という形に固定されている。項が足りないときは、残りを0で埋める。選択肢に0が用意されているのはそのためである。

検算 — 別の道すじで確かめる

同じ代表点を入れ直すのではなく、B側の点で不等式が成り立たないことを確かめる。

前半。 Bは直線の下側（右下）である。$(0.5,-0.5)$ を代入すると

$$0.5-(-0.5)+0=1>0$$

成立しない。 指示どおりB側に判定されるので、向きが正しい。

境界上でも確かめる。$(0.5,0.5)$ は直線上の点で、$0.5-0.5+0=0$ となりちょうど0。等号を含むのでAに属する。境界がA側に入るという条件と一致する。

後半。 Bは円の外側である。$(0.9,-0.9)$ を代入すると

$$0.81+0.81-1=0.62>0$$

成立しない。 B側に判定される。

境界上の点 $(1,0)$ では $1+0-1=0$ となり、こちらもちょうど0でAに属する。

符号を逆に取った場合も試す。 もし $-x^2-y^2+1\le 0$ としてしまうと、原点で $1>0$ となってBに判定される。円の内側がBになってしまい、図と食い違う。 符号の取り違えがどこで露見するかが確認できる。

選択肢の作りからも検算になる。 $x$ と $-x$、$x^2$ と $-x^2$、$-1$ と $1$ がすべて対で用意されている。符号を間違えても選択肢は存在してしまうので、代表点による確認を省くと気づけない設計である。

ここで効く一般則・学問的背景

判定式は「＝0」に移項してから作る。 $y=x$ なら $x-y=0$、円なら $x^2+y^2-1=0$。

符号の向きは代表点で決める。 原点や、明らかに領域内にある点を1つ代入するだけでよい。暗記より確実である。

$x^2+y^2-1\le 0$ は円の内側。 中心が原点、半径1のとき。$+1$ にすると内外が逆になる。

枠の数と項の数は一致しない。 足りなければ0で埋める。形式に引きずられて余計な項を作らない。

等号は境界をどちら側に含めるかを決める。 $\le$ なら境界はA側に入る。

情報Ⅱでは、この形が判別のしくみとして繰り返し現れる。データを2つに分けたいとき、$f(x,y)\le 0$ の $f$ をどう選ぶかが問題になる。直線で分けられれば $f$ は1次式で済むが、円のように囲む形が必要なら2次式がいる。分けたい形に応じて式の複雑さが決まるという関係が、学習によって境界を見つける手法の出発点になっている。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第3章 コンピュータとプログラミング に対応します。この設問でつまずいたら，まず該当章を読み直してください。

この設問で使う道具

分類問題は、正解が分かっているデータから境界線を学習し、未知の点がどちらに属するかを判定できるようにする問題である。本問では、境界線を1つの数 $w$ だけで表し、その $w$ を求める。

正解ラベルの符号化が出発点になる。属する領域に応じて $+1$ と $-1$ を割り当てておくと、予測値との差の2乗を足すという形で「どれだけ外れているか」を1つの数にまとめられる。

$$g(w)={\sum }_{i=1}^n(t_i-f(x_i,y_i){)}^2$$

2乗するので、外れの向きに関係なく必ず0以上になる。この値が最小になる $w$ が、最もよく分類できる境界である。

最小値を探す手続きが、後半のアルゴリズムである。

傾きが正なら右が上りなので左へ、負なら右が下りなので右へ動く。どちらの場合も「今の値から傾きの定数倍を引く」という同じ式で書ける。

$$w\leftarrow w-\alpha d$$

$\alpha$ は1歩の大きさで、1より小さい正の値にする。大きすぎると谷を飛び越え、小さすぎると進まない。

検算 — 別の道すじで確かめる

選択肢を選び直すのではなく、式を実際に展開して手続きが成立するかを確かめる。

境界の式を代入すると、外れの合計は

$$g(w)={\sum }_{i=1}^n(t_i+1-y_i-w{x}_i{)}^2$$

となる。$w$ について展開すると $w^2$ の係数は $\sum x_i^2$ で、必ず正である。 したがって $g(w)$ は下に開いた放物線であり、谷底がただ1つ存在する。 最小値を探す手続きが意味を持つことが確認できる。

歩幅の向きも確かめる。 谷底より右にいるとき傾きは正で、$w^{\prime }-\alpha d$ は $w^{\prime }$ より小さくなる。左へ、つまり谷底へ近づく。 左にいるときは傾きが負なので、引き算が加算になって右へ動く。どちら側からでも谷底へ向かう。 符号が逆なら谷から遠ざかるので、引き算であることが必要だと分かる。

切片の条件を別の点で確かめる。 選んだ式に $x=0,y=1$ を代入すると $-1+0+1=0$ となり、$w$ によらず0。点 $(0,1)$ は常に境界線上にあり、切片が1で固定されている。定数を $+1$ にした候補では同じ点で $2$ となり、境界を通らない。

ここで効く一般則・学問的背景

「切片が1」は、$y$ について解いて定数項を見る。 $w$ が $y$ に掛かっていれば切片が $w$ 依存になるので、その時点で除外できる。

ラベルは $+1$ と $-1$ で符号化する。 差の2乗和が対称になり、境界が $f=0$ の位置に定まる。

最小値探しは「傾きと逆向きに少し動く」。 $w\leftarrow w-\alpha d$。傾きの符号がどちらでも同じ式で谷底へ向かう。

歩幅 $\alpha$ は1より小さくとる。 大きすぎれば飛び越え、小さすぎれば進まない。

最小にしたい関数と、境界を表す関数を混同しない。 傾きを取る対象は前者。$w^2$ の係数が正なら谷底は1つで、収束の根拠になる。

情報Ⅱでは、この手続きが機械学習の基本形として扱われる。パラメータが1つなら谷は1つだが、増えると谷が複数現れ、出発点によって行き着く先が変わる。 歩幅や初期値が結果を左右するのはこのためで、本問はその仕組みを最も単純な形で見せている。

📘 この設問は情報Ⅱ「情報とデータサイエンス」の範囲です。『藤原進之介の ゼロから始める情報I』(KADOKAWA) には該当章はありませんが，第4章 情報通信ネットワークとデータの活用 の内容がそのまま土台になります。先にそこを固めてから取り組んでください。

この設問で使う道具

ハミング数とは、素因数が5以下しかない正の整数、すなわち

$$2^a{3}^b{5}^c(a,b,c\text{は0以上の整数})$$

の形で表せる数である。$a=b=c=0$ のとき1になるので、1もハミング数である。

7以上の素因数を1つでも含めば除外される。$7,11,13,14,21,22$ などが該当する。

この問題の要点は、数え上げの方針にある。

生成方式の要は、新しいハミング数は必ず既存のハミング数の2倍・3倍・5倍のいずれかである、という性質である。

$2^a{3}^b{5}^c$ で指数のどれかが1以上なら、その分を1つ減らした数もハミング数であり、それを2倍・3倍・5倍すれば元に戻る。だから候補の外にハミング数が現れることはない。

同じ数が複数の経路から作られる（たとえば6は $2\times 3$ とも $3\times 2$ とも作れる）ので、重複を消す処理が必要になる。表で斜線を引くのは、この重複消去にあたる。

検算 — 別の道すじで確かめる

順に数え直すのではなく、36以下のハミング数を、指数で系統的に分類して総数を求める。

5の指数で場合分けする。

$$14+5+1=20$$

36以下にちょうど20個。 そして36自身がハミング数なので、36が20番目である。順に並べた結果と一致する。

上限を1つ下げても確かめる。 35以下で数えると、36が抜けるので19個になる。19番目が32、20番目が36という並びと矛盾しない。

表の手順とも突き合わせる。 問題文の2つ目の表では、1行目に1〜6が並び、2〜4行目に8から30までの倍数が書き込まれている。手順を続けると、斜線のない最小の数は8、次は9、その次は10……と進む。この順序は、上で並べた7番目以降と一致する。

しらみつぶしとの比較で妥当性を見る。 1から36まで36個を調べて20個が当たりだから、この範囲では当たりが半分以上ある。しかし10000番目は18桁の数であり、そこまでの整数の中でハミング数はごくわずかしかない。範囲を広げるほど当たりの割合が急激に下がるので、生成方式が有利になる。問題文が10000番目の値を示したのは、この差を示すためである。

ここで効く一般則・学問的背景

ハミング数は $2^a{3}^b{5}^c$。1もハミング数（指数がすべて0）。7以上の素因数を含めば除外される。

新しいハミング数は、既存のハミング数の2倍・3倍・5倍のどれか。 だから候補を漏らさず作れる。

複数の経路から同じ数が作られるので、重複消去が必須。 これが手順の中心にある。

個数を数えるときは、大きい素因数から場合分けする。 5の指数で分け、その中で3、さらに2。漏れも重複も出ない。

「$N$ 以下にちょうど $k$ 個あり、$N$ 自身も該当する」なら $N$ が $k$ 番目。 順に並べるのとは独立した検算になる。

候補が疎になるほど、しらみつぶしは不利になる。 生成方式との差は範囲が広がるほど開く。

情報Ⅱでは、この手順が複数の列を併合する考え方として整理される。2倍の列、3倍の列、5倍の列という3つの増加列があり、そこから常に最小のものを取り出して並べていく。同じ値が複数の列に現れたらまとめて1つ進める——これが斜線の正体である。すでに整列された列を突き合わせるだけなので、全体を並べ替える必要がない。部分的な順序を利用して全体の順序を作るという発想が、ここで身につく。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第3章 コンピュータとプログラミング に対応します。この設問でつまずいたら，まず該当章を読み直してください。

この設問で使う道具

ハミング数を小さい順に作る手続きを、3本の指し示す位置（ポインタ）で実現する。

考え方はこうである。すでに求まった列 $h_1,h_2,\dots$ に対し、次に来るハミング数の候補は

$$2h_p,3h_q,5h_r$$

の3つしかない。$p,q,r$ は「その倍率で次に使うべき位置」を指している。この3つの最小値が、次のハミング数になる。

位置を進める規則が要点である。最小値を採用したあと、

採用された値と一致する候補の位置だけを1つ進める。

同じ値が2つの候補で同時に起きることがある（たとえば6は $2\times 3$ とも $3\times 2$ とも作れる）。このとき両方の位置を進めることで、同じ数を二度出すことを防ぐ。表で斜線を2か所に引くのは、この処理にあたる。

進めるのは「一致した候補」だけである。一致していない候補を進めると、その倍率で作れる数を飛ばしてしまう。

検算 — 別の道すじで確かめる

選択肢を選び直すのではなく、手続きを最初から数手動かして、既知の並びと一致するかを見る。

$p=q=r=1$、$h_1=1$ から始める。

出てきた並びは $1,2,3,4,5,6,8,9,10$ で、ハミング数の小さい順と完全に一致する。 7が飛ばされていることも確認できる。

同時成立の効果が2か所で現れている。 $n=6$ では $p$ と $q$ が同時に進み、$n=9$ では $p$ と $r$ が同時に進んだ。片方だけ進めていたら、6や10が二度出ていた。

誤った選択肢で動かすとどうなるかも見る。 (3)のように倍率を消すと、$n=2$ の時点で $h_2$ を求める根拠が失われる。候補が $h_p,h_q,h_r$ となり、すべて1のままで列が進まない。 手続きが止まることで誤りが露見する。

位置と $n$ の関係も確認する。 上の表では常に $p,q,r$ はいずれも $n$ より小さい位置を指している。まだ確定していない値を参照していないので、手続きとして矛盾がない。もし位置が $n$ に追いつけば、未確定の値を使うことになって破綻する。

ここで効く一般則・学問的背景

次の候補は「既存の各要素を2倍・3倍・5倍したもの」に限られる。 だから3つの位置だけで全体を作れる。

採用した値と一致する候補の位置だけを進める。 一致していない位置を進めると、その倍率の数を取りこぼす。

複数の条件が同時に真になりうる。 これが重複消去の仕組みそのものである。「もし〜ならば」を並列に3つ置く書き方には意味がある。

倍率の掛かる向きを確認する。 候補の側に掛ける。求まった値の側に掛けると大小が逆転する。

手続きは数手動かして既知の並びと照合する。 選択肢を眺めるより確実で速い。

情報Ⅱでは、この手続きが整列済みの列を突き合わせる考え方として整理される。すでに順序が付いた複数の列から常に最小を取り出せば、全体を並べ替えなくても順序が保たれる。部分的な順序を組み合わせて全体の順序を作るという発想は、大きなデータを扱うときの基本になる。全部をいちど並べ替える方式に比べ、必要な作業量が桁違いに小さくなる。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第3章 コンピュータとプログラミング に対応します。この設問でつまずいたら，まず該当章を読み直してください。

この設問で使う道具

アルゴリズムが正しいことの証明を穴埋めでたどる問題である。道具は2つ。

背理法。 求めたい性質が成り立たないと仮定して矛盾を導く。ここでは「列に含まれないハミング数がある」と仮定する。

最小の反例を取る。 反例があるなら最も小さいものを選べる。するとそれより小さいハミング数はすべて列に含まれている——これが決定的に効く。

$h^{\prime }=2^i{3}^j{5}^k$ と書けるとき、指数を1つ減らした

$$\frac{h^{\prime }}{2}=2^{i-1}{3}^j{5}^k$$

もハミング数で、$h^{\prime }$ より小さい。最小性から、これは列に含まれている。 ここから「では $h^{\prime }$ 自身も列に入っていたはずだ」と押し返すのが証明の骨格である。

指数が正であることが前提になる。$h^{\prime }=1$ では減らせないので、最初に $h^{\prime }>1$ を確かめる。

検算 — 別の道すじで確かめる

証明を読み返すのではなく、具体的な数で流れを追う。

$h^{\prime }=12$ が列に無いと仮定する。$12=2^2·3$ なので $i=2>0$。指数を1つ減らすと $h^{″}=6$ で、6は列にある（$6=h_6$、$s=6$）。位置 $p$ が6を指したとき候補は $2h_6=12$。$h^{\prime }$ が候補として現れ、仮定が崩れる。

指数を増やす選択肢も試す。 $h^{″}=2^{i+1}{3}^j{5}^k=24$ は $h^{\prime }=12$ より大きく、列にある保証がない。そこから先へ進めない。

4つ目を具体例で。 $n=10$ で $h_{10}=12=2h_6$ が採用され、$p$ は6→7。$p^{\prime }=7$ なら採用時の位置は $p^{\prime }-1=6$ で $h_{10}=2h_{p^{\prime }-1}$。$2h_{p^{\prime }}=2h_7=16$ なので $12<16$ もつながる。

5つ目を具体例で。 $n=8$ では $h_8=9$、候補は $2h_p=10,3h_q=9,5h_r=10$。$2h_p$ は最小でないので $p$ は進まず $p^{\prime }=5$。

$$h_8=9<2h_{p^{\prime }}=2h_5=10$$

成り立つ。 ここで $2h_{p^{\prime }-1}=2h_4=8$ を使うと $9<8$ で偽になる。 4つ目と5つ目が別の式でなければならないことが、この1例で確認できる。

ここで効く一般則・学問的背景

背理法では「最小の反例」を取る。 それより小さいものはすべて性質を満たす、という強い情報が手に入る。

指数を1つ減らせば、より小さいハミング数になる。 向きを間違えると最小性が使えない。

「$p$ が1増える」の直後は $p^{\prime }-1$、増えなければ $p^{\prime }$。 更新の前後どちらの値かを常に確認する。

同じ量を両側に置く不等式は成り立たない。 $X<2h_{p^{\prime }}$ の形が与えられていれば $X=2h_{p^{\prime }}$ は選べない。選択肢の絞り込みに直接使える。

証明は具体例で追う。 小さい数を1つ入れて流れをなぞれば、向きの誤りはすぐ露見する。

情報Ⅱでは、こうした議論がアルゴリズムの正当性として扱われる。動かして正しく見えることと、正しいことの証明は別である。「出力がすべて条件を満たす」ことと「条件を満たすものがすべて出力される」ことは別々に示す必要がある。 本問が前半をひと言で済ませ後半に紙数を割いているのは、漏れがないことの証明が常に難所だからである。

📕 『藤原進之介の ゼロから始める情報I』(KADOKAWA) 第3章 コンピュータとプログラミング に対応します。この設問でつまずいたら，まず該当章を読み直してください。