作者jasonliao89 (宅宅)
看板Grad-ProbAsk
标题[理工] 离散 Hamiltonian Cycle 证明
时间Sun Aug 29 23:05:38 2021
https://i.imgur.com/3CGuxlf.jpg
https://i.imgur.com/T1ZMXNb.jpg
是我的证法，课本是用Gray code证的，我看起来跟我写的思路差不多。我自己觉得我的
写法是对的但有些不严谨。
我的思路是固定Q^k的HC顺序，然後按照HC顺序在两边走，以k=3为例
https://i.imgur.com/vSLC4he.jpg
想问一下我的这个证法是对的吗，如果错的话是错在哪呢，那如果是对的请问考试可以这
样写吗，谢谢。
然後我想顺便问一下这题
https://i.imgur.com/huAeNSv.jpg
我的理解是安排13个工作且一个人不能连续工作两天，然後总共不能做超过7个。解答我
看的懂，但我觉得不用这麽复杂
假设有A,B两个工人，那麽工作安排就是
ABABABABABABAB，故得证可以
这样不是就好了吗，请问我这样想正确吗，谢谢。
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 180.217.44.145 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1630249540.A.802.html
※ 编辑: jasonliao89 (180.217.44.145 台湾), 08/30/2021 01:05:44
1F：→ BusterButter: 第二题直觉上反而会想用鸽笼原理，把连续的两个分为 08/30 04:22
2F：→ BusterButter: 一组（剩下的一个自己为一组） 所以13个人有7组，所 08/30 04:22
3F：→ BusterButter: 以一个人最少要选8个才会保证选到2个同组的 08/30 04:22
4F：→ BusterButter: 反过来说就是如果不保证选到同组的，那每个人都必须 08/30 04:25
5F：→ BusterButter: 选少於8个 08/30 04:25
6F：→ BusterButter: 我觉得你的证明不够general，证明不能用举例子除非 08/30 04:27
7F：→ BusterButter: 你把所有可能性都列出来 08/30 04:27
8F：→ BusterButter: 我後来想一下我觉得我的证明有错XD，这样证好像只证 08/30 04:41
9F：→ BusterButter: 了必要，没有证明到充要 08/30 04:41