※ 引述《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://webptt.com/m.aspx?n=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