スポンサーリンク

2018年10月25日木曜日

ハルヒの数学問題を解いた4chanの投稿が25年間解かれなかった数学問題を解いているかもしれない【海外の反応】

ハルヒの数学問題を解いた4chanの投稿が25年間解かれなかった数学問題を解いているかもしれない



ハルヒ数学問題(究極のハルヒマラソン問題)
(ハルヒ14話を可能な順で全て見なければならない時、最低でも何話見なければならないか?)

ハルヒは時系列順に放送していなかったため、このような問題が提起された


これに4chanのアノンが匿名掲示板に証明を掲載した

 Lower bounds  Anonymous Sat Sep 17 15:35:54 2011 No.3751197
Quoted by: >>3751366 >>3751370 
I think I have a proof of the lower bound n! + (n-1)! + (n-2)! + n-3 (for <span class="math">n \geq 2[/spoiler]). I'll need to do this in multiple posts. Please look it over for any loopholes I might have missed.
As in other posts, let n (lowercase) = the number of symbols; there are n! permutations to iterate through.
The obvious lower bound is n! + n-1. We can obtain this as follows:
Let
L = the running length of the string
<span class="math">N_0[/spoiler] = the number of permutations visited
<span class="math">X_0 = L - N_0[/spoiler]
When you write down the first permutation, <span class="math">X_0[/spoiler] is already n-1. For each new permutation you visit, the length of the string must increase by at least 1. So <span class="math">X_0[/spoiler] can never decrease. At the end, <span class="math">N_0 = n![/spoiler], giving us <span class="math">L \geq n! + n-1[/spoiler].
I'll use similar methods to go further, but first I'll need to explain my terminology...

https://warosu.org/sci/thread/S3751105#p3751197(4chanのログ)


2011年に4chanの匿名投稿者によって投稿されたこの証明は
コンピューター科学者で数学者でもあるロビン・ヒューストンによって2018年10月23日にツイッターで呟かれ
もしかしたら数学者が25年間解き続けているsuperpermutationsと呼ばれる問題の一部の解決法になっているのではないかと話題に
https://zbmath.org/?format=complete&q=an:0801.05004(問題)


これを受けてマーケット大学の数学者Pantoneが数学者にも分かりやすいように体裁を整えて翻訳

https://docs.google.com/viewer?a=v&pid=forums&srcid=MTUwMTUxMjExNDk4NTk5NjY5OTkBMDMxNDgwMTA5ODA5OTYyNzcyNDQBdlNFMnM3eTVCUUFKATAuMQEBdjI&authuser=0
(PDF)

Pantone氏はハルヒ14話を全ての順で見るためには最低でも93,884,313,611話を見なければならなくて、最高で93,924,230,411話見なければならないことを突き止めた

そして今この4chanのハルヒ問題の証明を基に25年間解けなかった数学問題(Construction of small superpermutations and minimal injective superstrings.)が解けるかもしれないと話題になっている



https://www.theverge.com/2018/10/24/18019464/4chan-anon-anime-haruhi-math-mystery
(詳細の英語記事)

SFみたいな話ですね

スポンサーリンク


この記事をシェアする



32 件のコメント:

匿名 さんのコメント...

ちょっと意味がわからん…w

匿名 さんのコメント...

放送順と時系列順だけで良いだろ…。

匿名 さんのコメント...

なるほどわからん

匿名 さんのコメント...

1週目に
1,2,3,4,5,6,7,8,9,10,11,12,13,14
2週目に最後を変えて
1,2,3,4,5,6,7,8,9,10,11,12,14,13
の順で見たとすると、1週目と2週目を繋げて
2,3,4,5,6,7,8,9,10,11,12,13,14,1
などのの連続も含まれている

さて、最低何話見たら、すべてのパターンで見たことになるでしょうか?

匿名 さんのコメント...

ハルヒの名前が数学史に残るのか・・・?

匿名 さんのコメント...

なかなかやるじゃない

匿名 さんのコメント...

ハルヒがわからんのだが紅莉栖の画像となんか関係あるん?

匿名 さんのコメント...

端的に言えば 無い
4chanで数学系(オタ成分含む)のスレを立てる時はこの牧瀬の画像をtop画にするのが定番になってるからそのせいだろう

