整数論の問題を出し合うスレ

自然数nに対し、
適当な自然数mが存在して、
次が成り立つ：

集合｛1,2,･･･,m｝を任意に{S1,S2,･･･,Sn}と分けたとする。
このとき適当なiに対して、
x+y=zを満たす3つの整数x,y,z（x=yでもよい）をSiが含む。

>>93
x+y=2z ならファンデルベルデン−ラムゼーの定理。

>>94
もっとくわしく！

>>93
「x=yでもよい」で「Siが3つの整数を含む」というのが分からん．
重複アリなの？重複ナシなら自動的に「m>2nが必要」というところだが…
（※逆に，「1,・・・,mの中に選ばない数字があってはいけない」はすぐ分かる）
スマンがもう少し説明希望．

↑重複あり

>>94
長さ k の等差数列が存在するというのがファンデルベルデン−ラムゼーの定理。
k = 3 とすればよい。

素数の2乗を12で割った余りの求め方を易しくキボンヌ

Re:>99 素数の2乗を3で割った余りと4で割った余りはどうなる？

３以上の素数は２では割りきれない。−＞３以上の素数は奇数である。１２で割ると余りは奇数。
５以上の素数は３では割り切れない。−＞１２で割ると余りは３や９はとれない。残りは、１、５、７、１１
だから２と３を除いた素数は１２で割ると余りが、１か５か７か１１。

例示
余り1--->13,37,61,,,,
余り5--->5,17,29,41,53,,,,
余り7--->7,19,31,43,67,,,,,
余り11-->11,23,47,59,,,,,,

これを自乗すると、
余りは１しかとれない。
なぜなら、１*１＝１、５＊５＝２５＝１２＊２＋１、７＊７＝４９＝１２＊４＋１、１１＊１１＝１２１＝１２＊１０＋１
だから２と３以外の素数の自乗を１２で割ると余りは１にしかならない。

どうして、これが整数論の問題なんだ？算数の問題ではあるが？

整数論の問題だけ200問ぐらい載ってる本発売されたな
整数論はまｔったくの無知だから買ってみようかな　面白そうだったし

>>93の証明

まず、任意の整数nに対して、「m≧R(n)ならば完全グラフK_mの辺をどのようにn色に塗り分けても、
かならず単色の三角形が存在する」という性質を持つR(n)が存在することを示す。

n=1ならば、R(1)=3ととれる。

あるnについてこの主張が正しいとし、R(n+1)の存在を示すために、
R(n+1)≧(n+1)(R(n)-1)+2ととれることを示す。
m=(n+1)(R(n)-1)+2ととり、K_nを(n+1)色に塗りわけ、その中の1点vをとる。
S_i={w| (v, w)は色iで塗られている}（i=1, ..., n+1）とすると、
|S_1|+...+|S_{n+1}|=m-1>(n+1)(R(n)-1)より、あるiに対して|S_i|≧R(n)となる。

S_iの中に色iで塗られている辺が存在しなければ、S_iはn色で塗り分けられているので
|S_i|≧R(n)より、S_iは単色三角形を含む。

S_iの中に色iで塗られている辺(w, u)が存在すれば、S_iの定義より(v, w)(w, u)(u, v)はいずれも色iで
塗られているのでこれは単色三角形となる。

よって、帰納法よりR(n)の存在が示された。

>>93を証明するには、V={1, 2, ..., R(n)}, 辺(x, y)を|x-y|∈S_iとなるiで塗ればよい。

>>95
van der Waerdenの定理は、

任意のk, lに対して
「{1, 2, ..., W(k, l)}をk個の集合にどのように分割しても、その中のある集合が
長さlの等差数列を含む」
という性質を満たす整数W(k, l)が存在する

というもので、l=3のときが>>94の場合。ちなみに>>93のはSchurの定理といわれる。

>>104
タイトルきぼん

>>107
内容は大学受験レベルだよ
同じタイプの問題を３つくらい別々に数えているので、実際の種類はたいしたことない
ていうか、期待はずれだったので買わなかった。
いまさら600の約数の個数と和を求めよっていわれてもね…

https://sslserver.sbs-serv.net/nippyo/books/bookinfo.asp?No=2578

>>108
整数の範囲なら和は 0.

自然数を2進数で表したものの集合は可算である。
自然数を2進数で表すと、0と1からなる無限長の文字列になる。
逆に 0と1からなる無限長の文字列を2進数と考えると、自然数である。
よって 0と1からなる無限長の文字列の集合は可算である。

言い換えよう。

0と1からなる無限長の文字列と自然数の2進数表記は一対一対応である。

間違い！ >>110、>>111

無限長 --------> 有限長

なら良い。

どんな長さであれ、0と1からなる文字列は2進数とみなせる

無限の問題は深いネェ・・・ζ関数とか・・・

>>109
楽しい？

>>106
ファンデルベルデン−ラムゼーの定理

k_1, k_2, ...... , k_n を与えたとき、
A = {1, 2, 3, ...... , W(k_1, k_2, ...... , k_n)} をどの様に n 個の集合 A_1, A_2, ..... , A_n に分割しても、　∃i, A_i は長さ k_i 以上の等差数列を含むような自然数 W(k_1, k_2, ...... , k_n) が存在。