来自人教群的一道1234567排列被11整除

kuing

爱好者福州小江(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

kuing

用代码打一遍过程：

首先容易证明：能被 $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$。

kuing

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

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. 那个实在太容易，不说了。

第一章

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

kuing

回复 4# 第一章

我也知道不多，你说的这个我就不知道……

nash

回复 4# 第一章


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

第一章

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

琉璃幻

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

hbghlyj

kuing 发表于 2013-8-8 23:06

第一章 发表于 2013-8-8 18:59
上次看了单墫的《解题研究》，里面用了这么个结论：$ 3|m^2+n^2\iff3|m$且$3|n $

我也知道不多，你说的这个我就不知道……

[1,3,4,6,7,9,11,12,14,15,16,19,21,22,23,24,27,28,
 30,31,33,35,36,38,39,42,43,44,46,47,48,49,51,54,
 55,56,57,59,60,62,63,64,66,67,69,70,71,75,76,77,
 78,79,81,83,84,86,87,88,91,92,93,94,95,96,99,102,
 103,105,107,108,110]

A018825 Numbers that are not the sum of 2 nonzero squares.
例如$77|a^2+b^2\iff77|a^2$ 且 $77|b^2$