数学詳しい奴来て！！！！！！！！！

[0001 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:42:19.271 ID:Q/iXrlW/0]

数学パズル、論理クイズ、ナゾナゾ、なんでもいいので頭使う問題ください！
https://mi.5ch.net/test/read.cgi/news4vip/1642344917/

↑のスレで出題された問題で
「どんな2n個の整数に対しても、その中のn個をうまく選べば和がnの倍数になることを示せ」

ってやつがマジでクソ難しすぎて分からん！！！

誰か解けませんか？？？

[0002 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:42:36.610 ID:Q/iXrlW/0]

というか出題者来て！！！！！

[0003 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:43:43.066 ID:Q/iXrlW/0]

今朝も立てたけど結局誰一人分からんかった
なんこれ

[0004 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:44:42.989 ID:H1NqP4nf0]

よくわからんけど
数学的帰納法つかってみれば

[0005 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:45:17.680 ID:Q/iXrlW/0]

>>4
帰納法ももちろん試したけどうまくいかないよ
次のステップで素数になる場合厳しいんよ
12→13とか

[0006 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:45:57.915 ID:uSJVAYm6a]

そもそも命題が正しいことはわかってるの？

[0007 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:46:39.213 ID:Q/iXrlW/0]

>>6
それも分からない
出題者がテキトーなこと言ってる可能性もあるかも

でも試せば試すほど正しそうには思える

[0008 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:46:47.270 ID:jhRhxf94d]

どんな2n個のmod nに対しても、その中のn個をうまく選べば和が0になることを示せ

ってこと？

[0009 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:47:06.863 ID:Q/iXrlW/0]

>>8
そそそそ
言い換えるとそういうことですね

[0010 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:48:44.913 ID:Q/iXrlW/0]

例えば2*3=6個の整数

13,2,-1,1,7,11
とかテキトーなもんとってきても、
-1,11,2を選べば和が12になって3の倍数にちゃんとなる

[0011 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:49:26.802 ID:uSJVAYm6a]

難しい

[0012 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:49:30.709 ID:2YA9NTnL0]

これ俺もわからなかった

[0013 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:50:16.523 ID:Q/iXrlW/0]

ちなみに今朝の議論

数学の天才来て！！！！ 特に整数問題強い奴！！！！
https://mi.5ch.net/test/read.cgi/news4vip/1642364313/

とりあえずこのスレではn=3の場合は正しいことを証明してくれた人がいました

[0014 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:50:47.771 ID:Q/iXrlW/0]

>>11
ね
これマジで考えても考えても全く解けない

[0015 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:51:00.990 ID:Q/iXrlW/0]

>>12
>>1のスレにいた人？

[0016 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:51:09.532 ID:e28T63r80]

n=1はどうすんの？

[0017 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:51:32.564 ID:Q/iXrlW/0]

>>16
n=1なら自明だよ
任意の整数は1の倍数なので

[0018 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:51:35.891 ID:2YA9NTnL0]

>>15
2のべきなら出来るとか言ってるやつ

[0019 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:52:12.335 ID:Q/iXrlW/0]

>>18
ああああありがとう
寝落ちしてた人だよね

あれからというもの、n=3の場合のみの進展しかないです...

[0020 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:55:05.475 ID:TODL3swo0]

含まれてる整数が全部n以上だと詰まない？

[0021 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:56:09.043 ID:Q/iXrlW/0]

>>20
そんなことないよ！nの「倍数」なので
例えばn=2で考えて
10,11,12,15とかでも、
10,12を二つ選べば和が22になってちゃんと2の倍数になる

[0022 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:58:02.805 ID:TODL3swo0]

種類じゃなくて個だから
含まれてるのが全部偶数でnが奇数の場合は詰むパターンないかな

[0023 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 18:58:13.153 ID:uSJVAYm6a]

自分で解くより研究探す方が楽そう

[0024 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:00:08.729 ID:Q/iXrlW/0]

>>22
うーんどうだろう

例えばn=3としても、
2,4,4,6,6,8
で全部偶数だけど{2,4,6}を選べば和が12でちゃんと3の倍数になってる

でも確かに素数とかの場合は結構探すの厳しそう

[0025 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:00:10.272 ID:e28T63r80]

2n個の中にはnで割った余りが0…n-1のものが最大2n個あるが、
n個以上あるものがあればそれを選べば良く…
みたいなことを言っていくんかな

[0026 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:00:36.606 ID:Q/iXrlW/0]

>>23
確かに

でもどうやって調べたらいいのやら

