有一个由n个城市组成的王国,其某些城市之间有道路相连,满足:
(1)所有道路互不相交(若某两个城市间有道路相连,则称它们相邻);
(2)对任意两个城市都可以从一个城市出发沿道路走到另一个城市(中间可能经过其它城市);
(3)从任意一个城市出发,如果每一条道路至多利用一次的话,一旦离开则不可能回到出发的城市。国王进行如下改革:任命改革前的n位市长中的每一位改革后仍担任市长;任命改革前相邻城市的两位市长改革后仍在某两个相邻城市做市长。
是否存在一个城市改革前后由同一个人任市长,或者存在两个相邻城市改革前后互换市长?
该题为巅峰推理题,您没有浏览该题目权限,只有有效OTF会员才能参加巅峰推理。
有两个国家,一个是正常的国家,另一个是它的镜像国,对于正常国家中的每一个城市,在镜像国中都有一个城市与之对应,反过来也一样。现知,若正常国中两个城市之间有铁路连接,则在镜像国中相应的两城市之间没有铁路连接;反之,对正常国中任意两个无铁路连接的城市,镜像国中相应的城市有铁路连接。设在正常国中,阿雅如果少于两次中转,就不能由A城到大B城。
证明:阿雅在镜像国中,可以由任意一城到达另一个城市,且都不需要超过两次中转。