數學 « Tornado

Blog
About

100個定理

2007年12月15日 at 15:26 | Posted in 數學 | Leave a comment

Originally from: The Hundred Greatest Theorems

序號	定理名稱	範疇	證明年份
1	2的開方是無理數	基礎代數	500 B.C.
2	代數基本定理	代數	1799
3	有理數集是可數集	基礎集論	1867
4	勾股定理	幾何	500 B.C.
5	質數定理	數論	1896
6	哥德爾不完全性定理	集論	1931
7	二次互反律	數論	1801
8	尺規作圖不能三等分角及倍立方體	代數	1837
9	圓面積	幾何	225 B.C.
10	費馬小定理的歐拉的一般化 (費馬小定理)	基礎數論	1760(1640)
11	質數有無限個	基礎代數	300 B.C.
12	平行公理的獨立性	幾何	1870-1880
13	多面體公式	立體幾何	1751
14	Euler’s Summation of 1 + (1/2²) + (1/3²) + …. = π² / 6	分析數論	1734
15	微積分基本定理	微積分	1686
16	一般一元五次或以上方程不可解	抽象代數	1824
17	棣美弗定理	基礎代數（複數）	1730
18	劉維爾定理及構作超越數	代數數論	1844
19	四平方和定理	基礎數論	1770
20	形式如4n+1的質數是兩個平方數之和	基礎數論	?
21	Green’s Theorem	數學分析	1828
22	The Non-Denumerability of the Continuum （實數數目不可數）	基礎集論	1874
23	勾股三數組的公式	基礎數論	300 B.C.
24	連續統假設	集論	1963
25	Schroeder-Bernstein Theorem (injective and bijective)	基礎集論	?
26	Leibnitz’s Series for π	數學分析	1674
27	三角形內角和	平面幾何	300 B.C.
28	Pascal’s Hexagon Theorem	投影幾何	1640
29	Feuerbach’s Theorem	投影幾何	1822
30	The Ballot Problem	組合數學	1887
31	Ramsey theorem	組合數學	1930
32	四色定理	圖論	1976
33	費馬最後定理	代數數論	1993
34	調和級數的發散性(1/1 + 1/2 + 1/3 –> infinity)	分析數論	1350
35	泰勒定理	微積分	1715
36	不動點定理	拓撲學	1910
37	三次方程的解	基礎代數	1500
38	算術級數/幾何級數(Proof by Backward Induction)(Polya的證明)	組合數學	??
39	Solutions to Pell’s Equation	數論	1759
40	Minkowski’s Fundamental Theorem	幾何數論	1896
41	Puiseux’s Theorem	代數幾何	1850
42	三角形數的倒數之和	基礎代數	1672
43	等周定理	基礎幾何／分析	1838
44	二項式定理	組合數學	1665
45	The Partition Theorem	組合數論	1740
46	一般四次方程的解	基礎代數	1545
47	The Central Limit Theorem	統計學	?
48	抽屜原理	組合數學	1837
49	The Cayley-Hamilton Theorem	抽象代數	1858
50	正多面體的數目	立體幾何	400 B.C.
51	威爾遜定理	基礎數論	1773
52	集的子集數目	組合數學	?
53	π是超越數	代數數論	1882
54	七橋問題	圖論	1736
55	Intersecting chord theorem	平面幾何	300 B.C.
56	The Hermite-Lindemann Transcendence Theorem	代數數論	1882
57	海倫公式	平面幾何	75
58	組合數目的公式:C(n,r)	組合數學	?
59	大數法則	概率	<many>
60	Bezout’s Theorem	代數幾何	?
61	塞瓦定理	平面幾何	1678
62	Fair Games Theorem	????	?
63	Cantor’s Theorem	集論	1891
64	洛必達法則	微積分	1696?
65	等腰三角形定理	平面幾何	300 B.C.
66	幾何級數之和	基礎代數	260 B.C.?
67	e是超越數	代數	1873
68	算術級數和	基礎代數	1700 B.C.
69	輾轉相除法	基礎數論	300 B.C.
70	完美數定理	數論	300 B.C.
71	子群的階 (Order of a Subgroup)	抽象代數	1802
72	Sylow’s Theorem	抽象代數	1870
73	Ascending or Descending Sequences	組合數學	1935
74	數學歸納法的原理	集論	1321
75	平均值定理	數學分析	1823
76	傅立葉級數	數學分析	1811
77	k次方之和 (1^k + 2^k + … + n^k )	組合數學／數論	1713
78	柯西—施瓦茨不等式	代數	1814?
79	中值定理	微積分	1821
80	算術基本定理（質因數連乘式是唯一和存在的）	基礎數論	300 B.C.
81	Divergence of the Prime Reciprocal Series (1/2 + 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + …)	分析數論	1734?
82	Dissection of Cubes (J.E. Littlewood’s ‘elegant’ proof)(Waring’s problem for cubes)（每個正整數都可以寫成五個立方數的和）	基礎數論	1940
83	友誼定理(The Friendship Theorem)	組合數學	1966
84	Morley’s Theorem	平面幾何	1899
85	除以3的原則	基礎數論	?
86	Lebesgue Measure and Integration	微積分	1902
87	Desargues’ Theorem	投影幾何	1650
88	Derangements Formula	組合數學	?
89	The Factor and Remainder Theorems	基礎代數	?
90	Stirling’s Formula	數學分析	1730
91	三角不等式	幾何	?
92	皮克定理 (Pick’s theorem)	組合幾何	1899
93	生日問題	組合數學／概率	?
94	餘弦定理	平面幾何	1579
95	托勒密定理 (Ptolemy theorem)	平面幾何	120?
96	容斥原理（inclusion-exclusion principle）	組合數學	?
97	克萊姆法則 Cramer’s Rule	線性代數	1750
98	Bertrand’s Postulate （n和2n之間至少有一個質數）	組合數論	1860?
99	比豐投針問題	概率	1733
100	Descartes Rule of Signs	基礎代數	1637

