※ 引述《pikahacker (Beat Cal)》之铭言： : 1. Prove that every tournament contains a Hamiltonian path. : (Tournament map: a directed graph such that for every pair of distinct vertices : u and v, there is either an edge from u to v or v to u, but never both.) : (I can prove this easily by double induction, but I heard there is a classic : proof by strong induction. How?) Excuse me...What is double induction? And strong induction? : 2. Given Bertrand's Theorem (there always exists a prime p such that n<p<2n n<p<=2n, for the case n=1 : for every n that is a positive integer), prove that all integers greater : than 6 can be written as the sum of one or more distinct primes. We want to prove that every integer n>=17 can be written as the sum of one or more distinct primes which are smaller than n-5. This can checked by brute force when n<33. Now use induction with it. If n>=33 and n=2k, there is some prime p in [k-2, 2k-7]. Then we have p >= n-p-5 and n-p>=17 when n-p >= p. Hence n-p can be written as the sum of some primes < p and therefore n can be written as the sum of some primes < n-5 If n>=33 and n=2k+1, there is some prime p in [k-2, 2k-7]. Then we have p >= n-p-5 and n-p>=17 when n-p >= p. Hence n-p can be written as the sum of some primes < p and therefore n can be written as the sum of some primes < n-5 This method fails when the theorem is slightly weaken, that is to say: "there always exists a prime such that n<=p<=2n." And, interestingly (Does this word exist?), it can be proved that Given any odd integer n>1, there is a subset S of positive integers such that 1. S contains only one even number 2 2. {3,5,...,n} is a subset of S. 3. For every positive integer m, there is an element s in both S and [m, 2m]. 4. There is a positive integer M such that M can not be written as the sum of some distinct elements in S. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 220.143.125.103 ※ 编辑: darkseer 来自: 220.143.125.103 (01/17 23:08) ※ 编辑: darkseer 来自: 220.143.125.103 (01/17 23:10)