『高校生からの挑戦状Part28』解答


広島県の中学校1年生 きしょうっち さんからも同様の問題をいただきましたが、こちらに統合しました。
1993バルト海数学団体コンテストの問題の改題だそうです。


◆北海道の高校生 ファージ さんからの解答。

8個の例

○○○○×
○×××○
○○××○
○×○×○
○○○○○
上図の×の部分を消せばいいです。


◆東京都 T.Kobayashi さんからのコメント。

正方形の辺の長さが一般に n の場合はどうなるでしょう?
n = 5 の場合は 12 個除けばできるようです。

o----o----*----*----*----*
|    |    |    |    |    |
|    |    |    |    |    |
*----*----*----o----*----o
|    |    |    |    |    |
|    |    |    |    |    |
o----*----o----o----*----*
|    |    |    |    |    |
|    |    |    |    |    |
*----*----o----*----o----*
|    |    |    |    |    |
|    |    |    |    |    |
*----o----*----*----*----*
|    |    |    |    |    |
|    |    |    |    |    |
*----*----*----o----o----*
('o' が除く部分。)

◆愛知県 Y.M.Ojisan さんからの解答。

【解答】 8個   例を下図に示す。


【7個は不可能の証明】
<定義>
 S:1×1の正方形 16個
 S:2×2の正方形 9個
 S:3×3の正方形 4個
 S:4×4の正方形 1個
 鉄柱:使用できない辺中央縦連続2個の点

 (1)下図に示すように隅のS4個を消すために4点が必須であり、中央の十字線上で使用できる点は最大3個である。


(2)中央の点を使用しない(黒丸で示す)場合でも(1)により鉄柱が1個あり、下図左の状態が何れかの方向で必須である。
すると、下図に示す6個、5個、2個の互いに点を共有しない3組に正方形の一部を分けることができ、それぞれ3点、3点、2点が消去には必要である。
つまりこの場合8点が必要であり、7点で完了するには中央の点を使用する必要がある。


1組が3点必要なことは、各点のSxの共有度をみればよい。青丸点が3個共有する以外は2個以下である。
従って6個の正方形を消すには2点3個+2個では不足である。

(3)中央を使用し、中央十字線上に合計2個以下を使用する場合を考える。
この場合鉄柱が3組かならず登場し、下図左の状態が何れかの方向で必須である。
さて、下図左の左半面で図のようにS4個 S1個を考えると共有度最大は2であるので、3点が必須である。
従って、鉄柱で囲まれたコーナー2箇所のうち何れかは点が1個でなければならず、
コーナーのS3個を消すためには1点しかなく、位置が確定する(緑丸)。
即ち(3-2)の状態である。
さらに(3-3)に示すS1個を消すにために点1個(黄丸)が確定する。
右上コーナーに3点配置すると全体で8点になるので、右上コーナーには2点が最大である。
よって右上コーナーの残されたS1個のために点を使用すると、Sは左側半面の点で消去しなければならなくなる。
(3-4)に示す左半面の点に関わる正方形のうち、S4個、S2個、S1個の合計7個を考えると
共有度は最大2であり、4点が必要である。
よってこの場合も7点では不可能である。


(4−1)中央を使用し、中央十字線上に合計3個を使用する場合のうち、鉄柱が対向配置の場合(下図)を考える。
この場合は直ちに下図に示すように7点では不可能である。
中央十字線に関わらないS8個、S1個を考える。


(4−2)中央を使用し、中央十字線上に合計3個を使用する場合のうち、鉄柱がコーナーを作る配置の場合(下図)を考える。
この場合、コーナー内の点は1点で無ければならず(3)同様、点の位置が決定する。図(4-2-1)
すると図(4-2-2)の状態となり、7点の配置がほぼ決定する。
長丸はどちらかに1点と言う意味である。
1個は図の位置でしか消すチャンスが無い。

よって、図(4-2-3)の黒丸位置の点は使えないことが決定する。
ここで図示のS2個を考えると2点(緑丸)が決定し、
最後に図(4-2-4)の黒S1個が7点では消せなくなる。

以上、7点では不可能であることが分かった。

【感想】 もう少し数学的な方法を目指していましたが、分かりませんでした。


 『高校生からの挑戦状Part28』へ

 数学の部屋へもどる