【たかし君】算数みたいな問題文なのに実は超難しい問題を出し合うスレ【釣り】

たかし君は1,2,3,4,...という数を、以下の条件を満たす二つ以上のいくつか(有限個)のグループに分けたいと思いました。

・それぞれのグループは「ある数からいくつか飛ばしごとの数達」の集まり
例: 5から3つ飛ばしごとの数達
→5,8,11,14,...

・飛ばす数はグループごとで全て異なる

しかし、たかし君のしようとしていることはどう頑張っても出来ません
それはなぜでしょう？

今日のうんこ、山盛り

無限飛ばし個だから

偶数と奇数で被らない

5から3飛ばしと0から9飛ばし

1グループ目　1から4飛ばし
2グループ目　2から4飛ばし
3グループ目　3から4飛ばし
4グループ目　4から4飛ばし

たかし君、頑張ってね

>>6
マジレスすると飛ばす数が全部４なので
「飛ばす数はグループごとで全て異なる」
に反する

その上で、さらなるマジボケ

1グループ目　1から2飛ばし
2グループ目　2から4飛ばし
3グループ目　4から8飛ばし
…
nグループ目　2^(n-1)から２^n飛ばし
…

さあ、つっこんで！(￣▽￣)←アホ

>>8
とっても、超ありがとう
その方法、なかなか素晴らしいですね

2グループなら4の倍数が埋まらない
3グループでも8の倍数が埋まらない
4グループでも16の倍数が埋まらない
でも、
高々10グループでも、
1024未満を埋尽くすぜぇ
たかし君にとっては、1024は無限大
みたいなものだろう。

たかし君、その内に教えようと思う

>>1の問題は「面白い問題おしえて〜な」スレにも
書かれたことがある問題で、自分でも挑戦してみたが、

・飛ばす数はグループごとで全て異なる
・グループ分けは直和である(異なる2つのグループの共通部分は空である)

という条件の場合しか解けなかった。この条件の場合は、適切な母関数を
適切な複素数値の近傍で観察することで矛盾が導けるので、それであっけなく終わった。

一般の場合はぜんぜん解けなくて、諦めて放置していたのだが、さっき調べてみたら、
この話題は covering system と呼ばれているようであり、wiki によると

Z = 2Z ∪ 3Z ∪ (4Z＋1) ∪ (6Z＋5) ∪ (12Z＋7)

が成り立つらしい。計算してみると、確かにこの等式が成り立つ。
そして、よく見ると、これは>>1の反例になっている。だまされた (＾o＾)
この程度なら自分でプログラム組んで検索しても反例を見つけられたはずなので、
面倒くさがらずに泥臭い検証やるのも重要だなって思った。

covering system の概念を考案したのは、かの有名なエルデシュであるらしく、>>10にも書いた

・飛ばす数はグループごとで全て異なる
・グループ分けは直和である(異なる2つのグループの共通部分は空である)

の場合には不可能であることを、1950年にエルデシュが予想として提出していたらしい。
これは意外だった。なぜなら、>>10に書いたように、この場合の証明は

＞適切な母関数を適切な複素数値の近傍で観察することで矛盾が導ける

で終わってしまうので、エルデシュほどの天才が自力で解けないわけないからだ。
実際、wikiによると、エルデシュがこの予想を提出してからすぐに何人かの数学者が
独立に証明したらしい。そして、最初に証明した数学者たちの名前を取って、
Mirsky–Newman theorem と呼ばれているようである。
残念ながら、調べてみても閲覧可能な形の論文は出てこなかった。
しかし、誰の証明かは知らないが証明そのものは1つ見つかって、以下のリンク先で読める。

ttps://math.stackexchange.com/questions/237909/understanding-a-proof-of-the-davenport-rado-mirsky-newman-theorem

そして、この証明は自分がやった証明と全く同じｗ
やはり、考えることは皆同じようである。