施佩纳定理（极值集合论）是什么？
What is Sperner's theorem (extremal set theory)?
施佩纳定理说：在 n 元集合的所有子集中，互不包含的子集族最大规模为 C(n,⌊n/2⌋)，即取“中间一层”。它是极值集合论的开山之作。
Sperner's theorem states the largest family of subsets with none containing another has size C(n,⌊n/2⌋)—the middle layer. It founded extremal set theory.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#组合 #极值 #集合
无损压缩为什么存在一个不可突破的极限？
Why is there an unbreakable limit to lossless compression?
香农无噪编码定理：对独立同分布的信源，无损压缩的平均位数不能低于熵 H=−Σpᵢlog₂pᵢ，同时存在达到任意接近 H 的编码方案。直观原因：信源中约有 2^(nH) 条“典型序列”承载了几乎全部概率，而低于 H 位的编码最多区分 2^n(H−ε) 条序列，必然发生碰撞、无法唯一解码。霍夫曼编码就是逼近这个极限的实用方法。
Shannon's noiseless coding theorem: for an i.i.d. source, lossless compression cannot average fewer bits than the entropy H=−Σpᵢlog₂pᵢ, yet schemes exist that approach H arbitrarily closely. Intuitively, about 2^(nH) “typical sequences” carry almost all the probability mass, while codes below H bits can distinguish at most 2^n(H−ε) sequences, forcing collisions and ambiguous decoding. Huffman coding is a practical method approaching this bound.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
《信息论基础》Cover 与 Thomas
Elements of Information Theory by Cover and Thomas
独立核验依据 · Independent verification: 核验依据 1 ISBN 9780471241959 (2006) · 核验依据 2 ISBN 9780665590955 (2002)
#熵 #无噪编码定理 #数据压缩
斯特林数（Stirling numbers）是什么？
What are Stirling numbers?
第一类斯特林数计算把 n 个元素分成若干环排列的方式数，第二类计算分成若干非空子集的方式数。它们在组合计数与级数展开中频繁出现。
Stirling numbers of the first kind count permutations into cycles; of the second kind, partitions into nonempty subsets. They recur in counting and series expansions.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#组合 #计数 #斯特林
卡特兰数出现在哪些组合计数问题中，它的递推公式是什么？
In which combinatorial counting problems do Catalan numbers appear, and what is their recurrence?
卡特兰数计数如合法括号序列、二叉树的形态、不越过对角线的格路等结构，第n项满足以更小项乘积求和的递推。它展现了看似不同的组合对象竟有同一计数。斯坦利的《计数组合学》与孔泰的《高等组合学》都系统收集了这些情境。
Catalan numbers count structures like valid parenthesis sequences, shapes of binary trees, and lattice paths that stay below the diagonal, with the nth term given by a recurrence summing products of smaller terms. They reveal that seemingly different objects share one count. Stanley's Enumerative Combinatorics and Comtet's Advanced Combinatorics collect these contexts.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-03
来源 · Source
Stanley《Enumerative Combinatorics, Vol. 2》；Comtet《Advanced Combinatorics》
Stanley, Enumerative Combinatorics, Vol. 2; Comtet, Advanced Combinatorics
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL25674992W：Enumerative Combinator
#卡特兰数 #二叉树 #括号序列
为什么把数列“装”进多项式或幂级数里，能算出数列的规律？
Why does encoding a sequence inside a polynomial or power series reveal its behavior?
把数列 a₀,a₁,a₂,… 记为幂级数 G(x)=a₀+a₁x+a₂x²+…，序列的递推关系会变成关于 G 的代数方程，解出 G 再展开系数，就能得到通项公式。以斐波那契数列 F_n 为例，递推 F_n=F_(n-1)+F_(n-2) 给出 G(x)=x/(1-x-x²)，把分母的二次式分解、用部分分式展开系数，就得到 F_n=(φ^n-ψ^n)/√5 的闭合形式。生成函数把“离散的计数”转化为“连续的分析”，是组合数学的核心技术。
Write the sequence a₀,a₁,a₂,… as a power series G(x)=a₀+a₁x+a₂x²+…. Recurrence relations become algebraic equations for G; solve for G and expand coefficients to obtain a closed-form formula. For the Fibonacci numbers, F_n=F_(n-1)+F_(n-2) yields G(x)=x/(1-x-x²); factoring the quadratic denominator and expanding by partial fractions gives F_n=(φ^n-ψ^n)/√5. Generating functions turn discrete counting into continuous analysis, making them a core technique of combinatorics.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#生成函数 #斐波那契 #幂级数
任何博弈都一定有纳什均衡吗？纯策略没有均衡时怎么办？
Does every game have a Nash equilibrium, and what happens when pure strategies have none?
纳什 1950 年证明：任何有限博弈（参与者、纯策略都有限）在混合策略下一定存在纳什均衡。混合策略就是按概率随机选择策略，这个结论依靠的是布劳威尔不动点定理。硬币配对游戏就是典型例子：两个玩家同时亮正反面，要求相同才赢，纯策略下你选哪面对方都能针对，但各以 1/2 概率随机出时达到均衡，双方期望收益都为零，谁也占不到便宜。
Nash proved in 1950 that every finite game — finitely many players and pure strategies — has a Nash equilibrium in mixed strategies, where players randomize over actions. The proof relies on Brouwer's fixed-point theorem. Matching pennies illustrates it: two players show heads or tails simultaneously and one wins when they match. With pure strategies any choice can be countered, but when both randomize 50-50, neither can gain, giving a mixed-strategy equilibrium with zero expected payoff for each.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
美国数学会(AMS)《博弈论与经济模型》
American Mathematical Society (AMS), Game Theory and Economic Modeling
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787100047876（豆瓣书目条目: 博弈论与经济模型）
#纳什均衡 #混合策略 #不动点定理
为什么网络中的最大流量恰好等于最小割的容量？
Why does the maximum flow in a network equal the minimum cut capacity?
割是把顶点分成含源点与含汇点的两部分后，从源侧指向汇侧的所有边。任何从源到汇的流量都必须穿过每个割，所以最大流不超过最小割容量。反过来，Ford–Fulkerson 增广路算法说明：找不到增广路时，当前流量恰好等于一个由饱和边构成的割的容量，于是相等。这个定理精确刻画了瓶颈，用于交通、通信和图像分割。
A cut splits the vertices into a source-side and a sink-side; its capacity is the total of edges pointing from the source side to the sink side. Every source-to-sink flow must cross each cut, so max flow ≤ min cut capacity. Conversely, the Ford–Fulkerson augmenting-path algorithm shows that when no augmenting path remains, the current flow equals the capacity of a cut formed by saturated edges—so equality holds. The theorem pinpoints bottlenecks, with applications in traffic, communication, and image segmentation.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
Ahuja、Magnanti 与 Orlin《Network Flows》第 6 章,Cormen 等《Introduction to Algorithms》第 26 章亦有完整证明
Ahuja, Magnanti and Orlin, Network Flows, Chapter 6; also Cormen et al., Introduction to Algorithms, Chapter 26 for a full proof
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#最大流最小割 #网络流 #瓶颈
Ramsey 定理 R(3,3)=6 说明任意 6 人中必有三人互相认识或三人互相不认识。请给出证明思路,并解释 R(4,4) 已知值的困难之处。
R(3,3)=6 says among any six people three mutually know each other or three mutually do not. Sketch the proof and explain what makes determining R(4,4) hard.
取一人 v,其余 5 人分成与 v 相识或不相识两类,由抽屉原理一类至少 3 人;这 3 人中若有两人同类相连则与 v 构成目标三角形,否则他们自身构成同色三角形。而 R(4,4)=18 直到 1955 年才由 Greenwood 和 Gleason 确定,因为顶点数的增长使染色方案数爆炸式增加,R(5,5) 至今仍是未知的著名难题。
Pick a person v and split the other five into those who know v and those who do not; by pigeonhole one class has at least three people. If any two within that class are joined in the same color, they form the target triangle with v; otherwise those three form one themselves. By contrast R(4,4)=18 was settled only in 1955 by Greenwood and Gleason, since the number of colorings explodes with vertex count, and R(5,5) remains a famous open problem.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
Graham、Rothschild 与 Spencer《Ramsey Theory》,及 Greenwood 与 Gleason 1955 年 Canad. J. Math. 论文“Combinatorial relations and chromatic graphs”
Graham, Rothschild and Spencer, Ramsey Theory; R. E. Greenwood and A. M. Gleason, "Combinatorial relations and chromatic graphs", Canadian Journal of Mathematics 7 (1955)
独立核验依据 · Independent verification: 核验依据 1 CROSSREF 标识 10.4153/cjm-1955-001-4：Combinatorial Relatio
#拉姆齐理论 #鸽笼原理
把 5 个城市用最少的路连起来，需要几条路？
What is the minimum number of roads needed to connect 5 cities?
4 条。只要每条新路都连接一个已经连通的点和一个新的点，4 条路就能让 5 个城市两两之间都能到达，而且没有任何多余回路。这种“连通且没有圈”的网络就是树：n 个点正好需要 n-1 条边，这是图论里最基本也最重要的结构之一。
Four. As long as each new road joins an already-reachable city to a new one, four roads suffice to make all five cities mutually reachable with no wasted cycle. A network that is connected and has no cycles is a tree: n vertices need exactly n-1 edges. Trees are among the most basic and important structures in graph theory.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#树 #图论 #连通性
卡特兰数（Catalan numbers）是什么？
What are Catalan numbers?
卡特兰数 C_n = (1/(n+1))·C(2n,n) 计数许多结构：合法括号串、二叉树、不跨越对角线的路径。它是组合数学中出现频率最高的数列之一。
Catalan numbers C_n=(1/(n+1))·C(2n,n) count many structures: valid parentheses, binary trees, lattice paths. Among the most frequent sequences in combinatorics.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#组合 #计数 #卡特兰
拉丁方与组合设计是什么？
What are Latin squares and combinatorial designs?
拉丁方是每行每列都出现一次全部符号的方阵，是实验设计的基础。更一般的组合设计研究如何平衡地安排试验，以减少偏差。
A Latin square has each symbol once per row and column, fundamental to experimental design. Broader combinatorial designs arrange trials to reduce bias.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#组合 #设计 #拉丁方
13 个人里为什么一定有两个人的生日在同一月份？
Why must two people among any 13 share a birth month?
一年只有 12 个月，把 12 个月当成 12 个“鸽笼”，13 个人要放进这些笼子里，至少有一个笼子要装两个人。这就是鸽笼原理：如果 n+1 件东西要放进 n 个抽屉，那么至少一个抽屉里有两件。它看似平凡，却是许多存在性证明的利器。
A year has only 12 months; treat them as 12 pigeonholes, and 13 people must fill them so that at least one month holds two people. That is the pigeonhole principle: if n+1 items go into n boxes, some box holds at least two. It sounds trivial, yet it powers many existence proofs.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#鸽笼原理 #存在性证明 #组合数学
哈希函数为什么被称为“单向”函数？
Why are hash functions called one-way functions?
好的哈希函数把任意长度的输入变成固定长度的输出，计算很快、同样的输入永远得到同样的输出；但从输出反推输入几乎不可能，也难以找到两个不同输入产生相同的哈希值（抗碰撞）。因此哈希被用来存储密码的“指纹”、校验文件是否被篡改，也是数字签名与区块链的基石。
A good hash function maps arbitrary-length input to a fixed-size output, evaluating fast with the same input always giving the same output; yet inverting from output to input is practically impossible, and finding two different inputs with equal hashes (collision resistance) is infeasible. Hence hashes fingerprint stored passwords, verify file integrity, and underpin digital signatures and blockchain.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Menezes、van Oorschot、Vanstone《Handbook of Applied Cryptography》（CRC Press）
Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography, CRC Press
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-1-4398-2191-6 (CRC Press)
#哈希函数 #单向函数 #抗碰撞
容斥原理是什么？
What is the principle of inclusion–exclusion?
容斥原理通过交替加减交集来准确计算若干集合并集的大小，避免重复计数。它是概率与组合计数的基本技术。
Inclusion–exclusion computes a union's size by alternately adding and subtracting intersections, avoiding double counts. It is basic to probability and counting.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#组合 #容斥 #集合
为什么规定 0! = 1？
Why is 0! defined to equal 1?
这不是随意规定，而是为了保持递推一致：n! = n·(n−1)!，代入 n=1 得 1! = 1·0!，所以 0! 必须等于 1。它也让组合数公式 C(n,0)=n!/(0!·n!)=1、排列计数和泰勒展开在边界情形自然成立——例如“从 n 个东西里选 0 个”恰好只有一种做法。
This is not arbitrary but keeps the recurrence consistent: n! = n·(n−1)!, and plugging n=1 gives 1! = 1·0!, forcing 0! = 1. It also makes the binomial formula C(n,0)=n!/(0!·n!)=1, permutation counts, and Taylor series work naturally at boundary cases—choosing 0 items out of n has exactly one way.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#阶乘 #组合数 #递推关系
递推关系是什么？
What is a recurrence relation?
递推关系用前几项定义后面的项，如斐波那契数列 F_n = F_{n-1} + F_{n-2}。许多自然与算法问题都可用递推建模并求解通项。
A recurrence defines later terms from earlier ones, e.g. the Fibonacci rule F_n = F_{n-1} + F_{n-2}. Many natural and algorithmic problems are modeled and solved this way.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#组合 #递推 #数列
怎样用图论给考试安排时间表？
How can graph theory be used to schedule exams?
把每门考试当作一个顶点，若两个考试由同一位学生参加，就在它们之间连一条边，得到“冲突图”。排时间表就是给顶点染色，使相邻顶点颜色不同，颜色代表时间段；所需的最少颜色数称为色数。贪心算法结合这类图往往接近最优，可以快速得到可行的时间表。
Represent each exam as a vertex and connect two exams if a student takes both, forming a “conflict graph”. Scheduling is then vertex coloring with adjacent vertices in different colors, each color being a time slot; the minimum number of colors needed is the chromatic number. Greedy algorithms perform well on these graphs, quickly producing feasible timetables.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#图着色 #色数 #排课问题
为什么 (a+b)ⁿ 展开后每一项的系数恰好是组合数？
Why are the coefficients of (a+b)ⁿ exactly binomial coefficients?
展开 (a+b)ⁿ 相当于从 n 个因子中每一个都选 a 或 b。要得到 aᵏb^(n−k)，只需在 n 个位置里挑出 k 个放 a，共有 C(n,k) 种选择，所以系数是组合数。这也解释了杨辉三角的递推 C(n,k)=C(n−1,k−1)+C(n−1,k)。
Expanding (a+b)ⁿ means choosing a or b from each of the n factors. To form the term aᵏb^(n−k) you must pick k of the n positions for a, giving exactly C(n,k) choices—so the coefficient is a binomial coefficient. This also explains Pascal's triangle recurrence C(n,k)=C(n−1,k−1)+C(n−1,k).
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
《什么是数学》(柯朗)（组合章）
What Is Mathematics? (Courant), chapter on combinatorics
独立核验依据 · Independent verification: 核验依据 2 DOUBAN ISBN 标识 9787309128109（按标识回读: 什么是数学（原作名 What Is Ma
#二项式定理 #组合数 #杨辉三角
帕斯卡三角形与二项式定理之间有什么联系？
What is the connection between Pascal's triangle and the binomial theorem?
帕斯卡三角形中第n行第k个数恰好是二项式展开里x的k次方的系数，即组合数。它把代数中的二项式定理与组合数递推直观对应，相邻两项相加生成下一行。克努特与格雷厄姆等的《具体数学》详述了这一关系。
In Pascal's triangle the kth entry of row n is exactly the coefficient of x to the k in the binomial expansion, a combination number. It visually matches the binomial theorem with the recurrence that neighboring entries sum to form the next row. Knuth and Graham et al. in Concrete Mathematics detail this relation.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-03
来源 · Source
Knuth《The Art of Computer Programming, Vol. 1》；Graham、Knuth 与 Patashnik《Concrete Mathematics》
Knuth, The Art of Computer Programming, Vol. 1; Graham, Knuth & Patashnik, Concrete Mathematics
#帕斯卡三角形 #二项式定理 #组合数
为什么计算机的信息都用 0 和 1 表示？
Why do computers represent information with 0s and 1s?
电子电路最容易可靠地区分两种稳定状态（如高低电平），用二进制最抗干扰。一位 bit 有 2 个取值，n 位能表示 2ⁿ 种不同信息，文字、图片、声音都能编码成 0/1 串。香农同时证明，信息量本质上就是以比特为单位度量的。
Electronic circuits most reliably distinguish two stable states (e.g., high and low voltage), so binary representation resists noise best. One bit has 2 values; n bits encode 2ⁿ distinct messages, and text, images, and sound all reduce to 0/1 strings. Shannon also showed that information is fundamentally measured in bits.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#二进制 #比特 #信息编码
柯尼斯堡七桥问题为什么“无解”？欧拉是怎么证明的？
Why is the Seven Bridges of Königsberg problem impossible, and how did Euler prove it?
问题要求：不重复地走过七座桥，一次回到起点。欧拉 1736 年把它抽象成“图”：陆地是顶点，桥是边。他证明，要一笔走完所有边且回到起点，必须每个顶点都有偶数条边与之相连；而柯尼斯堡四块陆地连接的桥数分别是 3、3、3、5，全是奇数，所以不可能。
The task was to cross all seven bridges exactly once and return to the start. In 1736 Euler abstracted it into a graph: land masses as vertices, bridges as edges. He proved that to traverse every edge once and return, every vertex must have even degree — while Königsberg's four land masses had bridge counts of 3, 3, 3, and 5, all odd. Hence impossible.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
《什么是数学》(柯朗)（拓扑章：柯尼斯堡七桥）
What Is Mathematics? (Courant), topology (Königsberg bridges)
独立核验依据 · Independent verification: 核验依据 2 ISBN 9787309086232（豆瓣书目条目: 什么是数学）
#欧拉路径 #七桥问题 #图论
信息熵是怎样度量一条消息的信息量的？
How does information entropy measure the information content of a message?
香农定义一条消息的信息量为 −log₂(概率)：越罕见、越出乎意料的事件携带的信息越多。对所有可能事件求平均，就得到信息熵 H = −Σ pᵢ log₂ pᵢ，单位为比特。霍夫曼编码用二叉树为符号设计最短的、不会歧义的前缀码，其平均码长接近但不低于熵这个理论下限。
Shannon defined the information content of a message as −log₂(probability): rarer, more surprising events carry more information. Averaging over all possibilities gives the information entropy H = −Σ pᵢ log₂ pᵢ, measured in bits. Huffman coding builds a binary tree yielding the shortest unambiguous prefix codes, whose average length approaches but never falls below the entropy bound.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#信息熵 #香农 #霍夫曼编码
囚徒困境里，两个囚徒明明合作对大家都好，为什么却都选择背叛？
In the prisoner's dilemma, cooperation is better for both — so why do both prisoners defect?
因为每个囚徒都担心对方背叛：如果对方沉默，自己背叛能减刑；如果对方背叛，自己背叛能少受罚。无论对方怎么选，背叛都是对自己更好的选择，于是双方都背叛。这种“谁也不愿单方面改变”的状态就叫纳什均衡，即使它并不对整体最优。
Each prisoner fears the other's betrayal: if the other stays silent, defecting shortens one's own sentence, and if the other defects, defecting limits the damage. Whatever the other does, defection looks better, so both defect. This outcome, where nobody wants to change alone, is a Nash equilibrium — even though it is not optimal for the group.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
美国数学会(AMS)《博弈论与经济模型》
American Mathematical Society (AMS), Game Theory and Economic Modeling
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787100047876（豆瓣书目条目: 博弈论与经济模型）
#纳什均衡 #囚徒困境 #博弈论
一个 3×3 的方格棋盘,要求每行、每列都恰好染红两个格子,有多少种染色方案?
On a 3×3 grid of squares, each row and each column must contain exactly two colored squares. How many distinct colorings are possible?
按第一行选哪两列分类,再逐行用列的剩余容量递推。枚举可得总数为 6:本质上是 2-正则二部图的关联矩阵,对应 3 个元素上的完美匹配结构。
Fix which two columns are colored in the first row, then proceed row by row tracking the remaining capacity of each column. The count comes out to 6: such colorings are exactly the incidence matrices of 2-regular bipartite graphs on 3+3 vertices, whose structures correspond to perfect matching decompositions.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Stanley《Enumerative Combinatorics》第 1 卷第 4 章关于 (0,1)-矩阵与二部图计数的内容
Richard P. Stanley, Enumerative Combinatorics, Vol. 1, Chapter 4, on counting (0,1)-matrices via bipartite graphs
独立核验依据 · Independent verification: 核验依据 1 ISBN 9781139200561 (2012)
#组合计数 #棋盘染色
容斥原理如何用于计算不超过 N 且至少能被集合 {p1,…,pk} 中一个素数整除的整数个数？
How does inclusion–exclusion count the integers up to N divisible by at least one prime in {p1,…,pk}?
先算各素数各自倍数的个数 ⌊N/pi⌋，再对每对素数加上被两素数乘积整除的个数以修正重复计数，依此类推对三元组取负号……最终答案为 Σ (−1)^(|S|+1) ⌊N/∏_{i∈S} pi⌋，S 取遍非空子集。这就是埃拉托斯特尼筛分析复杂度的核心恒等式。
Start by counting multiples of each prime individually, ⌊N/pi⌋; add counts for pairwise products to correct double-counting, then subtract triple products, and so on—giving Σ (−1)^(|S|+1) ⌊N/∏_{i∈S} pi⌋ over all nonempty subsets S. This identity underlies the complexity analysis of the Sieve of Eratosthenes.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：此条未指向带版次的可引用著作（通识性内容、机构文件或未展开的英文书名），本库不提供独立书目出处；如需精确引用，需由编辑补全具体篇目与版次。
Stanley, R. P. (2012). Enumerative Combinatorics, Volume 1 (2nd ed.). Cambridge University Press, Section 2.1.
Stanley, R. P. (2012). Enumerative Combinatorics, Volume 1 (2nd ed.). Cambridge University Press, Section 2.1.
#容斥原理 #整除计数
杨辉三角（帕斯卡三角）是什么？
What is Pascal's triangle?
杨辉三角是把数字排成三角形，每个数是它上方两数之和。它出现在组合数、二项式展开和概率中，是中国古代数学的重要成果。
Pascal's triangle arranges numbers so each is the sum of the two above. It appears in combinations, binomial expansions and probability—an ancient Chinese mathematical achievement.
难度 入门 · 适合 幼儿(3-6)
CC BY 4.0 · 已核验 · Verified 2026-08-23 · 2 条独立证据
来源 · Source
Graham, Knuth, Patashnik,《Concrete Mathematics》第2版,Addison-Wesley,1994
R. L. Graham et al., Concrete Mathematics, 2nd ed., Addison-Wesley, 1994
独立核验依据 · Independent verification: 核验依据 2 OPENLIBRARY 标识 /works/OL3951639W：Concrete mathematics（按标
#组合 #三角 #二项式