免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

[数论] 来自人教群的一道1234567排列被11整除

爱好者福州小江(4226*****)  21:12:53
1,2,3,4,5,6,7,组成七位数,使得是11的倍数,求能排出的个数
鱼子老师,这题有见过吗?竞赛题!!

学生--zhcosin(5323*****)  21:13:49
这题就别纠结了,连是否允许重复都没说,你还饶有兴趣

群管-kuing  21:16:52
不允许重复的话应该是 576

爱好者福州小江(4226*****)  21:18:23
KK你的思路是什么?参考答案没看懂

群管-kuing  21:20:17
想好想,说起来不好说,我先吃个西瓜

爱好者福州小江(4226*****)  21:21:04
吃个西瓜还是块

群管-kuing  21:21:41
别期望,我写的可能比你看的答案更简略

群管-kuing  21:31:23
首先容易证明:能被11整除等价于奇数位数字之和与偶数位数字之和的差能被11整除。
故 11|abcdefg \iff 11|(a+c+e+g-b-d-f)。
将 {1,2,3,4,5,6,7} 分割成一个四元子集 {a,c,e,g} 及另一个三元子集 {b,d,f},容易证明 a+c+e+g-b-d-f 一定是偶数。
但是 |a+c+e+g-b-d-f| 最大为 4+5+6+7-1-2-3=16,故要 11|(a+c+e+g-b-d-f) 只能 a+c+e+g=b+d+f,亦即 a+c+e+g=b+d+f=14。
于是容易列举出只有以下四种情况满足:
{2,3,4,5}, {1,6,7};
{1,2,4,7}, {3,5,6};
{1,2,5,6}, {3,4,7};
{1,3,4,6}, {2,5,7}.
每种情况对应 4!*3! 个数,所以最终结果为
4!*3!*4=576
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
$\href{https://kuingggg.github.io/}{\text{About Me}}$

用代码打一遍过程:

首先容易证明:能被 $11$ 整除等价于奇数位数字之和与偶数位数字之和的差能被 $11$ 整除。


\[11\mid\overline{abcdefg} \iff 11\mid(a+c+e+g-b-d-f).\]

现将 $\{1,2,3,4,5,6,7\}$ 分割成一个四元子集 $\{a,c,e,g\}$ 及另一个三元子集 $\{b,d,f\}$,容易证明 $a+c+e+g-b-d-f$ 一定是偶数。

但是 $\abs{a+c+e+g-b-d-f}$ 最大为 $4+5+6+7-1-2-3=16$,故要 $11\mid(a+c+e+g-b-d-f)$ 只能 $a+c+e+g=b+d+f$,亦即 $a+c+e+g=b+d+f=14$。

于是容易列举出只有以下四种情况满足:
\begin{gather*}
\{2,3,4,5\}, \{1,6,7\};\\
\{1,2,4,7\}, \{3,5,6\};\\
\{1,2,5,6\}, \{3,4,7\};\\
\{1,3,4,6\}, \{2,5,7\},\\
\end{gather*}
每种情况对应 $4!\times3!$ 个数,所以最终结果为 $4!\times3!\times4=576$。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

顺便说一下上面那三个“容易”为什么容易:

1. 因为 $10^k=(11-1)^k\equiv (-1)^k\pmod{11}$,故
\begin{align*}
\overline{a_na_{n-1}\cdots a_1a_0}&=a_n\cdot10^n+a_{n-1}\cdot10^{n-1}+\cdots+a_1\cdot10+a_0\\
&\equiv a_n\cdot(-1)^n+a_{n-1}\cdot(-1)^{n-1}+\cdots+a_1\cdot(-1)+a_0\pmod{11}.
\end{align*}

2. 交换 $\{a,c,e,g\}$ 与 $\{b,d,f\}$ 的任意元素,比如说交换 $a$ 和 $b$,交换前后那个差值相差 $2\abs{a-b}$,即奇偶性不变。

3. 那个实在太容易,不说了。
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

二项式定理用得妙!我还想着如何充分必要的证呢……
话说,数论没怎么做题,掌握的结论也少,更别说记住了。
上次看了单墫的《解题研究》,里面用了这么个结论:$ 3|m^2+n^2\iff3|m$且$3|n $
我还老老实实的推导了一遍。

TOP

回复 4# 第一章

我也知道不多,你说的这个我就不知道……
$\href{https://kuingggg.github.io/}{\text{About Me}}$

TOP

回复 4# 第一章


    是那本《我如何解题》?那啥最贵的出版社出版的那本?
老贵了,今天看了半天,48人民币……
没买

TOP

不知道。我看的都是电子书。
没钱买……

TOP

此题甚易,打个酱油。。。。。

TOP

返回列表 回复 发帖