For English speakers: We consider the numbers whose every digit is 1, such as 1, 11, 111, 1111,...... Prove that at least one of them is a multiple of 2019. We use the pigeonhole principle. If we divide an integer by 2019, we have 2019 cases of the remainders, which are 0, 1, 2, ......, 2018. Thus if we divide 1, 11, 111, ......, 11...1 by 2019, where the last is the 2020-digit number, at least two remainders are same. Let the remainders of the a-digit number and b-digit number whose every digit is 1 be same, where a > b. We consider the difference of them. Then 11...1*10^b (whose the first a-b digits are 1) is multiple of 2019. As 10 and 2019 are prime to each other, 11...1, which is (a-b)-digit number, is a multiple of 2019.
鳩の巣原理、最初授業で聞いた時漢字に変換できなくて外国人のハトノスさんが考えたカッコいい物なのかと思ってたのを思い出した
数学の授業って頭の考え方の幅を広げる練習だな。
本当に賢いのはこの解き方を1番初めに考えた人。その人は天才。
でもその天才が考えたツールをたくさん頭に入れるだけで同じぐらい賢くなれる。
天才ではないが、努力すれば賢くはなれる。
atけいた ああz
塾の先生が全く同じこと言ってたな〜
鳩の巣原理を知ったときは特に役に立ちそうになかったが、こういう使い方があるのだと勉強になりました
これは分かれば簡単ですが、2019にものすごい特殊性があるのではないかと考えるとはまりそうですね。
2019で割り切れる1…1の存在を直接示すのは難しくても、2019で割り切れる1…10…0の存在を示すのは簡単です。
aとnが互いに素のもとでは、x≡0 (mod n) ⇔ ax≡0 (mod n) という関係は右から左は頻用しますが、左から右の発想もできるようにしておくとよいと思います。なお一連数は難関中学では頻出。
n桁の1…1をf(n)と定める。
一連数の列 f(1), f(2), f(3), …を2019で割った余りは高々2019種類しかない。
よって、この中に2019で割った余りが同じものが必ず存在し、それらをf(l), f(m)とする (ただし、l>m)。
すなわち、f(l)-f(m)=f(l-m)×10^m≡0 (mod 2019)となるようなl, mが存在するが、
いま、2019と10^mは互いに素であるから、これは
f(l-m)≡0 (mod 2019)となるようなl, mが存在すること同値である。ゆえに、題意は示された。
映像授業って便利ですね。最初聞いた時はよくわかんなかったけど何度も聞いて噛み砕いて行くたび理解が深まって行く
途中まで、方針が全く見えなかったが、最後の「互いに素」でようやく腑に落ちた。なるほど。
Thomas Nanz おなじく
For English speakers:
We consider the numbers whose every digit is 1, such as 1, 11, 111, 1111,......
Prove that at least one of them is a multiple of 2019.
We use the pigeonhole principle.
If we divide an integer by 2019, we have 2019 cases of the remainders, which are 0, 1, 2, ......, 2018. Thus if we divide 1, 11, 111, ......, 11...1 by 2019, where the last is the 2020-digit number, at least two remainders are same.
Let the remainders of the a-digit number and b-digit number whose every digit is 1 be same, where a > b. We consider the difference of them. Then
11...1*10^b (whose the first a-b digits are 1)
is multiple of 2019. As 10 and 2019 are prime to each other,
11...1,
which is (a-b)-digit number, is a multiple of 2019.
"As 10 and 2019 are relatively prime"にした方が良いかと思います。
Coprimeとも言うらしいな
半端ねえ
皆様、ご指摘をありがとうございます。
鳩ノ巣原理ってすごいですね！
自明なことを1つの原理として、そこから、なにか大きな体系を作ったり、問題を解決に導くのはロマンを感じさせてくれます！
ホントですよね。一見すると当たり前すぎることなのに、それを使えなさそうな複雑な場面で使えうる。当たり前なことを原理として一般化しておくことで、そのような複雑な場面でも使いやすい。
（言いたいことがまとまってるかわからんが。。）
この情報量をたった5分で伝えられるなんてすごい
今日もわかりやすい解説をありがとうございます。
大学数学の範囲ならば、フェルマーの小定理を使っても示せます。
まず、2019 = 3*673 と素因数分解できます。よって、
10^672 ≡ 1 (mod 673)
とわかります。したがって、9 が 672 個並んだ数は 673 の倍数です。ここで 673 と 9 は互いに素なので、1 が 672 個並んだ数も 673 の倍数です。
また、672 は 3 の倍数なので、1 が 672 個並んだ数は 3 の倍数です。よってそれは 673 の倍数かつ 3 の倍数なので、2019 の倍数です。
ちなみに、1が 672 個並んだ数が2019の倍数となる最小の数であるかどうかはフェルマーの小定理からはわかりません。しかし、ほかの方のコメントによるとそれがちょうど最小のようです。
2019=3×673であることから10^672≡1であることがわかる理由がよくわかりません。もう少し解説していただけますか？
慶K
a^p ≡ a(mod p)
とくにaとpが互いに素のとき
a^(p - 1) ≡ 1(mod p)
（a∈N、p∈Ｐを満たす）
がフェルマーの小定理です。
10と673にこれを適用したのではないでしょうか。
私は9が672個並んだ数が673の倍数であるというところが分からないゾ···
10^672 ≡ 1 (mod 673)なら
9が671個並んだ数が673の倍数ではないのかゾ？
伏見荘圓名 10^673-1=99…99(9が672個)≡0(mod673)ですね
すうがくってたのちい
10^673 ≡ 10(mod 673)
10^673-1 ≡ 9(mod 673)
ではないのかゾ？
10^336,10^226,10^96 さえ調べれば最小性はすぐわかる
楽しく拝見させてもらっています。これは自分でもできそうだったので考えて見ました、いかがでしょうか。
まず、１の連続の数は解説の様に 2019a+b (2019>b>0の整数)となります。それがいつかは 2019Y(Y>0の整数)になるということを証明します。
また、１の連続の数は数列としてAn=10An-1+1(n>0の整数,A0=0)です。
ですから、2019Y=10(2019a+b)+1 と置く事が出来ます。
すなわち、2019y=10b+1(y>0の整数)です。これは b=(2019y-1)/10 にて、yの下1桁が9であれば成立します。
更にbの条件を考えると y=9 、b=1817 となります。
確かめたら、14桁15桁で解が有りますね。←追記)解は間違いですね。笑
この問題のポイントは”ある”より存在命題と言い換えできるか、2019の倍数を”2019で割った余りは0”に言い換えできるか...の2つ。
初見で解ける人が居たら凄いと思う。
私の計算では、１が672個並んだ数字は2019で割り切れます。計算してみてください。
mathematicaでやや強引に計算してみました。
www.wolframalpha.com/input/?i=%28∑10%5En%2Cn%3D0+to+671%29mod2019
672桁（10^671）まで1の総和を取ってmod2019したところ、無事に余り0になりました。
こういう証明問題って「1を672個並べた数値は割り切れます」と
回答したら、正解としてもらえるのかな…？
@@relux3925 実際に割り算をして余りが0であることを見せれば、存在を示してることになりますから紛れもなく正解ですよ。
cocco 3 存在命題は1つ条件を満たすものを示せば良いです。それをどのように見つけたかなどは書く必要がありません。
3で割り切れるのは明らか。フェルマーの小定理から 10^672≡1 (mod673) なので、これを使って673で割り切れるこを示せますね
現役・浪人と受験勉強に明け暮れていたのは33～34年前、一応理系職種ですが、それほど高等な数学は扱っていません。しかし、数学がちょっと好きなんでしょうね。検索履歴に反応して、おすすめのRUclipsに鈴木先生のサムネが現れるようになり、チャネル登録しました。他では「物理エンジン」とかも好き。
この問題も解ける訳はないのですが、やはり解法のエレガントさに惹かれるものがあります。エクセルで確認しようとしましたが、有効桁数の15まででは解が無く確認不能。エクセルに出来ないことを中学生でも理解できるような論述であっさりと説明してしまう・・・。やっぱ、数学好きです。
これを家族に分かってもらおうとしてるのですが、長男からは「興味ない・・・」、orz…。
動画のアップ、いつも有難うございます。めげずに頑張ります。
ご覧くださりありがとうございます😊
AKITO さんの(2020/6/8の)動画で思い出して、やって来ました。
私は、”11111 を 2019 で割った余りを 100000 倍して 11111 を足し、…” という計算を 135 回
繰り返すというかなり ”泥臭い” やり方で、55032…72269 という 668 桁の商と 672 桁の被除数にたどり着きました。（なぜ 5 桁の "11111" なのか、今となっては記憶にありませんが。）
このやり方なら、Excel でも可能です。（使った関数は、加減乗除にのほかに、
”INDEX”、”CONCATENATE” 〈これは "&" と同じですね(笑)〉くらいです。）
ちなみに（大学・学部は違いますが、）貫太郎さんと同じ文系です。
こんなところで（こんな時間に）♡もらうとは (^^♪
（「加減乗除にの…」とか改行がバラバラなところにはご海容を m(__)m）
自分は最初見た時、下の方のコメントにあるフェルマーの小定理からの解法が思い浮かんだ。
というのも1が連続する数は(10^n-1)/9と変形できて、10^n-1はフェルマーの小定理で2019の倍数だと示そうだったから。
最初鳩ノ巣原理と聞いた時にはまさか！？って思ったけど、少し考えたら鮮やかで感動しました。
こういう場面で鳩ノ巣原理を思いつけるとかっこいい！
今回は完全にやられました！ 2019から攻めると一生たどり着けないですねぇ
1/2019は循環小数のため、
99…99のように全部の桁が9である整数の中には2019の倍数がある
このときの整数99…99がn桁だとすると、2019は9が3n桁続く整数の倍数でもある
2019×N=999…99(9が3n桁続く)
2019×N=9×111…11(1が3n桁続く)
111…11(1が3n桁)は3の倍数であるから
999…999は27の倍数
2019は3の倍数だが9の倍数でないため、少なくともNは9の倍数、よってN=9Mとすると、
2019×M=111…11
なるほどぉー！！わかりやすい！
今年は2019年だから、入試に出るかもと思って見返しに来ました
これでほんとに出たら貫太郎さんに感謝ですね😁
Twitterでフォロバしていただきました！ありがとうございます！
1がa個並んでいるときの余りとb個並んでいるときの余りが同じだとすると、2020個並ぶまでに少なくとも一回は余りが循環していて、つまり1が2020個並ぶまでの間の中にも一個は2019で割り切れる数があるということでしょうか。
整数の問題の面白いところは、題意は分かるけど示し方がなかなか思いつかないところですね。
文転派ですが、最後の最後で大どんでん返しですげーってなりましたｗ
鳩ノ巣原理、高校でも大学でも教わったけど、ちっとも理解できませんでしたが、この場で理解することができたような気がします。ありがとうございました。
これ、分からない部分は引き算で消すという数列の考えを使ってるけど、同じ余りがあるって気づいてそこに持ってくまでの発想がすごい
ホーッと溜息しかありません。
全く、とっかかりさえ掴むことができませんでした。これだけ擦りもしなかった問題は久しぶりです。
じーっと考察モードに入って、何度手が止まったことか（苦笑）
数学は深いです。
これ灘中生とか普通に解きそうで怖い
柴田健太郎 僕は少し時間がかかりました。でもほかの灘中の子で賢い子なら簡単に解ける子もいると思います。
@@天才数学者未来の
す、すごい
数学を愛する者 質問なんだですが、どうやって数学好きになりましたか！？
モンテアル 勘だけで解けるならよっぽど楽だろうな
モンテアル よほどの天才か、よほどの努力をした人じゃないと初見で解けないと思う。
"勘のいい"程度では解けないよ
うぉ、すげぇ
ちょうど学校でやってるようなところだからなおさら頭に入る
3の倍数桁であることは分かったゾ〜(中学生並みの知識)
佐治さんの動画で似たような題材扱ってて、それ見てたから、なんとか解けました
部屋割り論法使って解く問題って面白いですよね
2019でなくても、2と5の倍数以外の数字なら何でも良さそうですね！
実はそのとおりです。2, 5 と互いに素な自然数ならば、同じようなことが言えます。
また、同じ方針で証明を進めると、3 以上の自然数 n が 2, 5 以外の素因数を含むならば、 1/n は十進法の循環小数で表せる、 ということが示せます。
因みにこの事実を使うと全ての有理数は循環小数か整数か有限小数で表せることが示せます
この問題を思い付いたやつすげえな、面白い
面白い問題だ！！
整数問題の中でもかなり難しい方ですよね。
聞いてしまえばなんてことはないが汗
子供の頃に「いずれの数も掛ける数によって9999…になるなあ」と予想したのを思い出しました。
予想通りやけど
どんな子供やねん(笑)
自分で証明したら学者並み～
@@NatureJapan3776 分数どうぞ
@@NatureJapan3776 メモ取る必要性皆無で草
しばらく考えないとどういうことか分かりませんでしたがなるほどそういうことか！天才ですねそれは、、、
こんな感じの問題があったように記憶しています(表現がヘタクソなのはカンニンしてください)：
任意の2019桁の自然数Xは、Xから連続した何桁かの数を取り出して(もちろん全桁すなわちX自身でもよい)、2019で割り切れるようにできることを示せ。
関連して、「５の倍数でない奇数には、必ず積が111...1となる相手の数が存在する」って、定理になると思いますが、どうでしょうか？。
1→1
3→37
7→15873
9→12345679
11→1or101
13→8547
（ry
その通りですね。
数学出来る人は2019年に特別な感情を抱くのだろうか
2,5の倍数でない数字で手っ取り早い数字として、今年2019年だから2019で出題しとけ
ってだけでしょ笑
RUclips界の数学者(料理も作れるサイクリスト)
鳩の巣原理ってそれ自体知っててもここまで上手く使えない……笑
類題がありましたので、ここに書いておきます。相異なる（ｎ＋１）個の整数がある．これらの中から２つの数を選べばその差がｎで割り切れるものがあることを証明せよ．（早稲田大）昭和５０年１月１日発行赤チャートより
最小の整数とそれ以外との差を考えればいいのかな？
nを法とする剰余類を考えます。
整数をnで割って得られる余りはぜんぶでn通り
整数はn+1個あるので得られる余りの数もn+1
鳩ノ巣原理で余りが同じになる組が必ずでてくるので差がnで割りきれる2つの数は必ずある！
来年のことを言うと鬼が笑いますよ
2019個の異なる自然数をそれぞれ
2019で割った余りは全て異なるのは何故ですか？
例えば、3、6、9と3つの異なる
整数を3で割った余りは全て同じです
全く分かりません、どなたか教えて頂けませんか？
すみません
全て異なる必要はないのですね、
自己解決しました
この考え方凄いなぁ おもしろい
あまり関係ないけど、2020個並べた数まで計算しなくても、2019個並べた数までに同じ余りの数はある前提でいけばいいね。
余りが被らない場合はその時点で割り切れてる数字があるから
こういうの見ると数学が楽しく思える
さっぱり分からないけど、不思議とワクワクします。
ぱっと循環小数が思い浮かびましたwww
こっちの方が簡単ですね
整数問題はいかに問題と出会って解法を吸収するかだよな
それ以外の問題はどうしたら？
良問ですね
Nを自然数からなる集合とする。
(0∈Nと規約する。)
2019を法として合同を考える。
全称記号∀や存在記号∀、否定￢
及び合同の否定として~を用いる。
集合Sの要素の数を|S|とする。
背理法で示す。
∀n∈Nに対してa(n)=1+10+…+10^nとして
∀n∈N a(n)~0と仮定する。
∀n,m∈Nに対して、n≦mのとき
・a(m+1)-a(n)=a(m-n)(a(n+1)-a(n))
・a(m-n)~0
・a(n+1)-a(n)=10^(n+1)~0……(※)
・m~0かつn~0、ならばmn~0
が成立する。
よって∀n,m∈Nに対して、n≦mのとき
a(m+1)-(n)~0
a(m+1)~a(n)
これより、S={a(0),…,a(2019)}として
∀x,y∈S x~y
￢∃x,y∈S x≡y
しかし、R={0,…,2018}として
・∀x∈S∃!y∈R x≡y
・|S|＞|R|
が成立し、鳩ノ巣原理から
∃x,y∈S ∃!z∈R x≡z≡y
∃x,y∈S x≡y
これで矛盾が生じた。
∴∃n∈N a(n)≡0
∴∃n∈N a(n)は2019の倍数 □
2019は(※)で
∀n∈Nに対して10^(n+1)の約数でない
2以上の数、つまり
2^n×5^m（n,m∈N）でない、2以上の数
として使われている。
よって、このような数で2019を
置き換えた命題も真である。
と動画を見る前に長々と書いたが
論法が似てた
理系こんなの理解できるのかよ………
まったく意味わからない
文系の範囲です。
鳩のす原理を使うと聞いたらわかるけどパッと見てこれは鳩ノ巣原理だなと思えないのが修行不足かなぁ…
解説を聞いてとても面白かったです！
2と5を素因数に持たなければどんな数字でもいけるんですね。
ほぇ〜(´-ω-｀)ﾅﾙﾎﾄﾞﾅ
3333…問題から飛んできました。はじめてみたとき、深く考えてしまいましたが、漸く消化でき、この問題と合わせて数学のノートに記録しました。鳩ノ巣原理を学べる非常に貴重な問題ですね。
最後の部分で質問なのですが，「x-yが111・・・111(1がa-b個並ぶ数)と互いに素である」と言い切れるのは何故なのでしょうか．
互いに素であるのは2019と10^bの部分。111.....111×10^b=2019(x-y)が示されたので、10^bを移項して考えたなら2019(x-y)/10^bが2019の倍数であれば、111...111は2019で割り切れるので、x-y自体が2019と10^bと互いに素でなくても関係はないということです。
じゃあ、11111……は2と5の倍数以外でなら割り切れるやつが存在するのか
私の持ってる参考書では、
部屋割り論法ってありました！
ハトの巣の方が馴染みやすい気がしますね♪( ´▽｀)
もしかして赤チャート勢ですか？笑
_ Flügel _
ごめんなさい、フォーカスΖ、goldなんです💦
赤チャートはレベル高すぎて買うのに勇気が足りません💦
でも赤チャートを使う人はめちゃめちゃ尊敬します！
鳩の巣原理ならピタゴラスイッチでのおかげで知ってた
私もnasternbさんと同じ事をやりました。 PCで１が5桁から1500桁まで全て2019で割った商と余りをチェックしました。
結果はnasternbさんやみなさんの予想を同じで、割り切れるのは最小が672桁、次が672ｘ２＝1344桁でした。（計算時間30秒） とんだ二番煎じでしたm(__)m
レプユニット数に関する入試問題ってあまり見かけたことがないな。
末尾9の数であれば1の位は1だからそうやって探すのかなあ…と予想した私は5流文系私大卒のバカでしたｗ
2019×???…???を筆算でやってみる。下の位から順に答が求まるので、すべて1になるように、?を一桁ずつ調整していけばよい。2019×(一桁の数)の一の位は、どの数字にもなり得るので、全ての桁が1になるまで繰り返せばよい。
こんな解き方があるとは…
なるほどぉ〜
なんとなく桁数とか最初の数字とか倍数って虚数平面にしてしまえば面白い気がする
ド・モアブルで指数関数を回転として扱うとどうなるのかなって
確か前に試したことがあったような🤔
鳩の巣原理(部屋割論法)は初めなんとなく使いそうだとは薄々思ったけどどうすれば良いか思いつけなかった自分はまだまだですね…
先日からこの問題がyoutubeの上位に表示されていたので挑戦してみましたが
さすがにこの問題は解けずにギブアップしました。
問題の題名に惹かれた
これは出ないわ笑
でも何回も見てたらそんなに難しくも無い気がしてきた
2と5 を約数に持ってなかったらなんでもいけるやん
この応用で、任意の奇数について、メルセンヌ数の中にその奇数の倍数であるようなメルセンヌ数があることを示せるなと思いました。
任意の奇数には、その倍数であるようなメルセンヌ数が存在する
[証明]
任意の奇数をkとする
以下のようなk+1組の式を考える。
左辺は二進表記で、すなわちメルセンヌ数である。
1 ≡ r_1 (mod k)
11 ≡ r_2 (mod k)
111 ≡ r_3 (mod k)
…
111…111 ≡ r_(k+1) (mod k)
これらの式において、r_xは高々k種類だがr_xはk+1あるため、鳩の巣原理によりr_xの値が衝突している2式が必ず存在する。
その2式を以下のように第m式、第n式とおく。（m
これ好き
東大生が見た動画としてオススメに出てきた
新将サブ大 さん
どこでどう検索すればそれが出てくるのですか？
タイトルの上に「(東大生ようつべrの名前)はこの動画を見ました」
と出てきました！
ちょうど来年の年と同じわけだからどこかで出題されるかもしれませんね
12^2コメ！
数学をやってると、自分が十進法に侵されているなあ、と感じるときがある。
実は進数変換で簡単に解ける問題もある（これとは言ってない）
これってどれやねん
絶対にカメラ見ないよね？
ということは末尾(1の位)が1,3,7,9である全ての自然数に適用できるということでしょうか!
(もっともただの「1」では割り切るもへったくれもありませんがｗ)
筆算でやり掛けて挫折した。
糀谷浩一 同士がここに
互いに素だから何、なんでってなったけどあーってなった(語彙力)
鳩ノ巣理論関係ないやんと思ったけど、同じ余りが出ることが重要なのか…はぇー使い所が難しい
解説聞いたら分かるけど、導出がむずすぎる、、、
すごすぎる
来年出るかもw
バルシャーク号 まじ共感
勉強しとこ
元隆三杉の千賀ノ浦親方にそっくりですね。
10^n-1=18171の倍数。18171の倍数が99999...9であることを示せれば、と思って筆算したら、160ケタまで行っても9が並んでくれない。しんだ。
10^n-1=18171の倍数+16354 ではないでしょうか？
ナゼだろう？ なんでだろ～ なんでだろ～ ななな・・・♪ 観てます！ ありがとうございます！(*- -)(*_ _)ペコリ
昔は「部屋割り論法」と言ったな。「求めよ」ではなく「必ずある」という問題文の表現で、ピンと来たw
1だけでできた整数=レピュニット
鳩の巣原理を使う問題っていいよな
ほえー…知らなかった。面白い！
考え方は分かったけどどういう風にしっかり証明していけばいいかわからない
責任は持てないけど多分これで○じゃないかな
全ての桁の数字が1でm桁の自然数をN(m)と書く。
自然数を2019で割った余りは0から2018の2019通り。よって鳩の巣原理から2020個の自然数N(1),N(2),N(3), ...,N(2020)の中に、2019で割った余りが等しい2数の組が必ず存在する。
その2数をN(a), N(b) [a>b]とし、2019で割った商をx, y 、余りをrとすると
N(a)=2019x+r
N(b)=2019y+r
よってN(a)-N(b)=2019(x-y)
ここで、N(a)-N(b)=N(a-b)×10^b であり、10^bと2019は互いに素なので
N(a-b)は2019の倍数である
よって全ての桁の数字が1で2019の倍数は存在する
@@いろはにほへと-d4u すげえ……
模範解答ありがとうござます。
「鳩の巣原理」など言わなくても十分通じるから「鳩の巣原理から」を抜けばいいだけ
奇数かつ5の倍数でない自然数は割り切れるレピュニット数を持つってこと❔
2019×1＝2019、2019×2＝4038、….ってやっていけば…
あれ？出ないな…
部屋割り論法かな？
あたった笑
脳死したワイ「2019×55032744482967365582521600352209564690991139728138242254141214022343294260084750426503769742997083264542402729624126355181332893071377469594408673160530515656815805404215508227395300203621154586979252655329921303175389356667216994111496340322491882670188762313576578063948049089208078806890099609267514170931704364096637499312090693962907930218479995597380441362610753398271971823234824720708821748940619668702878212536459193219965879698420560233338836607781630069891585493368554289802432447306147157558747454735567662759341808375983710307633041659787573606295745968851466622640471080292774200649386384899014913873754884156072863353695448792031258598866325463650872269を計算すると、確かにいずれの桁も1となり、題意は示された。」
やりましたね👍
今回、少し分かりづらかったかな
これ、すぐわかった奴。
相当な力があるぞ！！
自分は知ってたから見た瞬間わかってしまった…
自分で思い付く気がしないw
最後の最後の｢10と2019は互いに素だから11……111は2019の倍数｣ってところがよくわからないのですが、どなたか説明お願いしますm(_ _)m
2019=3×673の倍数より右辺は素因数として3と673を持つので左辺の素因数にも3と673が含まれます。
10^6の素因数には3も673も含まれていないので111…1は3と673を素因数に持つ、つまり2019の倍数であることが言えます