将 3,4,…,1155 排成数列 {ak：k=1,2,…,1153}，使 ak 都是 k 的倍数，有几种排法？

allen125

請問這題

lihp2020

我认为 有点难 晚上 分析分析

lihp2020

但是 我猜测 最后结果不大

uk702

试了一下，将 3,4,5,..., n ，重排成 { \( a_k \) }, 使得 \( k | a_k \) 总是成立，n <=8 时，似乎都是只有一种排法。


n = 9 时，似乎是 4 种：
3,4,9,8,5,6,7
3,8,9,4,5,6,7
3,8,9,4,5,6,7
9,8,3,4,5,6,7


n=10时，假设满足条件的序列为：x,a,b,c,d,6,7,8

由于 5 | d，∴ d=5 或 10，若 d=10的话，5只能填在第一位

情况一：d=10且5填在第一位

5,a,b,c,10,6,7,8，
∵ 4|c，∴ c 只能为 4（8 已经填在最后一位）

5,a,b,4,10,6,7,8
∵ 3|b，∴ b 只能为 3 或 9

若 5,a,3,4,10,6,7,8，则 a=9，不满足 2|a
若 5,a,9,4,10,6,7,8，则 a=3，不满足 2|a

故情况一无解

情况二：d=5
x,a,b,c,5,6,7,8

∵ 4|c，∴ c=4
x,a,b,4,5,6,7,8

∵ 3|b，∴ b=3或9
若 b=3，则 x,a,3,4,5,6,7,8，其中 (x,a)=(9,10)或(10,9)
只有 9,10,3,4,5,6,7,8 满足要求

若 b=9，则 x,a,9,4,5,6,7,8，其中 (x,a)=(3,10)或(10,3)
只有 3,10,9,4,5,6,7,8 满足要求

综合情况一和情况二，
共有两组解 (9,10,3,4,5,6,7,8) 和 （3,10,9,4,5,6,7,8）

王守恩

uk702 发表于 2023-10-16 11:35
试了一下，将 3,4,5,..., n ，重排成 { \( a_k \) }, 使得 \( k | a_k \) 总是成立，n

7,4,3,8,5,6,
7,8,3,4,5,6,
3,4,9,8,5,6,7
3,8,9,4,5,6,7
9,4,3,8,5,6,7
9,8,3,4,5,6,7

uk702

1153,...,577,...,1150,1151

数 575=25*23，所以它理论上可以放在 1，5，25，115，575 这几个位置，但由于 5 只能放在 1 和 5 这两个位置，位置 1 已经被 1153 占了，∴ 5 只能放在 5 这个位置，25 只能放在 25 这个位置

115 可以放在 1,5,23,115这几个位置，但由于 1,5,23 这几个位置都有数了，所以 115 只能放在 115 这个位置, 575 只能放在 575 这个位置

数 574=2*7*41，由于 7 只能放在 7 这个位置，41 只能放在 41 这个位置，82 只能放在 82 这个位置（或者放在位置2），7*41 只能放在 7*41 这个位置，所以  574 也只能放在 574 这个位置（更正：或者位置2；或者位置14，如果位置2放14；或者位置82，如果82放在位置2的话）


问题就变成了，有哪些数可以选择放多个位置？

3 只能放在 3 这个位置，4 只能放在  2 或 4 这个位置，6 只能放在 2 或 6 这个两个位置，

1）若 4 放在 2 这个位置，则 6 只能放在 6 这个位置，由归纳法，其它大概没得选， n 只能放在 n 的位置，只有一组解。

2）若 6 放在 2 这个位置，则 4 只能放在 4 这个位置，由归纳法，其它大概也一样没得选， n 只能放在 n 的位置，只有一组解。



猜测只有
第一个：1153,1152，3，4，5，...(直到) 1151
第二个：1153,576，3，4，5，...(直到) 1151 ，但位置 576 填 1152
第三个：1153,288，3，4，5，...(直到) 1151 ，但位置 288填576，位置576 填 1152
第四个：1153,288，3，4，5，...(直到) 1151 ，但位置 288填1152，（位置576 还是填 576）
第五个：1153,144，3，4，5，...(直到) 1151 ，但位置 144填288，位置288填576，位置576 填 1152
第六个：1153,144，3，4，5，...(直到) 1151 ，但位置 144填576，（位置288还是288），位置576 填 1152
...

lihp2020

1 简单分析 基本很多元素 都满足 an =n
2 唯一的变数 就是在 最后两个数
1154 和1155
分解因式
1155=3 * 5 * 7 * 11
因数        1, 3, 5, 7, 11, 15, 21, 33, 35, 55, 77, 105, 165, 231, 385, 1155

1154=2 * 577
因数        1, 2, 577, 1154
先分析 1154  是偶数
在偶数位 a2 a4...a1152   除了 a2  都确定好了  也只剩下 1154 了 也就是1154 必须填 1154

还剩下 1155
几乎不确定的位置
就  1, 3, 5, 7, 11, 15, 21, 33, 35, 55, 77, 105, 165, 231, 385 位置
填 1155, 3, 5, 7, 11, 15, 21, 33, 35, 55, 77, 105, 165, 231, 385

现在 有点杂乱  我们进行分类讨论
其中 a1 =任意数都可以
an!=n (n>1)的个数K 分类
K=0  有一种
K=1 有 14种 (a1=3 a3=1155)
k=2 (a1=3 a3=105 a105=1155)
        C(4,1)*C(3,1)+ C(4,1)*C(3,2)+C(4,2)*C(2,1) = 36
