作者LiquidTLO (俊伟)
看板Math
标题[其他] 离散一题
时间Fri Sep 18 13:41:27 2020
题目:
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://webptt.com/cn.aspx?n=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
1F：→ hwanger : 不是很重要 下图并不针对原po的主要问题(zhanguihan 09/19 00:33
2F：→ hwanger : 大大已经回文) 而是针对原问题给出另一个证明(不过 09/19 00:35
3F：→ hwanger : 原po和z大合起来的证明非常漂亮) 09/19 00:35