匿名 さんのコメント...

エンドレス・サマーはどの順番で見るのが正しいのか

匿名 さんのコメント...

なんでこんな古い投稿が掘り起こされるのだろう。
4chanって過去ログ見れたっけ?

匿名 さんのコメント...

涼宮ハルヒの順列で、イーガンを読む長門か……

匿名 さんのコメント...

中学受験でよく出るあの公式じゃダメなのか

匿名 さんのコメント...

えっと、、、日本語で頼む

匿名 さんのコメント...

虚構が現実に浸食し影響を与え、共に手を取り一歩先に進もうとするなんて
わりと素敵な話じゃないか。
ハルヒを観た事のない俺でも思う。

匿名 さんのコメント...

アホな俺にはなんで14の階乗じゃダメなのかわからん、、、

匿名 さんのコメント...

全話数をビデオに録画して話数順に見れば簡単に解くことができると思う
ま、俺は数学がからきしダメなんでそれでも心もとないけれど

匿名 さんのコメント...

なるほど、ようやく問題の意味がわかったわ

匿名 さんのコメント...

ハルヒの放送が時系列順でなかった副作用がこんなとこに出てくるのはなんかハルヒらしいね
問題の意味さえよくわからんけど

匿名 さんのコメント...

1からnまでの整数の順列組み合わせの全ケースが含まれてる数列の最短の長さはどんだけなの?って問題か

匿名 さんのコメント...

なるほど分かった
おまえらが誤解してるかも知れんからちょっと解説してみ?

匿名 さんのコメント...

ヤマカンの仕掛けがこの難問を解いたということか?

匿名 さんのコメント...

4chanに投稿したこの匿名の書き込み主が、超頭良かったというだけの話じゃね?

匿名 さんのコメント...

1,2,3,4,5,6,7,8,9,10,11,12,13,14,1
の視聴順の中には
1,2,3,4,5,6,7,8,9,10,11,12,13,14

2,3,4,5,6,7,8,9,10,11,12,13,14,1
が存在する
全パターンを視聴するにはどんな配列で視聴すればよいでしょうか

匿名 さんのコメント...

なるほどな、俺は完璧に理解できたけど
答え合わせのために、自信のあるやつはちょっと答えてみてくれ

匿名 さんのコメント...

理解できたがそれを書くための余白が足りない

匿名 さんのコメント...

そういうことか
俺は理解できたけど小学生でもわかるように教えることは苦手なんだよなぁ
だからそういうの得意なやつは俺の分まで頼む

匿名 さんのコメント...

問題文の最初の一行を流し読みしちゃってたから
「いや放送順と時系列順に並べたのと2回見ればいいだけじゃん」って一瞬考えちゃったが
『可能な順で全て見なければならない時』なんだな
可能かどうかだからストーリー的な順番はもうどうでもいいっていう
そりゃ膨大なパターンになるわな

匿名 さんのコメント...

それよりもエンドレスエイトを何話まで見たら全部見たのと同じ扱いになるのかを証明してくれ

匿名 さんのコメント...

930億回も見ないといけないのかよ!w

匿名 さんのコメント...

なるほどなるほどそれな
わかるわかる

匿名 さんのコメント...

既出だけど自分なりに分かりやすく説明してみる。

何パターンあるか計算するのは簡単だとなんとなく分かるから
「全パターン×14話」が答えと思いそうだが
1話~14話連続視聴して次にまた1話を視聴した時に
「1話~14話」と「2話~14話・1話」の2パターンクリアできることに気づく。
連続視聴している時にどの「14話つながり」を切り取ってもいいということから
「全パターン×14話」より随分短縮されると分かる。
また「14話つながり」の中に同じ話数が複数入ってるのは除外だろうし、
既出のパターンも除外されることを考えると素人には手に負えないと分かってくる。

匿名 さんのコメント...

全14話の組み合わせパターン自体は階乗を使って簡単に求められるが、
ではその全てのパターンを実際に見るには何話見る必要があるか。
ただし、お隣さんと共通し重なる部分があるのなら、それを利用してもよい。

ってことであっとる?