k=3 （a1=3 a3=3*5=15 a15=15*7=105 a105=105*11）
C(4,1)*C(3,1)*c(2,1)=24
一共 1+14+36+24 =75？

uk702

lihp2020 发表于 2023-10-17 06:15
1 简单分析 基本很多元素 都满足 an =n
2 唯一的变数 就是在 最后两个数
1154 和1155

1154 有两个因子，2 和 577，理论上可以填第1位，2位或第577位，
若 1154 放在第 577 位，则由于 577 是素数，只能放在第 1 位，
第2位放的数未知（但显然必须是偶数，不能是1155），设为 x，列作下面的 ② 。

①：1155，1154，3,4,...（直至）1153

第一种情况：

1155=3*5*7*11，共有 16 个因子，和这些因子对应的每个位置，都可以与基本形中排在第一的 1155 交换，
比如
③: 3,1154,1155,4,...（直至）1153
④: 5,1154,3,4,1155,6,...（直至）1153
⑤：15,1154,3,4,5,6,7,8,9,10,11,12,13,14,1155,16,...（直至）1153
...
易验证这些都是有效的排列。

① 的这种变化有 16 组解。

第二种情况：
3 要么放在第1位，要么放在第 3 位，对于 3 放在第 1 位，有下面 9 种变化解：
第17组：3，1154，15，4，5，...（直至）1153 ，但位置 15 放 105，位置 105 放 1155
第18组：3，1154，15，4，5，...（直至）1153 ，但位置 15 放 1155
第19组：3，1154，21，4，5，...（直至）1153 ，但位置 21 放 105，位置 105 放 1155
第20组：3，1154，21，4，5，...（直至）1153 ，但位置 21 放 1155
第21组：3，1154，33，4，5，...（直至）1153 ，但位置 33 放 165，位置 165 放 1155
第22组：3，1154，33，4，5，...（直至）1153 ，但位置 33 放 1155
第23组：3，1154，105，4，5，...（直至）1153 ，但位置 105 放 1155
第24组：3，1154，165，4，5，...（直至）1153 ，但位置 165 放 1155
第25组：3，1154，231，4，5，...（直至）1153 ，但位置 231 放 1155

同理，5 放在第1位，7 放在第1位，11放在第1位，各有 9 种变化解。
∴① 的这种形式的变化解共计 4*9=36 种

第三种情况：
15 要么放在第1位，要么放在第 3 位，要么放在第 5 位，要么放在第 15 位，后三种情况前面已经讨论。
若 15 放在第1位，这时 3 只能放在第 3 位，5 只能放在第 5 位，
15，1154，3，4，5，...（直至）1153 ，但位置 15 放 105，位置 105 放 1155
15，1154，3，4，5，...（直至）1153 ，但位置 15 放 165，位置 165 放 1155
15，1154，3，4，5，...（直至）1153 ，但位置 15 放 1155（去掉，和第一种情况重合）
计2种变化。

同理，首位为 3*7,3*11,5*7,5*11,7*11 各有 2 种变化，故情况三有 6*2=18 种变化。

第四种情况：
3*5*7=105 放在第1位，这时第 3*5*7=105 位必须填 1195，和第一种情况重合。

统合上述情况，共计 16+36+12=64 组解。


下面证明 ② 无解，


②：577,x,3,4,...（直至）1153，除了位置577填1154，
现在，由于 x 已经填在第 2 位，所以，第 x 位不能填 x，要填一个 x 的倍数，比如说 x1，
同理，第 x1 位不能填 x1，要填一个 x1 的倍数，比如说 x2，
...
直至第 k 步，且 xk > 578， 由于 2*xk > 1155，所以 xk 位将没法填


同样可证明无其它解：

比如第1位填 x，并且 x 不是 1154 和 1155 的因子，则第 x 位需要填一个 x 的倍数、但比 x 大的值，假设为 a1，
同样，第 a1 位需要填填一个 a1 的倍数、但比 a1 大的值，假设为 a2，
...
最后，到了第 k 步，且 ak > 578，位置 ak 需要填一个 ak 的倍数、但比 ak 大的值，而且不能是 1154 或 1155，
而现在 2*ak > 1155，所以没法填。

lihp2020

1154必须填1154是啥意思   这个打字错误
认真理解上下文 可以知道

在偶数位 a2 a4...a1152   除了 a2  都确定好了  也只剩下 a2 了 也就是a2 必须填 1154

时空伴随者

无论如何都是奇数排奇数位，偶数排偶数位。总排法=奇数排法×偶数排法
1154=2×577只能排在第二位，偶数排法是唯一的，只需考虑奇数排法。
1155=3×5×7×11，可排的位置有第1, 3, 5, 7, 11, 15, 21, 33, 35, 55, 77, 105, 165, 231, 385 位；
385=5×7×11，当本位被1155占据时，可排的位置有第1, 5, 7, 11, 35, 55, 77位；（105，165，231同理）
77=7×11，当本位被占时，77可排在，1，7，11（15，21，33，35，55同理）
3，5，7，11位被占时，只能排在第1位。


通过以上分析，可得出最后的结果。
偶数1154→2，其余各就各位；
奇数，除1155外，先各就各位，只有第1位虚位以待。
1155→385、231、165、105（三素数乘积），共4×13种；
1155→77、55、35、33、21、15（两素数乘积），共6×3种；
1155→11、7、5、3、1，共5种。
总共75种，不可能再多了。