[0027 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:00:49.154 ID:2YA9NTnL0]

昔は数オリのCも割と解けていた俺が解けていないってことはなかなか難しいと思われる

[0028 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:02:18.860 ID:Q/iXrlW/0]

>>25
なるほどー
でもn個以上あるのはごく一部だしなー

それぞれバラバラに点在してると難しいっす

[0029 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:03:09.848 ID:Q/iXrlW/0]

>>27
おおおすげえ 数オリのC解けるってガチ中のガチですね

それならもうこれ無理難題すぎるな...

[0030 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:05:31.733 ID:uSJVAYm6a]

http://quiz-tairiku.com/q.cgi?mode=view&;no=18982

若干近そうな問題あった

[0031 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:06:33.194 ID:2YA9NTnL0]

>>30
これは一目でわかる

[0032 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:06:35.091 ID:Q/iXrlW/0]

>>30
あああこの場合は>>13にも書きましたが
鳩ノ巣原理で解けますね
探してくれてありがとう

でもこれは問題なのは「いくつか」なので「ちょうどn個」じゃないんよね

[0033 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:08:42.329 ID:Q/iXrlW/0]

>>30
ちなみに解法としては、
n個の整数をa_1,...,a_n
として、
S_i := a_1+...+a_i mod n
とおきます
そうすると、鳩ノ巣原理から、ある異なるi,jがあって、
S_i ≡ S_j mod nになります

なのでi＞jとして、
S_i-S_jはnの倍数となり、これはいくつかのaの和になっている

[0034 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:09:06.241 ID:Q/iXrlW/0]

という感じです

和の個数が制限されていないのがポイントですね

[0035 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:09:08.366 ID:uSJVAYm6a]

うむむ

[0036 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:09:49.564 ID:Q/iXrlW/0]

>>31
一目でわかるのはさすが

[0037 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:11:20.311 ID:Q/iXrlW/0]

でも直感的には多分こんな感じで鳩ノ巣使うんだろうなとは思います

巣を作るのがホント難しいけど

[0038 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:13:41.967 ID:g9yMndqb0]

n個丁度使わないとだめなのか
むずそう

[0039 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:14:26.633 ID:2YA9NTnL0]

どの対称差もn個になる巣を沢山作るの普通に無理そうなんだが

[0040 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:14:27.240 ID:Q/iXrlW/0]

>>38
そうなんよ
ガチのマジで難しい
モヤモヤすごい

[0041 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:15:14.018 ID:Q/iXrlW/0]

>>39
うーん
単純な鳩ノ巣だけじゃ厳しいか...

[0042 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:19:28.854 ID:e28T63r80]

>>25
最大n-1個のときは、n-2個選び、残りの2個で全合計がnになる組み合わせが必ず1組みは存在し、
みたいな

[0043 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:20:06.695 ID:e28T63r80]

ごめん、しないや

[0044 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:22:55.244 ID:Q/iXrlW/0]

>>42
＞n-2個選び、残りの2個で全合計がnになる組み合わせが必ず1組みは存在し

n=3で
1,1,0,0,0,0
とかだと、1が2つあるけど1と残り二個だと無理ですね

[0045 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:24:00.283 ID:ijBMNrjK0]

だいぶ前からvipで見かける問題だけど解けてるのは見たことない

[0046 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:24:44.846 ID:Q/iXrlW/0]

>>45
マジ？ 結構有名問題なんかな？

[0047 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:25:42.403 ID:e28T63r80]

>>44
その場合は3で割った余りが0のものがn個以上あるケースなので考慮済みで大丈夫

[0048 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:26:05.755 ID:ijBMNrjK0]

>>46
そこは知らんわ
vipにはなぜか数学に自信ありとか物理に自信ありみたいなやつ一定数いるから
そういうやつらが自作したのかもしれん

[0049 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:26:11.796 ID:Q/iXrlW/0]

>>44
ごめんこれは最大がn-1個じゃないので反例になってないわ

[0050 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:27:38.376 ID:i6U1uYDK0]

「上手く選べば」だから背理法使わないと証明できないだろ
和がnの倍数になる組み合わせが存在しないと仮定して矛盾を導かないと

[0051 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:28:14.713 ID:2YA9NTnL0]

降参してググってしまったが多分無理なやつだったわ
しかも2n-1個で成り立つらしい

[0052 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:29:44.280 ID:lESQLdoMM]

0,0,...,0,n+1だと無理だけどなんか条件ある？

[0053 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:29:51.622 ID:Q/iXrlW/0]

