您当前的位置:首页 > 学习 > 阅览室

趣题:构造1到n-1的排列使得前缀和模n仍为一个排列

时间:12-03来源:作者:点击数:

对于哪些n,存在一个1到n-1的排列S_1, S_2, …, S_n-1,使得T_1, T_2, …, T_n-1也是一个1到n-1的排列,其中,

T_1 = S_1 mod n,

T_2 = (S_1 + S_2) mod n,

T_3 = (S_1 + S_2 + S_3) mod n,

…….

T_n-1 = (S_1 + S_2 + … + S_n-1) mod n.

首先,当n为奇数时,这样的排列永远不可能出现,因为T_n-1 = (1 + 2 + … + (n-1)) mod n = 0,而我们的排列是不包含0的。

当n为偶数时,这样的排列是一定存在的。事实上,当n为偶数时,n-1, 2, n-3, 4, n-5, 6, …, 3, n-2, 1就是一个合法的解。比如说,当n=10时,9, 2, 7, 4, 5, 6, 3, 8, 1就是一个解。

为什么这一定是一个满足题目要求的解呢?因为,它们除以n的余数分别是-1, 2, -3, 4, -5, 6, …,其前缀和恰为-1, +1, -2, +2, -3, +3, …。

题目来源:http://www.brand.site.co.il/riddles/200805q.html

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门