一道代數題

發表於 | 分類於

題目內容

$a_0=0$，$\forall 1\le k\le n,\ |a_k|=|a_{k-1}+m|\ (m>0)$。求$|\sum\limits_{k=1}^n a_k|$的最小值。

解題思路

很容易發現$(a_1,\cdots,a_k)$的符合條件的組合一共有$2^n$組，顯然逐個遍歷考慮是很不現實的。

然後想到整個題目可以映射到一個深度為$n$的完美二叉圖上，$(a_1,\cdots,a_k)$就對應根節點（$a_0$）到某一個葉節點（$a_n$的某一種可能情況）的路徑。根據二叉樹的性質，這時可以較容易想到對所有可能情況進行二進位制編碼。

例如在下面的解法中，我們將某個代表$a_{k-1}$的可能取值的節點的左子節點考慮為$a_{k-1}+m$，右子節點考慮為$-(a_{k-1}+m)$。當某一路徑經過該節點並前往左子節點時，我們將之編碼為$0$；反之則編碼為$1$。

在這之後，我們可以先試著檢查一些$n$較小的情況。例如$n=5$時，可以發現$32$組$(a_1,\cdots,a_k)$對應的$\sum\limits_{k=1}^n a_k$的可能取值只有$\{-3, -1, 5, 15\}$，一共$4$種。這時就可以順理成章地做出推測：很多不同$(a_1,\cdots,a_k)$組合得到的$\sum\limits_{k=1}^n a_k$都是重複的。

下面的代碼用以列出$n=1\sim20$的時候分別對應的取值集合（為方便，這裡$m=1$）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from math import inf

def f(n):
    return n+1

def decimal_to_binary_list(n, len):
    bin_str = format(n, f'0{len}b')
    bin_list = [int(bit) for bit in bin_str]
    return bin_list

def calculate(len):
    sum_list = []
    for i in range(2 ** len):
        bin_list = decimal_to_binary_list(i, len)
        a_list = []
        for j in range(len):
            if j>0:
                a_list.append((2 * bin_list[j] - 1) * f(a_list[-1]))
            else:
                a_list.append((2 * bin_list[0] - 1) * f(0))
        s = sum(a_list)
        if s not in sum_list:
            sum_list.append(s)
    return sorted(sum_list)

for len in range(1, 21):
    print(len, calculate(len))

運行結果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
1 [-1, 1]
2 [-1, 3]
3 [-2, 0, 6]
4 [-2, 2, 10]
5 [-3, -1, 5, 15]
6 [-3, 1, 9, 21]
7 [-4, -2, 4, 14, 28]
8 [-4, 0, 8, 20, 36]
9 [-5, -3, 3, 13, 27, 45]
10 [-5, -1, 7, 19, 35, 55]
11 [-6, -4, 2, 12, 26, 44, 66]
12 [-6, -2, 6, 18, 34, 54, 78]
13 [-7, -5, 1, 11, 25, 43, 65, 91]
14 [-7, -3, 5, 17, 33, 53, 77, 105]
15 [-8, -6, 0, 10, 24, 42, 64, 90, 120]
16 [-8, -4, 4, 16, 32, 52, 76, 104, 136]
17 [-9, -7, -1, 9, 23, 41, 63, 89, 119, 153]
18 [-9, -5, 3, 15, 31, 51, 75, 103, 135, 171]
19 [-10, -8, -2, 8, 22, 40, 62, 88, 118, 152, 190]
20 [-10, -6, 2, 14, 30, 50, 74, 102, 134, 170, 210]

從這個結果出發，很容易發現規律：只有$\lfloor\frac{n+1}{2}\rfloor$種可能取值，且所有取值排序後為二階等差數列。

這時就應該考慮如何給$\sum\limits_{k=1}^n a_k$相等的不同$(a_1,\cdots,a_k)$組合賦予（或者說尋找）關係，即構造等價關係和等價類。

這裡還是可以回到$n$較小的情況（例如$n=5$）去尋找關係。最後發現要找的關係和異或運算相關，至此本題即迎刃而解。

完整步驟

先考慮引理$\mathrm{I}$：

所有$n$位二進制數$(b_1b_2\cdots b_n)_2\in 2^n$（其中$\forall i\in[n],\ b_i\in\{0,1\}$）均可表示為以下形式：

