未解決問題集

この分野の研究をしていると、素朴で具体的な未解決問題が時々出て来ます。中には、既存の道具はあまり役立ちそうになく、プロがやるよりもむしろヒマな学生さん(失礼)とかが挑戦した方が解けそうなものもしばしばあります。そこで、このページでは特に

という条件をすべて満す問題を厳選し、広く江湖のヒマなひと諸賢に供することにしました。もし(部分的にでも)解けたら連絡頂ければ幸いです。

御注意

これはヒマなひと向け問題集です。ヒマでない人がわざわざ取組んだ結果により生じ得る時間的損害について当方では責任を追いかねます。

1. 掃討[H27.5.23]

或る国は碁盤の如く n×n 個の町が道で結ばれている.隣町へは昼間ずっと歩いて至る遠さであり,夜は町に宿らねばならない.

賊が一人どこかに潜んでいる.警吏を幾人か使って捕えたい.但し警吏が賊を捕えるのは,同じ町に居合せるか路上で出会うかしたときである.賊の居場所や今後の逃げ方は全く分らない(警察の策を見抜いているかもしれない).確実に捕えるには警吏を幾人要するか.

現状

元ネタ

次の論文など.

2. 四等分線[H27.5.27]

四等分線

整数 k ≥ 2 に対し,平面 R2 上の互に交らず空でない有界閉集合 PQ 間の k 等分線とは,R2 の空でない部分集合 k−1 個の組 (C1, …, Ck−1) であって各 i = 1, …, k−1 について

Ci = { zR2 : d(z, Ci−1) = d(z, Ci+1) }

を満すものをいう.但し d(z, X) = infxX |zx| は z から X へのユークリッド距離を表し,C0 = PCk = Q である.

与えられた PQ 間の四等分線は一意か.

現状

元ネタ

3. 遮光壁[H27.8.5]解決しました(下記)

正方形の遮光線

平面上の領域 U の遮光壁とは、可算個の線分の合併 BR2 であって,U に交わる任意の直線が B に交わるものをいう.その線分の長さの和(が有限であるときそれ)をこの遮光壁の長さという.例えば右図は単位正方形 U の遮光壁として知られている最短のものであり,その長さは √2+√6/2=2.638… である.なお右図では BU であるが,これは遮光壁の定義で要求されているわけではない.

与えられた U に対し、どこまで短い遮光壁が作れるだろうか.一般に周長 2pな領域 U の遮光壁の長さが p 以上であることは比較的容易である.例えば一辺 1 の正三角形の遮光壁なら最低でも長さ 1.5 以上は必要というわけである.

そこで問題.一辺 1 の正三角形の遮光壁であって長さ 1.5000000000000000001 以下のものはあるか.

[H27.9.12]N大学のIさんから,この問題が解けたという報告を頂きました.

[H28.3.3]解決論文(泉泰介氏)のリンク

現状

元ネタ

4. 線分の警邏[H28.3.3]

巡査が k 人おり各巡査 i は速さ vi で動ける.これを使って線分を警邏し,線分上のどの点にもどの単位時間に一度は誰かが訪れる(ことが永久に保たれる)ようにしたい.明らかな方法としては各巡査 i が長さ vi/2 の担当区間を往復するというもの(按分戦略)がある.これにより合せて長さ (v1 + … + vk)/2 を警邏できる.一方,その 2 倍である v1 + … + vk 以上の長さの線分が警邏できないことは比較的容易にわかる[1].

この「2 倍」という値を下げよ.つまり,1 よりも真に小さい定数 c が存在し,如何なる kv1,…,vk に対しても次が成立つことを示せ.速さ v1,…,vk の巡査がどのように動いても,長さ c(v1 + … + vk) の線分は警邏できない.

現状

元ネタ

ほか、思い出し次第、随時追加します……