海盜分金幣

2007年11月18日 at 08:35 | Posted in 數學 | Leave a comment

定義情況C_n,m：n個海盜分m枚金幣。稱呼這些海盜為P₁, P₂, …, P_n-1, P_n。由P_n制定分配的規則，如果不同意的人數多於或等於同意者的數目，P_n得要被槍殺，然後退到情況C_n-1,m。

每個海盜都是理性和遵守約定的，不會冒險，而且他們判斷時，不同事物對其重要性如下：（由較重要到不重要）

自己的性命
自己的利益
死亡的人數（海盜認為越來越人受害越好）

設f(n,m,k)為P_k在C_n,m會得到的金幣數目（若他必死，f(n,m,k)=-∞，若f(n,m,k)不確定，則函數無值），其中m>0, n>>1。

當m>>n>>1時，f(n,m,n)的值。
給定m，對於哪些n，P_n必死？有f(n,m,n)=0？

分n為單雙數考慮：
1. f(2k+1,m,2k+1) = m – k – 1 ：在C_2k,m，會有k-1個海盜必定得到0枚金幣。所以在C_2k+1,m，給那些海盜1枚金幣便能獲其支持。再加上自身，支持P_n的人便有k個。已知隨意選擇一個 i 符合 f(2k,m,i)=1，給予P_i 2枚金幣，也得到其支持了。到在C_2k,m的情況。
2. f(2k,m,2k) = m-k ：在C_2k-1,m，有k-2個海盜可能得到0枚金幣，這些海盜是在C_2k-2,m得到非零枚金幣的人。儘管這些可能得0枚金幣的人中，最終必定有剛好一個海盜在C_2k-1,m剛好得到2枚金幣，但在C_2k,m未退到C_2k-1,m前，那些可能者都不知自己在C_2k-1,m會得到2枚還是0枚金幣。以不冒險的原則，他們便會接受1枚金幣的安排。
留意各種邊界情況：
- f(2m-2, m ,2m-2) = 1 , f(2m-1, m ,2m-1) = 0 , f(2m, m ,2m) = 0 且 f(2m, m ,2m-1) = 0 。
- f(2m+1, m ,2m+1)=0，因為在C_2m,m的錢幣分配是確定的，只要P_2m+1的安排是 f(2m, m, i)=0 => f(2m+1, m, i)=1 ，便得到m個人支持，再加起自己，共有m+1人支持，可保性命。
- f(2m+2,m,2m+2)=-∞ 到了C_2m+2,m，在f(2m+1, m , i ) = 0 的i的值共有m+1個，而P_2m+2只可分配m枚金幣，怎樣分最多也是m+1人支持自己。
- f(2m+3,m,2m+3)=0 ！因為P_2m+2不想死，他只有支持P_2m+3。將m個金幣分配給P_i，其中 i 使得 f(2m+1, m , i ) = 0，以獲得m個人支持（這可以隨便分）。於是便有m+2人支持P_2m+3。
- f(2m+k,m,2m+k)= -∞ !? 且慢。在C_2m+7，P_2m+4, P_2m+5, P_2m+6, P_2m+7會支持，結果他們又能活下來。f(2m+k,m,2m+k) = 0 for k=2^r

n /P_i	1	2	3	4	5	6	7	8	9
1	100
2		-∞
3	0	0	100
4	1	1	0	98
5	2 or 0	0 or 2	1	0	97
6	1	1	0	1	0	97
7	2 or 0	2 or 0	1	0 or 2	1	0	96
8	1	1	0	1	0	1	0	96
9	2 or 0	2 or 0	1	2 or 0	1	2 or 0	1	0	95

參考：

http://gezhi.org/node/477
http://www.oursci.org/ency/math/001.htm

Favorite problems from Scottish Book

2007年10月05日 at 03:26 | Posted in 數學 | Leave a comment

Scottish Book (pdf)

Scottish Book #19 Problem; Mazur-Orlicz
Is a matrix, finite in each row and invertible (in a 1 to 1 way), equivalent to a normal matrix?

Scottish Book #19 Problem; Ulam
Is a solid of uniform density which will float in water in every position a sphere?

Scottish Book #38 Problem; Ulam
Given N elements (persons). To each person we attach K others among the given N at random (these are friends of a given person). What is the probability P_{kN} that from every element through a chain of mutual friends? (The relation of fdship is not necessarily symmetric.) Find lim N->infy P_kN = 0 or 1?

Scottish Book #152 Problem; Steinhaus
A disc of radius 1 covers at least 2 and at most 5 lattice points.
If we translate this disc through vector nw (n=1,2,3,…), where w has both coordinates irrational and their ratio is irrational, then the numbers 2,3,4 repeat infinitely many times. Frequency of these events for n-> infy? Does it exist? If not, give a counter-example.