[其他] 離散一題

看板Math作者LiquidTLO (俊偉)時間3年前 (2020/09/18 13:41)推噓0(0推 0噓 5→)

留言5則, 1人參與討論串7/15 (看更多)

題目: 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] 這裡就卡住了請問是從哪步開始錯? 應該如何改? -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.230.220.98 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1600407693.A.AC0.html ※ 編輯: LiquidTLO (125.230.220.98 臺灣), 09/18/2020 13:42:04 ※ 編輯: LiquidTLO (125.230.220.98 臺灣), 09/18/2020 13:42:42 ※ 編輯: LiquidTLO (125.230.220.98 臺灣), 09/18/2020 13:43:36

→

hwanger

09/19 00:33, 3年前 , 1^F

09/19 00:33, 1^F

→

hwanger

09/19 00:35, 3年前 , 2^F

09/19 00:35, 2^F

→

hwanger

09/19 00:35, 3年前 , 3^F

09/19 00:35, 3^F