【難問研究】数学科のキムとまたも超難問に挑んでしまいました。
Вставка
- Опубліковано 11 сер 2023
- ➡︎東工大作問サークルのTwitter
/ sakumontech
東工大の文化祭に行った時、気さくに対応していただきありがとうございました。
また、動画で使っていいと当時言っていただきありがとうございました。
最高の問題もまたありがとうございました。でんがん&キム
Corrections:
10:54 ガウス記号の中身は、nではなくℓです。
でんがんが"勉強法"の本を出しました！決して"天才"じゃない僕の全てをここに書き込みましたので、興味がある人は是非下記から予約お願いいたします。
⬇︎「元バカによるバカのための勉強100カ条」予約サイト⬇︎
www.amazon.co.jp/dp/4815612854/
でんがんTwitter ＠dengan875
はなおでんがん / @user-xn4vh6de3u
株式会社ほえい / @user-mc1eu5xr7l
ビックバン理論提唱者でんがんです。私は皆さんに、自分の経験を活かして、勉強の面白さをわかってほしいとの想いで自分のチャンネルを再更新することに決めました。僕の経験が皆さんの人生や進路の少しでも足しになったら幸いだと思っています。はなおでんがんチャンネルではふざけるけど、個人チャンネルでは勉強を中心に発信していきたいと思います。具体的にはガチの解説系からモチベーションの保ち方のようなメンタル面まで動画にできたら良いと思っています。でんがん
⬇︎日常でんがん編集協力⬇︎
・ダンボ(メイン編集者)
/ dam_bo_
・よっしー
/ yosshi_ediedu
・たくや
/ takuya_edit
・しげ
#日常でんがん # #
見てても何にもわからないけど悩んでるこの二人をいっぱい見せてくれて東工大サークルありがとう
今まではほんとに何もわからなかったけど、ついこの前Cを使う計算を習ったからノリノリ実験一緒にできて嬉しい、、、！！！！！
こういう系の動画まじであと45本くらいほしい
キムさんの計算用紙の書き方きれい。
問題がシンプルで、答えもカッコイイ！
完全にシリーズ化ですなぁ。
タイトルにPart.いくつとかつけても良いんじゃないでしょうか?😊
たぶん、一番シンプルな解法は以下のものかな
一般に整数nに含まれる因数2の個数をord2(n)と定義する。
pを0以上の整数として2^p≦n
キムの途中のガウスの証明めっちゃサラッと綺麗よな
このシリーズは面白すぎる
続編まってました！😂
数学勉強してて問題自体よりは定義とか条件に詰まって泣きそうになるけど、当たり前かもだけどでんがんさん達は当然のように武器として使えてて本当に凄い。自分は受験生なのにそれに迷ってるせいでペースが遅すぎる…
公式暗記して理解してそっからパターン化(最大値って単語見た瞬間5パターンくらいの解き方思いつく感じ)したらいける、そもそも公式の意味理解してない可能性ある
解き方のパターン化はそうなんやけども、高校数学レベルの公式なんて証明出来て当然やろ
意味理解してないとか論外
ちな京理
解く過程がわかるかつ新しいこと、今回はルジャンドルの定理、を知ることができて気持ちいい！次回も期待しています！
ずっとやってほすい
分子を偶数の積と奇数の積に分けると、計算途中で2^nが出てきて解きやすかった
この問題を作成したものです！解いてくださってありがとうございました！
作問者おって草
天才や
嘘つくな。証拠出せ
@@user-zb4yc2tx8sZ世代のキモいとこ
問題作るのと解くのってどっちが難しいんですか？作ったことないんで分かりきってることなら申し訳ない
整数問題、解くのはハチャメチャ難しいけど回答は割と理解できるから見てて楽しいです
n!に含まれる2の因数の個数を求める関数g(n)を考えると
nが偶数のとき
g(n)=n/2+g(n/2)
という性質がある
これを使うと
g(2n)-2g(n)-1=n-1-g(n)
となって自然かつ結構簡単に求めたい条件がn-1=g(n)と同値だとわかる
ちょー嬉しい
今回の証明の考え方は、チェビシェフの定理の証明の不等式評価でよく用いるようなものが多いですね！
14:32ぐらいのとこのキムの仕草可愛い
nを2進法で表した時の1の数をf(n)とするとn!が2で割り切れる回数はn-f(n)なので2nCnはf(n)回2で割り切れる
f(n)=1よりn=2^k
方針として出てきたn！の素因数の個数に関する式はしばしばルジャンドルの定理と呼ばれているものですね。
ちなみにこの定理にガウス記号が登場していますが、ガウス記号には天井関数版と床関数版が存在し、今回は床関数を用いた定理となっています。
このシリーズ大好きだから終わらないでほしい…🥹🥹
毎月1本ペースですが、頑張ります！
普通に2の乗数で割った数を整理するだけで出来ましたよ！
nを2^m < n < 2^(m+1)を満たす数と仮定すると
n = 2^m + K (K < 2^m) とおける。
ここで、Kを2でL回割れる数だと考えると
2nを2^(L+1)で割った数とnを2^(L+1)で割った数のガウスを2倍した数とで、数値が1ズレる。
2^(m+1)で割る時も同様のズレが生じる為2で割れる回数に2回ズレが生じる。
この結果はLの値によらない為、
nが2^m < n < 2^(m+1)を満たす数である時
2nCn/2は偶数となる。
nが2^m の時は2^(m+1)で割る時しかズレが生じないので奇数
これで出来てると思います！
パスカルの三角形を偶奇で色分けするとシェルピンスキーのギャスケットが出てきて、2n=2^k(kは自然数)以外の時はその幾らか上に１～n-1まで全部偶数の段があるから生成される2nCnは偶数の二倍、つまり4の倍数だな、という直感が働いた（分かりづら）
安定のでんキムペア！！
₂ₙCₙ=2n(2n-1)…(n+1)/n(n-1)…1
と表せる、ここでn=2ᵏのときmodnで
1≡n+1、2≡n+2…n-1≡2n-1が成り立つので、それらは2の素因数に関して打ち消しあい（2進数で考えてもらえば分かりやすいと思います）
残った2n/n=2となるので₂ₙCₙは素因数2を1つしか持たないことが分かる
待ってましたぁぁぁ！
2n!/n!=2のn乗*(奇数)になるからn!が持つ2の因数が(n-1)コになるものを探しにいく視点から入っても良さそうな感じがする、、
シンプルでかつめっちゃいい問題でした！ガウスの考え方参考になります！
今回は☆8の中では結構易しめだと思う。試験時間が長いなら出せる問題。
お互い同じ色のペン使ってて、なんかいい
2nCnに関する整数問題って東工大でちょっと前に出題されてたよねたしか！
2021ですね
こないだ解いたので覚えてました笑
6:45 のでんがんさんが問いかけてキムさんが証明してた数式
僕自身が受験した、岡山大学文系数学2014の大問3で出てきました笑笑
当時、この大問完答できて全完できたかも！！！！と思ったら、
大問2のベクトルの序盤で計算ミスしてた＆大問４の確率ちょいミスで
200点中150点くらいだったのいまだに思い出（教育学部合格できました）
6:48
証明しました、好きですw
nCm (mod p) 【≒nCmを素数pで割った余り】に関する議論としてはLucasの定理、v[p](nCm)【≒nCmが素数pで何回割れるか】に関する議論としてはKummerの定理が知られています。この問題解いた後にKummerの定理の証明を眺めるとめっちゃ世界広がるからおすすめです！
東工大模試研究会の人に連絡取って、出題者に設問の意図を説明してもらうとかのコラボしてほしい。
むずすぎる
いつかガウス記号の授業とかも出るのかな〜
この東工大作問げんげんに解いてほしい
6:04 この式変形したら①\sum_{k=1}^m [n/2^k] = n-1 になり、ガウス記号の定義に従って①の値を不等式評価したら、n
キムさんの爪綺麗すぎて見とれてた、
クンマーの定理が強すぎる･･･
東工大オープン受けてほしい
このシリーズいちばんおもろい(解説の意味はわからん)
パスカルの三角形の全ての数を2で割ったあまりに書き換えれば良いですね。
東大の過去問に同様の問題があるのでそれを参考にしたのでしょう。
n を2進数表記してルジャンドルの定理を使えば n! が2で割り切れる最大回数が n - (nを2進表記したときの各桁の和) になるので
そこから (nを2進表記したときの各桁の和) = 1 が必要十分とわかります
キム氏のノートすごく綺麗。将来はでんがんさんの予備校のカリスマ講師になるのかなあ？
動画を見る前に自分なりに解いてみました。
2nCnに2の素因数がただ1つ存在するとき、2nCn/2は奇数になる。
2nCn
=2n!/n!n!
=2n(2n-1)(2n-2)…(n+1)/n! ・・・①
①式から偶数の因数のみを取り出したものをf(n)とする。奇数の因数には2の素因数は含まれない為、f(n)に含まれる2の素因数の数と、2nCnに含まれる2の素因数の数は等しい。
n=1の場合、2nCn/2=1となり、題意を満たす。
nが偶数の場合、n=2k(kは任意の自然数)として、偶数の因数のみを取り出すと、
f(2k)=4k(4k-2)(4k-4)…(2k+2)/2k(2k-2)(2k-4)…2
=2k(2k-1)(2k-2)…(k+1)/k!
=2kCk
となる。
2kCkとf(k)に含まれる2の素因数の数は等しい為、2nCnとf(k)に含まれる2の素因数の数は等しい。
同様にして、n=m･2^i(mは任意の奇数、iは任意の自然数)とすると、2nCnとf(m)に含まれる2の素因数の数は等しい。
nが3以上の奇数の場合、n=2k+1として、同様に偶数の因数のみを取り出すと、
f(2k+1)=(4k+2)・2kCkとなる。
2kCkは必ず偶数になると仮定する。
nが3以上の奇数の場合、f(n)は2の素因数を2つ以上含むため、題意を満たさない。
nが偶数の場合、mが3以上の奇数のときに題意を満たさない。m=1のときに題意を満たすため、m=1のときにのみ題意を満たす。
よって、この仮定が真ならば、n=1, 2^iのときに題意を満たす。
2nCnが必ず偶数になることを数学的帰納法で証明する。
n=1の時、2nCn=2で偶数となる。
n=kのとき、2nCnが偶数であると仮定すると、n=k+1のとき、
2k+2Ck+1={(2k+2)(2k+1)/(k+1)^2}・2kCk
=2(2k+1)2k!/(k+1)!k!
となり偶数となる。
よって、2nCnは全ての自然数nに対して、偶数となる。
よって、n=2^a(aは0以上の整数)のとき、2nCn/2は奇数となる。
二項係数関係の問題って色々あって、例えば ₂ₙCₙ=Σ[r=0,n]ₙCᵣ² とか。
まぁ色々楽しんでみて。
13:00位からとうとうパンクしてついていけなくなった...
いやむずい
2n!はn!より2の因数をn個多く持つこととn=2^kの予想を一緒に考えたら簡単に解けたよ！
これ誘導ついてどっかで出されそう
おもろすぎるw
卒業して数十年経った阪大卒業生です。最近積サーさん界隈の動画楽しく観させてもらってます。今もう一度数IAからやり直してみたくなりました。
₂ₙCₙ/2=₂ₙ₋₁Cₙ=奇数
mod2のパスカルの三角形を描いて₂ₙ₋₁Cₙの部分を見ればわかりますね
(2n)!に含まれる約数2の数は2n自体を半分にして切り捨て、2以上であれば半分にして切り捨てを繰り返すだけで良く、nが2^mとなる時は(2n)!に含まれる約数2の数は2n-1個、n!に含まれる約数2の数はn-1個で成り立つ
それ以外の時は面倒なのでパス
2で割って切り捨て2で割って切り捨ての総和なので、2^mでなければ必ず2nの方と1個以上の差ができるで良いのか…
nを二進数で考えると二進数表記でn=100....000しか成り立たないことは結構すぐわかるのでそれですぐだと思います
11:24の式の右辺にあるnってlの間違いではないでしょうか、、？
これって漸化式的に解けそうやな
マジで需要あるね、数学科b1的には本当に嬉しい。楽しい限りだわ。
受験生終わってからでよかった〜笑
証明するのはよく分かりませんが、nを2進数で表した時の1の数分だけ、2nCnを2で割れるような気がしました
任意の自然数nに対してあるkがあって、2^(k-1)≦n
詳しく聞きたいです。
@@SpaceGTM このコメント欄で「シンプルな解法」として紹介されているものそのままです
東工大生なのに模試研究会の存在を初めて知った、、
東工大の模研の人達なんでこんな問題作れるんや、、、
東工大行く説濃硫酸ですね
ふむふむ、、、。
なるほど、わからん。
もうルジャンドルやん笑
頭良すぎて理系だけど全く着いていけないw
nを2進数で表したら一瞬で解けたよ。2進数で表したときの1の数が2nCnを2で割れる回数になるから2^kのときだけ2で1回しか割れない。証明も割とかんたんだった。
この問も周期関数の問も東大で出てきたら捨て問でしょｗ
東大後期に似た問題あったようななかったような
2nCn = (2n)!/(n!)^2
n! が2を素因数にもつ個数を f(n) とすると, 2nCn/2 が 2 を素因数に持つ個数は (n + f(n)) - (2f(n) + 1) = n-1 - f(n)
ルジャンドルの定理より f(n) = [n/2] + [n/4] + …
ここで 1 + 2 + 4 + … + 2^k = 2^(k+1) - 1 であることを思い出すと, n = 2^k 以外のときは切り捨ての影響で n-1 より小さくなるということが考えられて, 実際そう
証明省いたけど思ったよりも自明では無いか？
f(2m) = f(2m + 1)
f(4m + 2) =2m+1 + f(2m+1) = 2m+1 + f(2m) = f(4m) + 1
みたいにむだな 2^l が付いてると l 回目で 1 になって切り捨てられてロス
ちゃんと書くなら帰納法が楽かなぁ
なのでさっき僕は証明しました
みんなで数学やってる時に一度は言ってみたいセリフですねぇ・・。
解答考えてみました
n=(2^k)*m
(kは0以上の整数、mは奇数)とおいてf(n)をnを2で割れる回数とするとして定義すると、
f(2nCn)=f((2n)!)-2f(n!)であり、具体的にf((2n)!)、f(n!)を考えると、
f(2nCn)=m-f(m!)となるが、ルジャンドルの定理をm!に適用し、任意の実数xに対し[x]
よく考えたらn=(2^k)*mと置かなくても同様の証明ができますね
10:54のとこ正しくはガウス記号の中のnはLが正しいんだけどね。
うぽつです ＿ |＼○＿ .ᐟ.ᐟ
n=2^kで成り立つのは割と簡単に証明出来て、
素因数の2の個数は、n以下の2の累乗で割りきれるから
Σ_{i=1}^{k} 2^{i-1}
で2^k-1になるから、分母がこれの2倍で分子がkを2kに置き換えた奴になって、2が一つ余るので奇数になる。
次に1
ホリエモンの東大受験企画でヨビノリが数学の魔術師として出てきた時にキムさんが行ってた問題を見た記憶がありました。
Tシャツちっちゃ！
受験期に見てたらどんだけ学びがあっただろうか、、、3年遅かった(*^^*)
まぁ、オーバーワークやけどね
2015東大のと確かに似てはいるけど難易度が違いすぎる
2015C mが偶数になる最小だっけ？
はず、動画で言ってるやん笑
友達に出されて解けなかった問題置いておきます。
問。次の不等式を証明せよ
e^(1-π/2)
f(x)=e^(-x)sinxが[π/4,π/2]で単調減少から示せますね
東大文系の過去問かと思ったわ
ルジャンドルの定理を独自に導いたってことでOK?
パスカルの三角形書いて2ᵏにはすぐ気づけて気持ちよくなってたけの、結局証明難しかったw
N=2^k+aと置くと、aが0でないときは必ず分母の2の数が分子より2つ以上多くなる。a=0なら2^k+1の１つ分だけ多くなる でどうでしょう？
キム、小山功に見えてきた
ありがとう（ボソッ）
九大(旧帝底辺)でこれ出たら発狂するわ笑
この企画に河野玄斗呼んでほしい
3:19きむかせつなんちゃらのすけ
ord_2(n)=n-popcount(n)なので、
popcount(n)=1ですね
(popcount(n)はnの2進数表記時の各位の和)
他の方もおっしゃってるように、クンマーの定理の証明を知っていると方針が見えますね。(p=2の証明は結構簡単)
今回は比較的簡単でしたね
nを整数とするとき、4nC2nと2nCnは2の素因数の個数が等しいので、これを繰り返し用いて2^αnC2^(α-1)nと2nCnの2の素因数の個数が等しくなるので、任意の自然数が2^α×(奇数)と表せることを用いると、nが奇数の場合のみ調べればよいことが分かり、議論が簡単になります。
今回もありがとうございました。
全くわからないのに一番好きです。
この企画に触発されて1A白チャート買いました。
月一回とか信じられない、あっという間ですね。楽しそうなお二人を何度も見てます。
いつかは理解できるようにと、白チャから継続していきます。
是非ともこの企画、無理のない範囲でどうか続けてください。
お二人と作問者に感謝と敬意を込めてコメントさせていただきます。
長文失礼しました。
この問題に実際に入試で遭遇したらどこで見切りをつけるかがポイントになりそう
なんであたりまえのことをカッコつけてんのww
@@user-bk3no6yt4r その感性すばらしいね
@@user-yn1fy1dk7o 素晴らしくないっすよ
@@user-bk3no6yt4r 草
@@user-yn1fy1dk7o これだけで笑える感性が羨ましい
いつまで数学の勉強してんねんww
ヨビノリがルジャンドルについてやってたなー
久本さんて整体があまり近づかないよね
この東工大作問げんげんに解いてほしい