其中，$\oplus$是異或符號，$m\in\mathbb{N}$且$0\le m\le \lfloor\frac{n+1}{2}\rfloor$，$c_1,c_2,\cdots ,c_m$兩兩不相等且均屬於集合$A_n$（$A_n$的定義見下）。

下面給出證明：

我們定義累異或符號以便表示：

特別地，當$m=0$時，$\mathop\oplus\limits_{i=1}^{0}c_i=(00\cdots 0)_2$。

設$\beta_{j}=(b_1b_2\cdots b_n)_2,1\le j\le n-1,b_j=b_{j+1}=1,\sum\limits_{i=1}^n b_i=2$，

特別地，$\beta_{0}=(100\cdots 0)_2,\ \beta_{n}=(00\cdots 1)_2$。

則$A_n$可表示為$A_n=\{\beta_{0},\beta_{1},\cdots,\beta_{n-1},\beta_{n}\}$。

定義$\gamma_{j,k}=(b_1b_2\cdots b_n)_2,1\le j< k\le n,b_j=b_k=1,\sum_{i=1}^n b_i=2$，容易發現

$\gamma_{j,k}=\mathop\oplus\limits_{i=j}^{k-1}\beta_{i}$，即$\gamma_{j,k}$可以表示為$k-j$個$A_n$元素的異或。

對於任意一個$n$位二進制數$(b_1b_2\cdots b_n)_2\in 2^n$，設$b_1,\cdots,b_n$中有$l$個$1$和$n-l$個$0$，所有滿足$b_i=1$的$b_i$的下標分別為$\sigma(1),\cdots,\sigma(l)$。（$\forall 1\le j\le l,\ \sigma(j)\in[n],\ \sigma(1)<\cdots<\sigma(l)$）

(1). 若$l$為偶數，我們有兩種拼湊異或的方法：

a. 不使用$\beta_{0},\beta_{n}$：

設這種方法一共會使用$S_1$個$A_n$的不同元素，則

b. 同時使用$\beta_{0},\beta_{n}$：

設這種方法一共會使用$S_2$個$A_n$的不同元素，則

$\min\{S_1,S_2\}\le\frac{S_1+S_2}{2}\le\frac{n+1}{2}$，顯然$\min\{S_1,S_2\}\in\mathbb N$，因此$\min\{S_1,S_2\}\le\lfloor\frac{n+1}{2}\rfloor$。

(2). 若$l$為奇數，我們亦有兩種拼湊異或的方法：

a. 使用$\beta_{0}$但不使用$\beta_{n}$：

設這種方法一共會使用$S_3$個$A_n$的不同元素，則

b. 不使用$\beta_{0}$但使用$\beta_{n}$：

設這種方法一共會使用$S_4$個$A_n$的不同元素，則

同理可得$\min\{S_3,S_4\}\le\lfloor\frac{n+1}{2}\rfloor$。

綜上，對於任意的$n$位二進制數$(b_1b_2\cdots b_n)_2$，均能將之表示為不多於$\lfloor\frac{n+1}{2}\rfloor$個$A_n$的不同元素的異或。

引理$\mathrm{I} $得證。

回到題目，易發現$\sum\limits_{k=1}^n a_k\in\{vm|v\in\mathbb{Z}\}$，且 $\max\left\{\sum\limits_{k=1}^n a_k\right\}=\sum\limits_{k=1}^nm=m\cdot\frac{n(n+1)}{2}$。

定義映射$f:2^n\to\{vm|v\in\mathbb{Z}\}^n$，由$n$位二進制數$(b_1b_2\cdots b_n)_2$映射得到的像$(a_1,\cdots,a_n)$滿足

顯然$f$是單射，且$f$的值域是所有滿足條件的$(a_1,\cdots,a_n)$的集合。

另外，為了方便，我們設

考慮引理$\mathrm{II} $：

對於任意的$n$位二進制數$(b_1b_2\cdots b_n)_2$，假設其最少可以表示為$t((b_1b_2\cdots b_n)_2)$個$A_n$的不同元素的異或。

（由引理I可知$0\le t((b_1b_2\cdots b_n)_2)\le \lfloor\frac{n+1}{2}\rfloor$）