>>50
背理法使うにしろ難しいと思うんだよね
どんなn個組みも和が「nの倍数じゃない」と仮定する
なので
複雑にたくさんパターンがある

[0054 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:30:26.570 ID:Q/iXrlW/0]

>>51
うおおおお！！！
まじ！！！！！

ググって答え出たのか！！！！
どうやって調べた？？

お願いします！

[0055 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:31:00.263 ID:Q/iXrlW/0]

>>52
いや出来るよ
0をn個を選べばよい
0はn×0だからnの倍数にもちろんなるよ

[0056 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:31:17.418 ID:2YA9NTnL0]

>>54
Erdős-Ginzburg-Ziv theorem

[0057 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:31:36.647 ID:Q/iXrlW/0]

>>13でも予想してた人いたけど
やっぱり2n-1でも可能なのか！

[0058 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:32:55.132 ID:lESQLdoMM]

>>55
マジだ吊ってきます

[0059 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:33:08.054 ID:Q/iXrlW/0]

>>56
うはっｗｗｗｗｗｗ
調べたらまんま同じ主張でワロタｗｗｗｗ

すげえ！！！ ありがとう どうやってググって調べましたか？

[0060 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:33:50.193 ID:Q/iXrlW/0]

証明も載ってるな

https://mathoverflow.net/questions/16721/egz-theorem-erdő;s-ginzburg-ziv

頑張って読解してみる

[0061 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:37:12.717 ID:Q/iXrlW/0]

まさかの帰納法だったのかｗｗ
帰納法厳しい疑ってすまんかったｗｗｗｗ

[0062 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:37:45.032 ID:Q/iXrlW/0]

ああいや定理のための補題が帰納法で示されるってだけか

[0063 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:45:34.952 ID:H1NqP4nf0]

そもそもその問題出した奴はどこから引っ張ってきたのか教えてくれなかったのか

[0064 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:45:36.823 ID:vhDNo6Pra]

n=0のとき、0個の数は0の倍数ではない
はい、反例

[0065 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:46:36.009 ID:Q/iXrlW/0]

>>63
出題するだけどっか行ってもうた

[0066 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:47:40.624 ID:Q/iXrlW/0]

>>64
さすがにnは自然数でしょ
もちろん原文にはそう書いてなかったけどさ

[0067 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:48:58.019 ID:H1NqP4nf0]

そら残念だ

まさか○○予想みたいな、ガチのお題だったりしないよな

[0068 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:50:15.388 ID:Iie1AOXE0]

a と 2n-a (aは1〜n) をn個集めれば、和は2n*n になって、nの倍数になるんじゃね？
なんか勘違いしてる？

[0069 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:50:19.414 ID:Q/iXrlW/0]

>>67
>>56で定理を見つけてくれたよ！！
今読解中です

[0070 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:51:21.900 ID:Q/iXrlW/0]

>>68
いやもちろん連続した整数とは限らないよ
「どんな2n個の整数」に対してもそうなることを証明しないといけない

[0071 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 19:59:33.436 ID:Q/iXrlW/0]

ほぼほぼ証明理解した！！！！
SUGEEEEEE！！！ あたまいい！
けど二箇所ほど認めている部分がよく分からないな...

[0072 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 20:05:08.708 ID:Q/iXrlW/0]

nが素数の場合を示せば十分
n=pとする

次の補題を用意します
「2≦i≦pとして、a_1,...,a_(2i-1)∈Z/pZを、i個が同じものではないものとします
A:={a_1,a_2,...,a_(2i-1)}とします
さらにS:={Aのi個の要素の和 全体}とします
すると、#S ≧ i となります」

[0073 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 20:05:35.294 ID:Q/iXrlW/0]

補題の証明をします

[0074 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 20:05:57.575 ID:Q/iXrlW/0]

iについての帰納法で示します

[0075 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 20:07:56.397 ID:Q/iXrlW/0]

i=2の場合、
A = {a_1,a_2,a_3}で、全て異なる成分であるため、
a_1+a_2 ≠ a_1+a_3より、少なくとも#Sは2以上です

なのでi=2はおk

[0076 以下、5ちゃんねるからVIPがお送りします 2022/01/17(月) 20:10:56.499 ID:Q/iXrlW/0]

次、i=kのとき補題が真だったとします

A’ = {a_1,a_2,...,a_(2k-1),b,c}とすると、
一般性を失わずにb,cがA’に最も多く現れる2個の要素を表すと仮定しても問題ありません(←ここ謎ポイント)
さらに仮定よりb≠cです(←ここもわからん)