一道证明题求教

一个 set S = 【1，2，…5】
有一个 bidirectional one to one map function f(x), 正好把 上面 set S 的每个数 map 成为 另外不是自己的另外一个数。
求证明： 这个 map function 由 一个 或多个 closed loop link list 等效描述：
例如 1 to 2, 2 to 3, 3 to 1 加 4 to 5, 5 to 4 … 1 to 3, 3 to 2, 2 to 4, 4 to 5, 5 to 1
试图用反证法来给出严谨描述证明，失败。
求指教！

就不妨设1不在任何闭环里，然后不妨设f(1)=2，那么1不在闭环里，f(2)只能为3，4，5之一。不妨设f2)=3。因为双射和1不在闭环里，f(3)只能4，5之一。不妨设f(3)=4。那么f(4)同理只能为5。f(5)因为双射只能为1（其他值都被选过了），但这形成了带1的闭环，矛盾。
可以吗？

就不妨设1不在任何闭环里，然后不妨设f(1)=2，那么1不在闭环里，f(2)只能为3，4，5之一。不妨设f2)=3。因为双射和1不在闭环里，f(3)只能4，5之一。不妨设f(3)=4。那么f(4)同理只能为5。f(5)因为双射只能为1（其他值都被选过了），但这形成了带1的闭环，矛盾。
可以吗？

heyykitty0 发表于 2024-01-22 03:30

f(3) = 2 也可以的，不一定 从4，5中选的。
one to one mapping，图形上，可以这么理解： 左边一列，右边一列，中间用 crossbar 连起来
如果压缩成一列，（左右相同到数字 overlay 一下），就是一个或多个 闭环 link loop.
可是，如何把这种 illustration 转换成 严谨证明，让我头疼 🤕

对 {1, 2, ..., n} 上的置换都是成立的。

回复 1楼youyouzou的帖子
从任意一个数出发，每一步都必须走到一个新的数，直到回到起点为止。

你这个对任何有限集合都对。
假设 S = {1,2,3,...,N}， f is a bijection from S to S.
首先证明 在 S 中 存在 i 和 一个小于等于 N 的正整数 0<n<N+1, such that f^n(i) = i
然后证明用归纳法假设对 |S| < N 都成立，然后证明 |S| = N 时成立。

对 {1, 2, ..., n} 上的置换都是成立的。
Skipper 发表于 2024-01-22 15:49

是的。这个对于任何集合自我 one to one bijectuon都是这个对的。

你这个对任何有限集合都对。
假设 S = {1,2,3,...,N}， f is a bijection from S to S.
首先证明 在 S 中 存在 i 和 一个小于等于 N 的正整数 0<n<N+1, such that f^n(i) = i
然后证明用归纳法假设对 |S| < N 都成立，然后证明 |S| = N 时成立。
nj_guy 发表于 2024-01-22 15:57

好思路。我去想一想。
你是怎么想到这个切入点的？

好思路。我去想一想。
你是怎么想到这个切入点的？
youyouzou 发表于 2024-01-22 16:00

第一部分：
因为 |S| = N, 而 {1, f(1),...，f^N(1)} 有 N+1 个点，所以必有两个点一样. i.e.: 存在 0<=j<k<=N such that f^j(1) = f^k(1). 这样 i = f^j(1), n = k - j

一个 set S = 【1，2，…5】
有一个 bidirectional one to one map function f(x), 正好把 上面 set S 的每个数 map 成为 另外不是自己的另外一个数。
求证明： 这个 map function 由 一个 或多个 closed loop link list 等效描述：
例如 1 to 2, 2 to 3, 3 to 1 加 4 to 5, 5 to 4 … 1 to 3, 3 to 2, 2 to 4, 4 to 5, 5 to 1
试图用反证法来给出严谨描述证明，失败。
求指教！




youyouzou 发表于 2024-01-22 03:12

怎么严格描述不可能 永远回不到 起点？
新的数，是怎么定义的？ 和上一步不同？还是之前所有步骤不同？

回复 10楼的帖子
你每一步都要走到一个新的数，n-1步之后就输出完了n-1个数，下一步只能回到起点，因为除了起点其他的数都在输出端出现过一次了

第一部分：
因为 |S| = N, 而 {1, f(1),...，f^N(1)} 有 N+1 个点，所以必有两个点一样. i.e.: 存在 0<=j<k<=N such that f^j(1) = f^k(1). 这样 i = f^j(1), n = k - j
nj_guy 发表于 2024-01-22 16:07

谢谢你🙏
你这个回答，把基于我问题之上的最终问题给解决了。

怎么严格描述不可能 永远回不到 起点？
新的数，是怎么定义的？ 和上一步不同？还是之前所有步骤不同？


youyouzou 发表于 2024-01-22 16:09

新的数是和之前所有的都不一样，否则就会转圈循环

怎么严格描述不可能 永远回不到 起点？
新的数，是怎么定义的？ 和上一步不同？还是之前所有步骤不同？


youyouzou 发表于 2024-01-22 16:09

不要试图去证明回到起点，先假设它回到某一点，在某一点形成 loop， 再用归纳法，把形成 loop 的那一部分踢出去，剩下的 element 个数少于 N， 归纳法保证可以是 由几个 loop 组成，再加上上面那个 loop 就证完了。

怎么严格描述不可能 永远回不到 起点？
新的数，是怎么定义的？ 和上一步不同？还是之前所有步骤不同？


youyouzou 发表于 2024-01-22 16:09