若在上述表達式中沒有出現$\beta_{j}$，令

則對於任意滿足條件的$j$，有

下面給出證明：

(1). 當$t((b_1b_2\cdots b_n)_2)=0$時，$(b_1b_2\cdots b_n)_2$僅有一個符合條件的取值$(00\cdots0)_2$，滿足條件；

(2). 假設$t((b_1b_2\cdots b_n)_2)=t_0\ (0\le t_0<\lfloor\frac{n+1}{2}\rfloor)$時結論成立。

當$t((b_1b_2\cdots b_n)_2)=t_0+1$時，假設其異或表達式為$\mathop\oplus\limits_{i=1}^{t_0+1}\beta_{\sigma(i)}$。

考慮$(b_1’b_2’\cdots b_n’)_2=\mathop\oplus\limits_{i=1}^{t_0}\beta_{\sigma(i)}$，顯然有$t((b_1’b_2’\cdots b_n’)_2)=t_0$，

且$(b_1b_2\cdots b_n)_2=(b_1’b_2’\cdots b_n’)_2\oplus\beta_{\sigma(t_0+1)}$。

$\forall j\in\{0,1,\cdots,n\}\backslash\{\sigma(i)|1\le i \le t_0+1\}$：

a. 若$j<\sigma(t_0+1)$，考慮$d_{j+1}’,\cdots,d_{\sigma(t_0+1)}’$中$-1$的個數。

顯然，對於$A_n$中的元素，只有$\beta_{j},\beta_{j+1},\cdots,\beta_{\sigma(t_0+1)-1},\beta_{\sigma(t_0+1)}$能改變這個值。

而我們已知$(b_1’b_2’\cdots b_n’)_2$的異或表達式中不包含$\beta_{j},\beta_{\sigma(t_0+1)}$，因此$d_{j+1}’,\cdots,d_{\sigma(t_0+1)}’$中$-1$的個數隻受$\beta_{j+1},\cdots,\beta_{\sigma(t_0+1)-1}$影響。

這之中的每個$\beta$都可使$d_{j+1}’,\cdots,d_{\sigma(t_0+1)}’$中的兩個數取反（即$0\mapsto1,1\mapsto 0$），其中$-1$的個數的所有變化可能為$+2,-2,0$。

又知初始情況$(00\cdots 0)_2$中，下標在$j+1\sim\sigma(t_0+1)$範圍內的數有$0$個為$1$。

由此可知$d_{j+1}’,\cdots,d_{\sigma(t_0+1)}’$中有偶數個$1$，即有

又因為$(b_1b_2\cdots b_n)_2=(b_1’b_2’\cdots b_n’)_2\oplus\beta_{\sigma(t_0+1)}$，而$\beta_{\sigma(t_0+1)}$只能使$d_{j+1}’,\cdots,d_{\sigma(t_0+1)}’$的其中一個數取反，其中$-1$的個數的所有變化可能為$+1,-1$。

因此$d_{j+1},\cdots,d_{\sigma(t_0+1)}$中有奇數個$-1$，即有

結合$d_i$和$d_i’$的關係

可知

其中左部分：

右部分：

因此有

b. 若$j>\sigma(t_0+1)$，同理可得

綜上，且因為$t=t_0$時結論成立，我們有

這說明$t=t_0+1$時結論亦成立。由數學歸納法，引理$\mathrm{II} $得證。

對於滿足$t((b_1b_2\cdots b_n)_2)\ge1$的$(b_1b_2\cdots b_n)_2$，

假設其異或表達式為$\mathop\oplus\limits_{i=1}^{t((b_1b_2\cdots b_n)_2)}\beta_{\sigma(i)}$，設其中最後一項為$\beta_{j}$。

考慮

顯然有$t((b_1’b_2’\cdots b_n’)_2)=t((b_1b_2\cdots b_n)_2)-1$，且$(b_1b_2\cdots b_n)_2=(b_1’b_2’\cdots b_n’)_2\oplus\beta_{j}$。

由此可知$\forall 1\le k \le j-1,\ b_k=b_k’,\ a_k=a_k’$；$a_j=-a_j’$。

另，$a_j’=d_j’(d_{j-1}’\cdots (d_1’(a_0’+m)\cdots)+m)=m\sum\limits_{i=1}^j\prod\limits_{i’=i}^jd_{i’}’$（觀察$m$的係數易得之）

