組合せ（nCr）の分子が、分母で必ず割れるってすごくない？
「組合せ」と言うくらいだから、その値は必ず整数になる。 つまり、組合せを計算する際の分子は必ず分母で割りきれるわけ。 これって、誰も言わないけど、かなり驚きのことだと思う。 例えば、10×9×8×7×6が5×4×3×2×1で割りきれるかって考えてみてほしいんだけど、計算しないですぐわかる？ 直感的にはわからないじゃん。でもこれって、10C5の分子と分母だから、割りきれるわけですよ。 他にも、111×110×99×98×97×96×95が7×6×5×4×3×2×1で割れるとか、わからないでしょ。 これも、111C7の分子と分母だから割りきれるの。 すごさがわかったよね？ もっとすごいのは、これが一般的に言えること。 すなわち、組合せnCrって、任意の整数nから下に連続するr個の整数を、r×r-1×…×2×1で割った値だけど、 こんな変な割り算が、自然数nとrがどんな値でも常に整数になるなんて
逆数学｜森北出版株式会社
「定理の証明には、いったいどれくらいの公理が必要なのだろう？」――古くは紀元前から、数学にはたびたびこの疑問が投げかけられてきた。この疑問にある種の回答を与えるのが、逆数学とよばれる数学基礎論の一分野である。 逆数学では、“公理”から“定理”を導く通常の数学とは異なり、“定理”に必要な“公理”を探る。これによって、定理どうしを“深さ”で分類したりすることができる。たとえば、「最大値の定理は中間値の定理より“深い”」といった具合だ。 本書では、解析学の基礎を通して、逆数学の基本的な考え方を解説。要所要所で歴史的な話題にも触れながら、読者をナビゲートしていく。 本書を読み終えた後、読者は、これまで出会ってきた定理たちを少し違った角度から眺めている自分に気づくはずだ。 「数学者は、材料の公理を加工して、定理という製品をつくり出す機械みたいなものか、といえば決してそうではないだろう。むしろ、ある定
三体問題が解けないことを証明したのは誰？…ポアンカレはいったい何を証明したのか（浅田 秀樹）
三体問題が解けないことを証明したのは誰？…ポアンカレはいったい何を証明したのか 三体から生まれた「カオス」の発見 ポアンカレは「三体問題が解けないことを証明した」といわれます。しかし、「二体問題」の一般解を求める方法（「求積法」）では、「三体問題」の一般解を求めることができないということは1887年にドイツの天文学者ハインリヒ・ブルンスによって証明されていました。それではいったい、ポアンカレは何を証明したのでしょうか？ 浅田秀樹さんの著書『三体問題』から、ポアンカレが証明した驚くべき事実をご紹介します。 ポアンカレの登場 ブルンスによる証明がなされた2年後の1889年、スウェーデン国王兼ノルウェー国王のオスカル2世の60歳の誕生日を祝うために、数学に関する懸賞問題が公表されました。 このオスカル2世の懸賞問題とは、厳密な数学的な定義・用語を避けて筆者なりに意訳すればおおよそ以下のようなもの
数学の難問「巡回セールスマン問題」の近似解を求める最良のアルゴリズムが数十年ぶりに更新される
巡回セールスマン問題とは、「複数の都市を移動するセールスマンが全都市をちょうど一度ずつ巡り、総移動コストが最小の経路を求める」という数学の難問です。長年にわたり「クリストフィードのアルゴリズム」が巡回セールスマン問題の近似度が最も高いアルゴリズムとされてきましたが、新たに「クリストフィードのアルゴリズムを上回る近似度のアルゴリズムがあると証明された」という論文を、コンピューターサイエンスの研究者が発表しています。 [2007.01409] A (Slightly) Improved Approximation Algorithm for Metric TSP https://arxiv.org/abs/2007.01409 Computer Scientists Break Traveling Salesperson Record | Quanta Magazine https://www
リーマンの再配列定理を使って級数を「お望みの実数」に収束させよう - tsujimotterのノートブック
今日のテーマは 「リーマンの再配列定理」 です。「条件収束する実数列の級数は、再配列によって任意の実数に収束させることができる」という主張です。何を言っているかわからないという方にも、これから詳しくは説明していきますのでご安心ください。 無限級数 が絶対収束するとは、各数列に絶対値をつけた が収束するということです。名前の通りですね。 対する条件収束とは、無限級数が絶対収束はしないが収束はすることを言います。 たとえば、平方数の逆数の和 は絶対収束しますが、自然数の逆数を足し引きする級数（交代級数） は条件収束します。後者が条件収束であることは、たとえばこちらの記事の最後に紹介されています： mathtrain.jp 「なぜ絶対収束か条件収束を気にするのか」と疑問に思った方もいるかもしれませんが、それにはワケがあります。 絶対収束する級数は、足し合わせる順番に関わらず同じ値に収束します。つ
中1の問題『(-1)×(-1)=1を示せ』を大学レベルの数学でオーバーキルするリプ欄が勉強になる
青猫 @AonekoSS @marsh0604 (−1)×(−1) = (−1)^2 = (cosπ+i sinπ)^2 ※複素数平面に展開して = cos2π+i sin2π ※ド・モアブルの定理で = 1 + i・0 ※ゼロの乗算は別途必要やも = 1 中学生向けじゃない…… 2020-07-05 10:47:34
ゼロから学んだ形式手法 - DeNA Testing Blog
2020年1月に入社し、SWETの仕様分析サポートチームに加わったtakasek（@takasek）です。 仕様分析サポートチームでは、社内のプロダクト開発に対する形式手法の活用可能性を模索しています。当ブログでも、継続的に形式手法に関する情報発信をしています（形式手法 カテゴリーの記事一覧）。 この記事では、加入3か月を経てようやく形式手法の輪郭が掴めてきた私の視点から、学習前後での理解の変化について振り返ります。想定読者として学習前の私と近い属性——すなわちコンピュータサイエンスや数学の専門教育を受けておらず、主に現場での実務と自習に頼ってきたソフトウェアエンジニアを想定しています。 形式手法を学ぶ前の認識と疑問 ソフトウェアエンジニアとしての私の一番の興味関心は設計手法です。設計は、なんらかの解決したい問題に対して、ある一面を切り取った構造（モデル）を与え、そのモデルを解決の機構に落
Mathematical proof that rocked number theory will be published
Thank you for visiting nature.com. You are using a browser version with limited support for CSS. To obtain the best experience, we recommend you use a more up to date browser (or turn off compatibility mode in Internet Explorer). In the meantime, to ensure continued support, we are displaying the site without styles and JavaScript.
クイックソートは半順序でもソート可能であることをCoq/SSReflectで証明する - Qiita
はじめに 前回の記事で、全順序が仮定されているからこそうまくいくソートアルゴリズムを半順序で使用するとどうなるかを見ました。結果としてクイックソートなら半順序でもうまくソートできることを見ましたが、本記事では、これを定理証明支援系Coqを用いて、形式的に証明していきます。 定理証明支援系Coqに関して軽く説明しておくと、プログラムが正しく動くことを、数学的に検証できるツールとして使えるものです。 クイックソートを定義 SSReflectのpathライブラリには、標準のソート関数sortが定義されていますが、このアルゴリズムはマージソートなので、前回の記事で検証したように半順序では使えません。 そこでCoqでクイックソートを定義します。 まず定義の前に、ソートを行う要素の集合Tと、半順序関係Rを宣言しておきます。実際にはTは型で、RはただのT上の二項関係T -> T -> boolとして定義
量子重力には対称性はない ― 大栗機構長らが証明
2019年6月19日 東京大学国際高等研究所カブリ数物連携宇宙研究機構（Kavli IPMU） 1. 発表概要 東京大学国際高等研究所カブリ数物連携宇宙研究機構（Kavli IPMU) の大栗博司 (おおぐりひろし) 機構長は、マサチューセッツ工科大学物理学教室の Daniel Harlow 助教と共同で、重力と量子力学を統一する理論では、素粒子論の重要な原理であった対称性がすべて破れてしまうことを、ホログラフィー原理を用いて証明しました。この証明にあたっては、量子コンピューターで失われた情報を回復する鍵とされる「量子誤り訂正符号」とホログラフィー原理との間に近年発見された関係性を用いるという新たな手法が用いられました。本研究成果は、素粒子の究極の統一理論の構築に大きく貢献するものであるとともに、近年注目される量子コンピューターの発展にも寄与すると期待され、アメリカ物理学会の発行するフィジ
中学生の数学定期テストが難解過ぎて議論紛糾「多項式を文字でおくことが出来るのはなぜ？」
鈴木貫太郎 @Kantaro196611 視聴者の塾の先生から「某中学校の定期テストの過去問を見て困った」どう答えればいいのでしょうかという質問。常に「どうしてそうなるかを考えることが大事」と言っているオイラも、流石にこの「なぜ？」には困った。模範解答を募集します。 pic.twitter.com/MK8OVIeUHF 2019-06-09 01:05:34
"二分探索はX分探索において最強"の証明 - Qiita
0.背景 二分探索を初めて学習してから数年、今更二分探索を学習する機会があり、 「分割する個数を増やしても計算時間は二分探索より早くならないのか？」 という単純な疑問が浮かんだ。 サイズNの配列をx(>2)個の領域に分割すれば、計算時間はlogx N * １ループ当たりの比較回数となり、logx N < log2 Nなので、１ループ当たりの比較回数次第では早くならないか？と思ったからである。 しかしWebで検索してみたが、探索アルゴリズムの一環としてのX分探索に関する記事は(少なくとも日本語では)見つからなかった。 また「凸関数の極値を求める」という目的における三分探索や黄金比探索といった探索アルゴリズムがあることを知ったが、今回は二分探索と同様の目的における探索アルゴリズムを対象にするため、本稿では対象外とした。 参考 ・ 実数探索三種類解説 -nodchipの日記 ・ 三分探索と黄金分
有限集合とは何だろう（ストーリー付き練習問題集） - 檜山正幸のキマイラ飼育記 (はてなBlog)
「Xは有限集合である」とか「Xは有限集合でない」とかの表現はよく出てきますが、この有限性ってのはいったい何なんでしょう？ 少しマジメに考えてみることにします。これといった予備知識を要求しませんが、マジメに考える態度は必要です。 実は、有限性を調べるのは目的じゃなくて手段です。証明の“お膳立て”シリーズとか、自然演繹ダメじゃんシリーズ（って、そんなシリーズねえけど、「存在記号の除去規則について考える」とか）に対して、例題を提供するのが、この記事の主たる目的です。この記事を読みながら、ハッキリとは書いてない証明を全部書いていくことが練習問題になります。内容的には超カンタン（当たり前）なので、明示的な証明は逆にハードです。 内容： 自然数についてよく知っているとする 論理記号など 有限性の定義 個数勘定の原理 個数勘定の補題と鳩の巣原理 個数勘定の補題と数学的帰納法 もう少し数学的帰納法のための
ルジンの問題 - Wikipedia
ルジンの問題（Luzin - のもんだい）とは、正方形に関してニコライ・ルジン (Nikolai Luzin) が考えた問題である。 「任意の正方形を、2個以上の全て異なる大きさの正方形に分割できるか」という問題であり、ルジンはこの問題の解は存在しないと予想したが、その後いくつかの例が発見された。 最小の解[編集] 21個の正方形に分割 最小の解は21個で、A. J. W. Duijvestijn がコンピュータを使って発見し、それが最小の解であることを証明した[1]。1辺 112 の正方形を、一辺の長さがそれぞれ 2, 4, 6, 7, 8, 9, 11, 15, 16, 17, 18, 19, 24, 25, 27, 29, 33, 35, 37, 42, 50 の計21枚の正方形で、隙間なく埋めつくすことができる。(オンライン整数列大辞典の数列 A014530) 正方形を上辺から順番
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://twitter.com/johncarlosbaez/status/1478421119736504323
無理数の無理数乗 = 有理数となる場合 (2020年 横浜市立大/1986年 阪大)
六角精児のどこが六角形なんだよ
Johnson-Lindenstraussの補題 (ランダム射影)
数学の超難問ABC予想、京大教授が「証明」 - 日本経済新聞
韓国人 on Twitter: "神の話すると大体存在証明の話されるけど、証明可能なことと真であることは別の概念であることは一般に知られてないことを毎回思い出す"