两城间红航蓝航恰有一家直达，从A到E坐红航需四趟航班，证：两城间坐蓝航至多两趟航班

dodonaomikiki · 发表于 2022-8-1 00:32

本帖最后由 dodonaomikiki 于 2022-8-1 03:47 编辑

但觉得这种做法有枚举之嫌，
因为还没有枚举完

且四城情形之下，剩下地16城怎么办？

难道不用考虑？

dodonaomikiki · 发表于 2022-8-2 12:33

针对三城情形中的这一类

要保证剩余的17城中，
有两座城市，一座与A，M皆通红杭，一座与M，E之间也皆为红航，她们之间则是兰航

dodonaomikiki · 发表于 2022-8-2 12:35

针对三城情形中的这一类

要保证剩余的17城中，
有两座城市，一座与A红杭，与M兰航，一座与M红航，她们之间则是红航

dodonaomikiki · 发表于 2022-8-2 12:36

那么，12楼，13楼，都存在这样一个问题：

在剩余的17城中，
是否一定能保证，有这样的两个城市呢？如果没有呢？
这是我认为解题中存在的巨大隐患！
不晓得，怎么解决？

dodonaomikiki · 发表于 2022-8-7 11:49

本帖最后由 dodonaomikiki 于 2022-8-7 11:58 编辑

进行再思考：

实际上，通往某个城市，
不可能全是兰航，也不可能全部是红杭，
要不然，不是·亚瑟不能抵达，就是玛莎不能抵达

dodonaomikiki · 发表于 2022-8-7 11:57

对于7楼，进行再度深入思考：

我们到目前为止，
都是对三四座城市进行

有目的

的极具针对性地思考，
说白啦，针对性极强

这本身木有什么，
可是剩余的一些城市，就不用思考吗？她们是一种什么情况呢？

比如7楼打了紫色问号的“剩余城市”，
都是出现了两个红航！
但谁能保证剩余城市中有两座城市一定（至少）有两个红航？万一只有一个红航呢？
或者说，剩余城市中只有一座城市只有两个红杭剩余的都至少有三个红航呢？
到底是一种什么情况？
为什么是这种情况？该如何证明？
说白啦，是不是也需要用数学手段证明剩余的17城或者16城的兰航红航分布分配的情形？
果真如此，这将是一件极其困难的事情

dodonaomikiki · 发表于 2022-8-7 11:58

题目是到好体，承认！不错

小fisher · 发表于 2022-8-8 10:50

本帖最后由小fisher 于 2022-8-8 11:59 编辑

20座城市之间可以有20*19/2=190条航线
如上图，20座城市除去A城、E城外，剩余18座城市可以编号为Bn, Cn, Dn (n=0,1,2,3,....)，与A城有直飞红航航班的城市编为Bn，与E城有直飞红航航班的城市编为Dn，其余编为Cn，要满足题设条件亚瑟乘坐红航从A城到E城需要乘坐四个航班，红航只能执飞开头字母相同或相邻的两座城市之间的航班。
在最极端的情况下，开头字母相同和相邻任意两座城市之间的航班全部为红航，假设字母B、C、D开头的城市各有6座（城市数量多少不影响结论），可以形成129条红航航线，但从A城到E城最短的行程仍然必须按A-Bn-Cn-Dn-E的顺序，至少乘坐4趟航班，题设成立；而蓝航虽然只有61条航线，但可以保证任意两座城市之间可以直达（开头字母不相同也不相邻的任意两座城市，如A-Cn，A-Dn，Bn-Dn， Bn-E，Cn-E）或只经A城或E城中转一次到达（Bn-Bn，Bn-Cn, Cn-Cn可以通过E城中转；Cn-Cn, Cn-Dn, Dn-Dn可以通过A城中转），结论成立。
把上面的任意一条或多条红航变为蓝航，只要满足上面的规则，题设和结论始终成立。

小fisher · 发表于 2022-8-8 12:21

最极端的情况是编号为字母B和/或D开头的城市只有1座，此时若开头字母相同和相邻任意两座城市之间的航班全部为红航，最多可以形成1+1+16+16+C(16,2)=154条红航航线，此时蓝航航线为36条

Nicolas2050 · 发表于 2022-8-8 13:26

用图论里的染色理论不就可以解决？

		自动登录	找回密码
密码			注册

两城间红航蓝航恰有一家直达，从A到E坐红航需四趟航班，证：两城间坐蓝航至多两趟航班

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

点评

点评