推 pikahacker:thx 128.12.47.33 01/18
※ 引述《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)