カーブデータ

黒マスのない長方形盤面の問題を考える。以下の条件を満たす記号のうち最も形状が簡単なものは何か。

その記号1つだけを表出とするあらゆるサイズの問題を考えたときに、ただ1つのサイズを除いて、解がない。

最小構成と考えられているもの author: CW-MV 掲載20250206出題20250206

この記号1つだけを表出とする場合、5x5サイズのときを除いて、解がない。

5x5より小さいサイズでも解はないし、5x5より大きいサイズに「引っ張って」拡大した解も構成できない。

考察について上記記事より転載。

https://gyazo.com/27a24cdbc84574be8240e7fc90301dd6

author: PinkHoodie 図のような点線を持つとき不適。「引っ張る」ことができる。

https://gyazo.com/5e057fa3d081b7309653e261ff69f09a

author: 三価スニウム 図のような点線:横方向で常に線をまたぎ、縦方向で常に×をまたぐ、を持つとき、縦に「引っ張る」ことができるので不適。この方針で4x4で存在しないことを示せる。

https://gyazo.com/bd17588099f9bebe2142ce7e33584785

中央を通る分割線が横断する辺の両方が✕の場合に、その上の行で横線が発生するかを見る

左上のように横線が発生しない場合は縦線が発生して延長可能になり、右上のようにいずれかの横線が発生する場合は上から下への延長可能な分断線が伸びてくる

これを下半分でも同様に考えれば全体で延長可能な分断線が必ず作れる

よって中央を通る分断線は中央2マスで線をちょうど1本またぐ

対称性から左下の場合を考えると、右下のように二択のいずれにしても延長可能な分断線が作れる

以上より4x4の場合は必ず延長可能

CW-MVによる証明方針

【主張】縦幅4の箱型記号(=外周を四角く全部囲った記号のこと。この問題の記号は幅5の箱型)は縦または横の少なくとも一方向に延長可能(つまり、縦か横幅を長くしても隙間なく埋めることができる)であり、特にそれを示す分割線が引ける(=三価スニウム様のコメントにある必要条件を満たすもの)。

証明方針

反例が有ったとして、その最小の横幅kを取る。2~k-1の任意の整数jに対して、縦j列目の線の通る様子を見る。

もし縦線がない場合、この列の全マスは横線で回収するので、この横線らを全て同じだけ伸ばせば横に延長可能。

また、この列内の縦線がマスを完全に回収している場合、その行の縦線を全て引いた記号(A'と置く)を考える。

A'は引かれた縦線によって二つの箱型記号B,Cに分かれるが、kの最小性よりB,Cは横に延長可能か縦に延長可能。

Bが横に延長可能である場合、A'においても(Bの部分だけを横に延長することで)横に延長可能であり、仮定に反する。

同様の議論がCにも成立し、よってBもCも横に延長可能ではなく、縦に延長可能。(※これだけではAの縦延長可能性は分からない)

以下、そのようなj行目がないA(これを『良い領域』と呼ぶこととする)に対して考える。

このとき、Aはどの縦の行においても縦線で回収していないマスを持つ。

縦幅4であることから、これはAの上から2~3行目の間を横切る縦線が存在しないことを意味する。

これより、Aの上から2行目にある横線と3行目にある横線を繋ぐことで『縦方向で必ず跨ぎ、横方向で絶対に跨がない』分割線が引ける。

これは仮定に矛盾するので、対称性より2行目には横線が無いとしてよい。つまり2行目は全て縦線が入る。

よって良い領域とは、以下の条件を満たす。

◆ 2or3行目にある(外周以外の)線は全て縦線であり、3or2行目にある(外周以外の)線は全て横線である。

あとは良い領域が幾つか横に繋がっている場合を考えればよいのですが、ここでアイデアに詰まりました。

【追記】

正確にはAを分割し続けていって良い領域まで分解した後、その時に引いた余計な縦線を消しても問題ないことを示す必要が有りましたことをここに書き加えます。