若$b_{j+1}’=0$，則$b_{j+1}=1$，

若$b_{j+1}’=1$，則$b_{j+1}=0$，

綜上，$a_{j+1}-a_{j+1}’=-2md_{j+1}’$。

$\forall j+2\le k\le n,\ b_k=b_k’$，因此

由此推得

設$\Sigma((b_1b_2\cdots b_n)_2)=\sum\limits_{k=1}^n a_k$，結合引理II可知，

累加可得：

$\begin{align}
&\Sigma((b_1b_2\cdots b_n)_2)\\
=&\Sigma((00\cdots 0)_2)+\sum\limits_{t=1}^{t((b_1b_2\cdots b_n)_2)}(-2m(n+2-2t))\\
=&m\cdot\frac{n(n+1)}{2}+4m\sum\limits_{t=1}^{t((b_1b_2\cdots b_n)_2)}(t-\frac{n}{2}-1)\\
=&m\cdot\frac{n(n+1)}{2}+4m(\frac{t((b_1b_2\cdots b_n)_2)(t((b_1b_2\cdots b_n)_2)+1)}{2}-t((b_1b_2\cdots b_n)_2)(\frac{n}{2}+1))\\
=&m\cdot\frac{n(n+1)}{2}-2mt((b_1b_2\cdots b_n)_2)(n+1-t((b_1b_2\cdots b_n)_2))
\end{align}$

我們知道$0\le t((b_1b_2\cdots b_n)_2)\le \lfloor\frac{n+1}{2}\rfloor$，且下面的構造說明$t((b_1b_2\cdots b_n)_2)$可以取遍$0,1,\cdots,\lfloor\frac{n+1}{2}\rfloor$所有$\lfloor\frac{n+1}{2}\rfloor+1$種可能的值：

顯然$(00\cdots 0)_2$是滿足$t((b_1b_2\cdots b_n)_2)=0$的構造。對於$t((b_1b_2\cdots b_n)_2)>0$的情況，

令$b_i=1(1\le i\le \lfloor\frac{n+1}{2}\rfloor),\ \sum\limits_{j=1}^{n}b_j=1$，可知

$(b_1b_2\cdots b_n)_2=\mathop\oplus\limits_{j=0}^{i-1}\beta_{j}$，是滿足$t((b_1b_2\cdots b_n)_2)=i$的構造。

至此，我們證明了$\Sigma((b_1b_2\cdots b_n)_2)$有且僅有$\lfloor\frac{n+1}{2}\rfloor+1$種可能的取值，

所有可能的取值的集合為

最後，我們將尋找$T_n$中絕對值最小的元素。

設$\Sigma_t=m\cdot\frac{n(n+1)}{2}-2mt(n+1-t)$，固定$m,n$的值。

發現關於$t$的二次函數$2mt(n+1-t)$中線為$t=\frac{n+1}{2}\ge \lfloor\frac{n+1}{2}\rfloor$，

因此數列$\{\Sigma_t\}_{(0\le t\le \lfloor\frac{n+1}{2}\rfloor)}$嚴格遞減，且最大值為

最小值為

當$n$為偶數時，

當$n$為奇數時，

綜上，對於任意的$n$，

由此可知存在$0\le i_0\le \lfloor\frac{n+1}{2}\rfloor-1$，使得$\Sigma_{i_0}\ge 0\ge\Sigma_{i_0+1}$，顯然

因此

具體地，如果希望求得$i_0$的值，考慮關於$t$的二次函數

由$\Delta=4m^2((n+1)^2-n(n+1))=4m^2(n+1)>0$可知，該函數與$y$軸有兩個交點$(x_1,0),(x_2,0)\ (x_1<x_2)$。

由於$t$的範圍限制，我們只需要關注左邊的交點$(x_1,0)$，其中

由$\lfloor\frac{n+1-\sqrt{n+1}}{2}\rfloor\le x_1\le\lfloor\frac{n+1-\sqrt{n+1}}{2}\rfloor+1$可知，

因此$\lfloor\frac{n+1-\sqrt{n+1}}{2}\rfloor$是$i_0$的一個可能值，進而有

絕對值取最小值時的具體構造參見前面的部分。

0%