Re: [其他] 離散一題
※ 引述《LiquidTLO (俊偉)》之銘言:
: 題目:
: There are n cities(n >= 2) such that
: for every pair of cities X and Y,
: either X had road to Y(X->Y) or Y had road to X(Y->X).
: Prove that there existed a city reachable
: from every other city by traveling at most 2 roads.
: 想法: using strong induction(但中間卡住)
: P(n): ∃c[i] reachable from c[j], j∈{1,2,...,n}-{i} through at most 2 roads
: Base Case:
: P(2): c[1]->c[2] or c[2]->c[1] -> True
: Induction Hypothesis:
: Assume P(k) is true for all 2<k<n
: Inductive Step:
: Assume n cities.
: Remove 1 city c[n] and all roads to or away from it.
: By P(k), ∃c[y], y∈{1,2,...,n-1},
: reachable from c[z], z∈{1,2,...,n-1}-{y}
: Let A be the set of cities with 1 road to c[y].
: Let B be ... with 2 road to c[y].
: Let c[b] be cities in B, c[a] be cities in A.
: That is, c[b]->c[a]->c[y]
: If c[n]->c[y], at most 1 road -> True
: If c[n]->c[a], then c[n]->c[a]->c[y], at most 2 roads -> True
: If c[n]->c[b], c[n]->c[b]->c[a]->c[y] 這裡就卡住了
: 請問是從哪步開始錯?
: 應該如何改?
The notation is the same as above.
c[n] has the road to c[y] or c[y] has the road to c[n] by assumptoin.
There is nothing needed to prove for the first case.
For the second case, there are two situations:
(1) there exists a city c[a] in A such that c[n] has the road to c[a].
(2) for each city c[a] in A, c[a] has the road to c[n].
For the case (1), c[y] can be reached from c[n] through c[a] and
c[y] can be reached from other cities in A or B at most two roads by
the induction hypothesis.
For the case (2), c[n] can be reached from c[y] and all cities in A.
On the other hand, given a city c[b] in B, there exists a city c[a] in A
such that c[b] had the road to c[a]. Then c[n] can be reached from c[b]
through this c[a].
Therefore c[n] is the desired city satisfying the statement in the case (2).
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.216.128.156 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1600411565.A.649.html
※ 編輯: zhanguihan (61.216.128.156 臺灣), 09/18/2020 14:46:52
※ 編輯: zhanguihan (61.216.128.156 臺灣), 09/18/2020 14:52:40
※ 編輯: zhanguihan (61.216.128.156 臺灣), 09/18/2020 14:54:09
→
09/18 15:01,
3年前
, 1F
09/18 15:01, 1F
→
09/18 15:01,
3年前
, 2F
09/18 15:01, 2F
推
09/18 16:04,
3年前
, 3F
09/18 16:04, 3F
→
09/18 16:05,
3年前
, 4F
09/18 16:05, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容:
其他
0
5
完整討論串 (本文為第 8 之 15 篇):
其他
1
1
其他
0
3
其他
8
28
其他
0
24
其他
0
5
其他
1
4
其他
0
23
其他
1
39