1 - 2 - 3 - 1 4 -5 -4 从 1 出发， 三步就回起点1，五步变成3
这个也可以啊。
这个可以是多个 closed loop.
证明描述很困难，对我来说 😂

1 - 2 - 3 - 1 4 -5 -4 从 1 出发， 三步就回起点1，五步变成3
这个也可以啊。
这个可以是多个 closed loop.
证明描述很困难，对我来说 😂
youyouzou 发表于 2024-01-22 16:24

没考虑到可能有多个环。能否说，因为是one to one的函数，所以任何一段链条最后的输出只能回到起点而不能回到链条的中间？

不要试图去证明回到起点，先假设它回到某一点，在某一点形成 loop， 再用归纳法，把形成 loop 的那一部分踢出去，剩下的 element 个数少于 N， 归纳法保证可以是 由几个 loop 组成，再加上上面那个 loop 就证完了。
nj_guy 发表于 2024-01-22 16:22

最后一个点，要回只能回到起点：反证法可以： v1 - v2 …. - vi, 其中 任意 两个数都不一样 如果vi 回到 vj, j/=1, 那么 both vj-1 and vi are mapped to vj, 那么就不是 bijection
在这个 chain 的增长回程中，下一个数只有两种可能： （a) 一个完全新的数，（chain之前从没出现过） （b) V1
（a) 最多长度是 n, 因为只有n个数 可以选择排在 chain上 一旦达到这个界限，必然只能回到 （b)
当然，如果 Vi, i < n, 直接回到 v1 也可以。那么剩下的 vi+1 …. van继续这么故事讲一遍
最多故事讲 n/2 遍。
这个能算证明完毕吗？

f(3) = 2 也可以的，不一定 从4，5中选的。
one to one mapping，图形上，可以这么理解： 左边一列，右边一列，中间用 crossbar 连起来
如果压缩成一列，（左右相同到数字 overlay 一下），就是一个或多个 闭环 link loop.
可是，如何把这种 illustration 转换成 严谨证明，让我头疼 🤕

youyouzou 发表于 2024-01-22 15:38

是1-1bidirectional啊，不能有两个数同时映射到2的。已经假设f(1)=2了。 我觉得你想复杂了。

没考虑到可能有多个环。能否说，因为是one to one的函数，所以任何一段链条最后的输出只能回到起点而不能回到链条的中间？
fogger 发表于 2024-01-22 16:37

是的。最后的输出，不能回到链路中间。
否则：链路中间有两个输入：前面的，最后一个。破坏了one to one mapping

把每个数当作图的节点，每个节点必是一进一出，不成环则必有一个节点有进无出或者有出无进，或者大于一进一出

把每个数当作图的节点，每个节点必是一进一出，不成环则必有一个节点有进无出或者有出无进，或者大于一进一出
家有二猫 发表于 2024-01-22 17:29

👍 简洁的反证法。

最后一个点，要回只能回到起点：反证法可以： v1 - v2 …. - vi, 其中 任意 两个数都不一样 如果vi 回到 vj, j/=1, 那么 both vj-1 and vi are mapped to vj, 那么就不是 bijection
在这个 chain 的增长回程中，下一个数只有两种可能： （a) 一个完全新的数，（chain之前从没出现过） （b) V1
（a) 最多长度是 n, 因为只有n个数 可以选择排在 chain上 一旦达到这个界限，必然只能回到 （b)
当然，如果 Vi, i < n, 直接回到 v1 也可以。那么剩下的 vi+1 …. van继续这么故事讲一遍
最多故事讲 n/2 遍。
这个能算证明完毕吗？
youyouzou 发表于 2024-01-22 16:48

你没必要非去证明回到原点，因为你只需要证明有个loop， 剩下的用归纳法就行了。
如果你非想说明有个从 1 开始的loop, 也很简单：
首先 {1，f(1), f(f(1)),...,f^N(1)} 有 N+1 个点，而且是 {1,...,N} 的子集，所以有 j, k, such that 0<=j<k<=N, with f^j(1) = f^k(1) . 然后 f 是 bijection， 所以有 逆 f^(-1) 而且也是 bijection。 这样：
1 = f^(-j) ( f^j (1)) = f^(-j) (f^k(1)) = f^(k - j)(1)。
这很容易直接证明，但是没必要。

你没必要非去证明回到原点，因为你只需要证明有个loop， 剩下的用归纳法就行了。
如果你非想说明有个从 1 开始的loop, 也很简单：
首先 {1，f(1), f(f(1)),...,f^N(1)} 有 N+1 个点，而且是 {1,...,N} 的子集，所以有 j, k, such that 0<=j<k<=N, with f^j(1) = f^k(1) . 然后 f 是 bijection， 所以有 逆 f^(-1) 而且也是 bijection。 这样：
1 = f^(-j) ( f^j (1)) = f^(-j) (f^k(1)) = f^(k - j)(1)。
这很容易直接证明，但是没必要。
nj_guy 发表于 2024-01-22 20:17

这个就是 我最最终问题需要的答案。👍
你在教aime吗？😂

是1-1bidirectional啊，不能有两个数同时映射到2的。已经假设f(1)=2了。 我觉得你想复杂了。
heyykitty0 发表于 2024-01-22 16:50

我回复写错了。 是 f(3）= 1 也可以。
1- 2 - 3 - 1 4-5-4

这是数学的一个常识。狗：Every permutation is a product of disjoint cycles

这是数学的一个常识。狗：Every permutation is a product of disjoint cycles
AlexW 发表于 2024-01-22 22:57

没学过，不是数学系的。
假如是高一学生，就需要让你证明这个，怎么找突破口，不容易啊。