什么是鸽巢原理的推广形式？它在组合证明中如何发挥作用？
What is the generalized pigeonhole principle, and how does it function in combinatorial proofs?
推广鸽巢原理：把 n 个物体放入 k 个盒子，则至少有一盒含至少 $\lceil n/k\rceil$ 个物体。它无需构造即可保证某种重复或聚集存在，常用于证明存在性，例如证明任意 5 个整数中必有 2 个之和被 4 整除。
The generalized pigeonhole principle says that placing n objects into k boxes forces some box to hold at least $\lceil n/k\rceil$ objects. Without construction it guarantees repetition or concentration, and is used for existence proofs, e.g. showing that among any 5 integers two have a sum divisible by 4.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
《组合数学》Brualdi
Introductory Combinatorics by Richard Brualdi
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111377870（豆瓣书目条目: 组合数学）
#鸽巢原理 #存在性 #组合
什么是 NP 问题？
What is an NP problem?
在复杂性理论中，NP 指那些“答案可以被快速验证”的问题类；著名的 P vs NP 问题问：是否每个可快速验证的问题也都可快速求解。它被列为千年大奖难题之一。
In complexity theory, NP is the class of problems whose answers can be quickly verified; the famous P vs NP question asks whether every quickly verifiable problem can also be quickly solved. It is one of the Millennium Prize Problems.
难度 专业 · 适合 高中(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（按标
#NP #复杂性 #计算机
图灵如何证明停机问题是不可判定的？
How did Turing prove that the halting problem is undecidable?
图灵在1936年设想一种通用机，并假设存在判定任意程序是否停机的算法。他构造出若自身停机则不停机、若不停机则停机的自指程序，导出矛盾，从而证明这样的算法不存在。图灵的原始论文与西普塞的书是权威来源。
In 1936 Turing imagined a universal machine and assumed an algorithm deciding whether any program halts. He constructed a self-referential program that halts if and only if it does not, yielding a contradiction, so no such algorithm exists. Turing's original paper and Sipser's book are authoritative sources.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-03
来源 · Source
Turing《On Computable Numbers》（1936，Proc. London Math. Society）；Sipser《Introduction to the Theory of Computation》
Turing, On Computable Numbers (1936, Proc. LMS); Sipser, Introduction to the Theory of Computation
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL19859284W：Introduction to the th
#停机问题 #不可判定 #图灵机
什么是图论？
What is graph theory?
图论研究由“点”（顶点）和连接点的“线”（边）构成的图形结构及其性质。它被用于社交网络分析、地图着色、最短路径和电路设计等。
Graph theory studies structures made of points (vertices) connected by lines (edges) and their properties. It is used in social network analysis, map coloring, shortest-path problems, and circuit design.
难度 专业 · 适合 高中(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 is algorithmic complexity?
算法复杂度衡量算法随输入规模增长所需的资源（时间或空间），常用大 O 记号表示，如 O(n) 或 O(n²)。它帮助我们比较不同算法在大数据量下的效率。
Algorithmic complexity measures the resources (time or space) an algorithm needs as the input size grows, often expressed with big-O notation such as O(n) or O(n²). It helps compare the efficiency of different algorithms on large inputs.
难度 专业 · 适合 高中(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（按标
#复杂度 #大O #算法
P与NP问题的核心疑问是什么，库克对此做出了什么贡献？
What is the central question of P versus NP, and what did Cook contribute?
P与NP问题询问：能被快速验证的解，是否也能被快速找到，即NP是否等于P。库克在1971年证明布尔可满足性问题（SAT）是NP完全，意味着它是所有NP问题中最难的一类。西普塞的教材系统阐述了这一计算复杂性理论。
P versus NP asks whether solutions that can be quickly verified can also be quickly found, that is, whether NP equals P. Cook proved in 1971 that Boolean satisfiability (SAT) is NP-complete, meaning it is among the hardest problems in NP. Sipser's text systematically presents this computational complexity theory.
难度 专业 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-03
来源 · Source
Cook《The complexity of theorem-proving procedures》（1971，STOC）；Sipser《Introduction to the Theory of Computation》
Cook, The complexity of theorem-proving procedures (1971, STOC); Sipser, Introduction to the Theory of Computation
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL19859284W：Introduction to the th
#P与NP #NP完全 #计算复杂性
什么是拉姆齐定理？它如何说明「完全无序」不可能存在？
What is Ramsey's theorem, and how does it show that complete disorder is impossible?
拉姆齐定理指出：对任意整数 r，存在数 R(r) 使得任意 r 色完全图的边着色必含单色完全子图 $K_r$。换言之，只要规模足够大，任何着色结构都必然出现某种有序（同色团），说明在足够大的系统中完全无规律的模式不可能存在。
Ramsey's theorem states that for any r there is a number R(r) such that any r-coloring of the edges of a sufficiently large complete graph contains a monochromatic $K_r$. In other words, beyond a certain size every coloring necessarily contains an ordered monochromatic clique, so complete disorder is impossible in large enough systems.
难度 专业 · 适合 大众
CC BY 4.0 · 来源待核验 · Source pending review
来源 · Source
出处备注：著录仅给书名，无版次与年份；同一书名常对应多个版次，不臆测具体版本。
《拉姆齐理论》Graham、Rothschild 与 Spencer
Ramsey Theory by Graham Rothschild and Spencer
#拉姆齐 #单色 #组合
什么是二项式系数？它在组合计数中如何表示「从 n 个中选 k 个」？
What is a binomial coefficient, and how does it represent choosing k from n in combinatorial counting?
二项式系数 $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ 计数从 n 个不同元素中无序选取 k 个的方式数。它出现在二项式展开 $(a+b)^n=\sum\binom{n}{k}a^{n-k}b^k$ 中，也用于概率（如超几何分布）与帕斯卡三角形的递推。
The binomial coefficient $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ counts the ways to choose k items from n without order. It appears in the binomial expansion $(a+b)^n=\sum\binom{n}{k}a^{n-k}b^k$ and in probabilities such as the hypergeometric distribution and Pascal's triangle recurrence.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
《组合数学》Brualdi
Introductory Combinatorics by Richard Brualdi
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111377870（豆瓣书目条目: 组合数学）
#二项式系数 #组合 #计数
欧拉如何通过分析柯尼斯堡七桥问题开创图论？
How did Euler's analysis of the Königsberg bridges problem found graph theory?
欧拉把柯尼斯堡七桥抽象为顶点与边，证明若能一笔画走完所有桥，至多两个顶点的度必须为奇数。这一把实际问题转化为拓扑图结构的思路，被公认为图论的开端。欧拉1736年的论文与迪斯特尔的《图论》都是标准文献。
Euler abstracted the Königsberg seven bridges into vertices and edges, proving that a walk using every bridge once is possible only if at most two vertices have odd degree. This recasting of a practical puzzle into a topological graph structure is regarded as the birth of graph theory. Euler's 1736 paper and Diestel's Graph Theory are standard references.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-10-04
来源 · Source
Euler《Solutio problematis ad geometriam situs》（1736）；Diestel《Graph Theory》
Euler, Solutio problematis ad geometriam situs (1736); Diestel, Graph Theory
独立核验依据 · Independent verification: 核验依据 1 ISBN 9783662575604 (2018)
#柯尼斯堡七桥 #图论 #一笔画
什么是图灵机？它如何为「可计算性」提供形式化定义？
What is a Turing machine, and how does it formalize the notion of computability?
图灵机是一条无限纸带加一个按状态表读写移动的读写头，构成最小通用计算模型。丘奇-图灵论题认为任何可有效计算的函数都能被某图灵机计算，从而把直觉的可计算精确化为机械可模拟，是计算理论与复杂性分支的基石。
A Turing machine is an infinite tape plus a read-write head that moves according to a state table, forming a minimal universal model of computation. The Church-Turing thesis holds that any effectively computable function is computable by some Turing machine, formalizing intuitive computability as mechanically simulable and underpinning computability and complexity theory.
难度 进阶 · 适合 高中(15-18)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
《计算理论导引》Sipser
Introduction to the Theory of Computation by Michael Sipser
独立核验依据 · Independent verification: 核验依据 1 ISBN 9787111499718（豆瓣书目条目: 计算理论导引）
#图灵机 #可计算性 #丘奇-图灵
什么是排列与组合？
What are permutations and combinations?
排列关注“顺序重要”的选取方式，组合关注“顺序无关”的选取方式。例如从 3 人中选 2 人排队是排列，选 2 人组成小组是组合。
Permutations count selections where order matters, while combinations count selections where order does not matter. For example, choosing 2 of 3 people and lining them up is a permutation, whereas choosing 2 to form a group is a combination.
难度 进阶 · 适合 大众
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 an Eulerian circuit in graph theory, and what is the necessary and sufficient condition for its existence?
欧拉回路是经过每条边恰好一次并回到起点的闭合路径。对连通图，存在欧拉回路的充要条件是每个顶点的度数均为偶数。该结论源于欧拉对柯尼斯堡七桥问题的分析。
An Eulerian circuit is a closed trail that traverses every edge exactly once and returns to the start. For a connected graph, such a circuit exists iff every vertex has even degree. This result originated from Euler's analysis of the Königsberg bridge problem.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
《图论》Diestel
Graph Theory by Reinhard Diestel
独立核验依据 · Independent verification: 核验依据 1 ISBN 9783662575604 (2018) · 核验依据 2 ISBN 9780582249936 (1996)
#欧拉回路 #图论 #度数
什么是四色定理？它的计算机辅助证明为何引发争议？
What is the four-color theorem, and why did its computer-assisted proof spark controversy?
四色定理称任何平面图可用四种颜色给区域着色使相邻区域不同色。阿佩尔与哈肯 1976 年的证明把问题归约为近 2000 个可约构型并交由计算机穷举验证，因人类无法逐行核对全部计算而引发「何为证明」的哲学争论，直至后来被独立重现。
The four-color theorem asserts any planar map can be colored with four colors so adjacent regions differ. Appel and Haken's 1976 proof reduced the problem to about 2000 reducible configurations verified by computer, sparking debate over what counts as proof since humans could not check every computation by hand, until later independently reproduced.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
《图论》Diestel
Graph Theory by Reinhard Diestel
独立核验依据 · Independent verification: 核验依据 1 ISBN 9783662575604 (2018) · 核验依据 2 ISBN 9780582249936 (1996)
#四色定理 #计算机证明 #平面图
什么是树？在计算机网络设计中它有什么用途？
What is a tree, and what is its use in computer network design?
树是连通且无环的图，n 个顶点的树恰有 n-1 条边，任意两点间唯一路径。生成树以最少链路连通所有节点且无回路，可避免广播风暴，是网络路由与最小生成树算法（如 Prim、Kruskal）的基础。
A tree is a connected acyclic graph; a tree on n vertices has exactly n-1 edges and a unique path between any two nodes. A spanning tree connects all nodes with the fewest links and no cycles, avoiding broadcast storms, and underlies routing and minimum-spanning-tree algorithms such as Prim and Kruskal.
难度 进阶 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-10-03 · 2 条独立证据
来源 · Source
《算法导论》Cormen 等
Introduction to Algorithms by Cormen Leiserson Rivest and Stein
独立核验依据 · Independent verification: 核验依据 1 ISBN 978-0-262-04630-5 · 核验依据 2 ISBN 9780691079516 (1957)
#树 #生成树 #网络
什么是质数的埃拉托斯特尼筛法？
What is the Sieve of Eratosthenes?
埃拉托斯特尼筛法是一种找出一定范围内所有质数的古老算法：从小到大依次划去每个质数的倍数，剩下的就是质数。它简单高效，适合教学和小范围筛选。
The Sieve of Eratosthenes is an ancient algorithm for finding all primes up to a limit: repeatedly cross out the multiples of each prime in order, and what remains are primes. It is simple and efficient for teaching and small ranges.
难度 进阶 · 适合 大众
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 planar graph, and what property does Kuratowski's theorem characterize?
平面图是能画在平面上且边不相交的图。库拉托夫斯基定理给出判定：一个图是平面图当且仅当它不含与 $K_5$（五顶点完全图）或 $K_{3,3}$（完全二分图）同胚（即细分）的子图，从而把拓扑可平面性转化为组合禁止子式。
A planar graph can be drawn on the plane with no crossing edges. Kuratowski's theorem characterizes this: a graph is planar iff it contains no subgraph homeomorphic (a subdivision) of $K_5$ (the complete graph on five vertices) or $K_{3,3}$ (the complete bipartite graph), turning topological planarity into a combinatorial forbidden-subdivision condition.
难度 进阶 · 适合 大众
CC BY 4.0 · 已核验 · Verified 2026-10-04 · 2 条独立证据
来源 · Source
《图论》Diestel
Graph Theory by Reinhard Diestel
独立核验依据 · Independent verification: 核验依据 1 ISBN 9783662575604 (2018) · 核验依据 2 ISBN 9780582249936 (1996)
#平面图 #库拉托夫斯基 #禁止子式
鸽巢原理最简单的表述是什么，它能推出什么有趣结论？
What is the simplest statement of the pigeonhole principle, and what interesting conclusions follow?
鸽巢原理说，若把多于n个物体放进n个盒子，必有某个盒子含至少两个物体。它看似平凡，却能证明如任意367人中必有同生日者，或抽屉里袜子配对的日常结论。格雷厄姆与格里马尔迪的离散数学教材都以其为题引入组合推理。
The pigeonhole principle says that if more than n objects are placed into n boxes, some box holds at least two objects. Trivial as it sounds, it proves things like two people sharing a birthday among any 367, or finding a matching pair of socks. Graham and Grimaldi introduce combinatorial reasoning with it.
难度 入门 · 适合 初中(12-15)
CC BY 4.0 · 已核验 · Verified 2026-11-02
来源 · Source
Graham、Rothschild 与 Spencer《Ramsey Theory》；Grimaldi《Discrete and Combinatorial Mathematics》
Graham, Rothschild & Spencer, Ramsey Theory; Grimaldi, Discrete and Combinatorial Mathematics
独立核验依据 · Independent verification: 核验依据 1 OPENLIBRARY 标识 /works/OL1901959W：Discrete and combinator
#鸽巢原理 #组合数学 #抽屉原理
什么是维恩图？
What is a Venn diagram?
维恩图用互相重叠的圆来表示集合及其交、并、补等关系，便于直观理解集合运算。例如两个圆的重叠部分表示两个集合的公共元素。
A Venn diagram uses overlapping circles to represent sets and their intersections, unions, and complements, making set operations easy to visualize. For example, the overlap of two circles shows the common elements of the two sets.
难度 入门 · 适合 大众
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 binary?
二进制是一种只用 0 和 1 两个数码表示数的记数系统，是计算机内部数据的基础。例如二进制的 101 等于十进制的 5。
Binary is a number system using only the digits 0 and 1, and it is the basis of data inside computers. For example, the binary number 101 equals 5 in decimal.
难度 入门 · 适合 大众
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（按标
#二进制 #计算机 #记数法