ヒマなひと向け未解決問題集
この分野の研究をしていると、素朴で具体的な未解決問題が時々出て来ます。中には、既存の道具はあまり役立ちそうになく、プロがやるよりもむしろヒマな学生(失礼)とかが挑戦した方が解けそうなものもしばしばあります。そこで、このページでは特に
- はっきりと意味が定まる数学的な問題である
- 高校数学までで意味がわかる(ような形に書ける)し、解けるとしても特段の知識は使いそうにない
- 既に発表された文献で論ぜられており、それなりに背景がある(もし解けたら論文が書ける)
- とはいえ、今の人類に歯が立たない可能性の高い有名な難問(と同等)だったりはしない
- 河村が少くとも数日考えてみたが解けてない
という条件をすべて満す問題を厳選し、広く江湖のヒマなひと諸賢に供することにしました。もし(部分的にでも)解けたら連絡頂ければ幸いです。
H27.5 河村(広域システム系・情報図形部会)
1. 掃討[H27.5.23]
或る国は碁盤の如く n×n 個の町が道で結ばれている.隣町へは昼間ずっと歩いて至る遠さであり,夜は町に宿らねばならない.
賊が一人どこかに潜んでいる.警吏を幾人か使って捕えたい.但し警吏が賊を捕えるのは,夜に同じ町に居合せるか昼に路上で出会うかしたときである.賊の居場所や今後の逃げ方は全く分らない(警察の策を見抜いているかもしれない).確実に捕えるには警吏を幾人要するか.
現状
- n 人で十分.各列に一人づつ配し,同時に第一行から第 n 行まで並進すればよい.
- n/2 人以下ではダメ.
- n-1 人では不可能だろうと河村は予想している.これは n=2 のときはまあ明らか.n=3 のときもどう考えても不可能そうな気がするが,示せていない.
↑[H27.10.5]と書きましたが、K大学のOさんより,n=3,4,…くらいなら賊の存在し得る範囲の状況をすべて調べ尽して確かめられるという指摘を頂きました.実際それによると n=4 まではやはり n-1 人では足りないと判るそうです。
元ネタ
次の論文など.
- [1]A. Dumitrescu, I. Suzuki, P. Zylinski.
Offline variants of the “lion and man” problem.
In Proc. 23rd Annual Symposium on Computational Geometry (SoCG 2007),
pp. 102–111.
2. 四等分線[H27.5.27]
整数 k ≥ 2 に対し,平面 R2 上の互いに交らず空でない有界閉集合 P,Q 間の k 等分線とは,R2 の空でない部分集合 k−1 個の組 (C1, …, Ck−1) であって各 i = 1, …, k−1 について
Ci = { z ∈ R2 : d(z, Ci−1) = d(z, Ci+1) }
を満すものをいう.但し d(z, X) = infx∈X |z−x| は z から X へのユークリッド距離を表し,C0 = P,Ck = Q である.
与えられた P,Q 間の四等分線は一意か.
現状
- 存在はする[2].
- 四等分線でなく三等分線なら一意[3].
- P,Q がそれぞれ一点ならばその四等分線は一意[1].すなわち直線と抛物線からなる自明なもの以外にはない.(但しこれの証明[1]は極めて汚いので、簡潔に示せたらそれはそれで嬉しい.)
- 五等分以上については,P,Q が一点であっても一意性は不明.なお五等分以上だと真ん中の2~3本を除いて曲線は有界になる.
- 多分一意だろうと私(河村)は予想しています.
元ネタ
- [1]R. Fraser, M. He, A. Kawamura, A. López-Ortiz, J. I. Munro and P. K. Nicholson.
The distance 4-sector of two points is unique.
In Proc. 24th International Symposium on Algorithms and Computation (ISAAC), Hong Kong, December 18, 2013.
- [2]K. Imai, A. Kawamura, J. Matoušek, D. Reem and T. Tokuyama.
Distance k-sectors exist.
Computational Geometry 43(9), 713–720, 2010.
- [3]A. Kawamura, J. Matoušek and T. Tokuyama.
Zone diagrams in Euclidean spaces and in other normed spaces.
Mathematische Annalen 354(4), 1201–1221, 2012.
3. 遮光壁[H27.8.5]解決しました
[H27.9.12]N大学のIさんから,この問題が解けたという報告を頂きました.
[H28.3.3]解決論文(泉泰介氏)のリンク
平面上の領域 U の遮光壁とは、可算個の線分の合併 B⊆R2 であって,U に交わる任意の直線が B に交わるものをいう.その線分の長さの和(が有限であるときそれ)をこの遮光壁の長さという.例えば右図は単位正方形 U の遮光壁として知られている最短のものであり,その長さは √2+√6/2=2.638… である.なお右図では B⊆U であるが,これは遮光壁の定義で要求されているわけではない.
与えられた U に対し、どこまで短い遮光壁が作れるだろうか.一般に周長 2p の凸な領域 U の遮光壁の長さが p 以上であることは比較的容易である.例えば一辺 1 の正三角形の遮光壁なら最低でも長さ 1.5 以上は必要というわけである.
そこで問題.一辺 1 の正三角形の遮光壁であって長さ 1.5000000000000000001 以下のものはあるか.
現状
- 河村の予想は「無い」.多分中心から各頂点へ線分を引く(長さ √3=1.732…)が最短だと思う.
- 単位正方形については下界 2.00002… が示されている[2].すなわち単位正方形の遮光壁の長さの限界はこの 2.00002… 以上で上記の 2.638… 以下であるが,それよりも詳しくはわかっていない.
- 実は単位正方形に限らず,「三角形以外」の任意の凸領域について,このように周の長さの半分よりも真に大きい下界が示されている[2].
- それはそれとして,与えられた U(例えば多角形として)に対し,そこそこ短い遮光壁を求めるプログラムが作れれば面白い(幾つか近似算法あり,[1]参照).誰か書いてくれませんか.←この問題はまだ有効
元ネタ
4. 線分の警邏[H28.3.3]解決しました
[R1.7.7]この論文によって否定的に解決されたようです.
巡査が k 人おり各巡査 i は速さ vi で動ける.これを使って線分を警邏し,線分上のどの点にもどの単位時間に一度は誰かが訪れる(ことが永久に保たれる)ようにしたい.明らかな方法としては各巡査 i が長さ vi/2 の担当区間を往復するというもの(按分戦略)がある.これにより合せて長さ (v1 + … + vk)/2 を警邏できる.一方,その 2 倍である v1 + … + vk 以上の長さの線分が警邏できないことは比較的容易にわかる[1].
この「2 倍」という値を下げよ.つまり,1 よりも真に小さい定数 c が存在し,如何なる k と v1,…,vk に対しても次が成立つことを示せ.速さ v1,…,vk の巡査がどのように動いても,長さ c(v1 + … + vk) の線分は警邏できない.
現状
- 按分戦略が最適でない場合がある(つまり c が 0.5 までは下がらない)ことが判っている[2].実は更に,按分戦略の 4/3 倍に幾らでも近い長さの線分が警邏できる例がある(つまり c が 2/3 以上である)ことも判っている[3].多分この 2/3 が本当の限界であるような気がする.
元ネタ
ほか、思い出し次第、随時追加します……