北大相关选拔数学真题汇总

发表于 更新于 分类于 Waline：

2024寒假学堂(部分)

Problem4

设$G ( x ) = ( x^2 + x - 1 )^{ 100 } = \sum_{ k = 0 }^{ 200 } a_k x^k$,求$2 a_0 - a_1 - a_2 + 2 a_3 - a_4 - a_5 + \cdots + 2 a_{ 198 } - a_{ 199 } - a_{ 200 }$.

Solution4

考虑求出$\sum_{ 0 \leq k \leq 66 }{ a_{ 3 k } }$.直接取三次单位根$\omega_3 = - \frac{ 1 }{ 2 } + \frac{ \sqrt{ 3 } }{ 2 } i$,自然有$1 + \omega_3 + \omega_3^2 = 0$,所以$G ( 1 ) + G ( \omega_3 ) + G ( \omega_3^2 ) = 3 \sum_{ 0 \leq k \leq 66 }{ a_{ 3 k } }$.

所以答案显然是$G ( \omega_3 ) + G ( \omega_3^2 ) = ( - 2 )^{ 100 } + ( - 2 )^{ 100 } = 2^{ 101 }$.

Problem10

等差数列中,$a_1 > 0$,公差$d < 0 , \frac{ a_{ 31 } }{ a_{ 30 } } < - 1$,求最大的正整数$n$,使得$S_n > 0$.

Solution10

显然$S_{ 60 } = 30 ( a_{ 30 } + a_{ 31 } ) < 0 , S_{ 59 } = 59 a_{ 30 } > 0$.

Problem11

全为整数的等差数列,$d = 4$,求所有满足$S_n = 2024$的$n$的和.

Solution11

则$n ( 2 n - 2 + a_1 ) = 2024 = 2^3 \times 11 \times 23$.显然只要$n | 2024$即可.

所有$n$的和自然是$( 1 + 2 + 4 + 8 ) ( 1 + 11 ) ( 1 + 23 ) = 15 \times 12 \times 24 = 4320$.

Problem14

整数数列$U_n$满足$U_0 = 1$,且当$n \geq 1$的时候$U_{ n + 1 } U_{ n - 1 } = kU_n$,其中$k$是一个正整数.问能让$U_{ N } = N$的$k$的个数有多少个,其中$N = 2024$.

Solution14

则$U_{ n + 1 } = \frac{ kU_n }{ U_{ n - 1 } } , \frac{ U_{ n + 1 } }{ U_n } = k \frac{ U_n }{ U_{ n - 1 } } \frac{ 1 }{ U_n }$.

观察上面的式子,不难想到换元后求前缀积,但其实注意到我们可以直接求前缀积,设$T_n = \prod_{ k = 1 }^n U_k , W_n = U_n \prod_{ k = 1 }^{ n - 2 } U_k$.

注意到$W_n = kW_{ n - 1 } , W_1 = U_1 , W_n = k^{ n - 1 } U_1$.又注意到$T_n = kU_{ n - 1 } W_{ n - 1 } = kW_{ n - 1 } \frac{ T_{ n - 1 } }{ T_{ n - 2 } } = k^{ n - 1 } U_1 \frac{ T_{ n - 1 } }{ T_{ n - 2 } } = ( k^{ n - 1 } U_1 ) ( k^{ n - 2 } U_1 ) \frac{ 1 }{ T_{ n - 3 } }$,$T_{ n - 3 } = ( k^{ n - 4 } U_1 ) ( k^{ n - 5 } U_1 ) \frac{ 1 }{ T_{ n - 6 } }$.所以$T_{ n } = k^6 T_{ n - 6 }$,所以$U$存在长度为$6$的循环节.所以$U_{ N } = \frac{ T_N }{ T_{ N - 1 } } = \frac{ T_2 }{ T_1 } = U_2 = kU_1$.(其实直接暴力找循环节也是可以的)

所以$k$需要是$N$的因子.

哦,还不如直接找循环节,还要判断这是个整数序列.

设$w = U_1$,则$U$的前六项是:$1 , w , kw , k^2 , \frac{ k^2 }{ w } , \frac{ k }{ w }$.要求$kw = N , w | k$,所以$( 11 \times 23 ) | k$,$k \equiv 0 \pmod{ 4 }$.所以$k = 4 \times 11 \times 23$或$k = 8 \times 11 \times 23$.

Problem15

求使方程$\lfloor \frac{ 10^n }{ x } \rfloor = N = 2024$恰有两个整数解的正整数$n$的个数.

Solution15

我们有:

显然$\lfloor \frac{ 10^n }{ N ( N + 1 ) } \rfloor = 1 , 2 , 3$.而$N ( N + 1 ) = 4098600$,所以只有$n = 7$可能满足条件,带入检验可行.

Problem18

用六种颜色给正方形六个面染色,旋转平移后相同算一种方案,要求每个面颜色都不同,求方案数.

Solution18

钦定一个面,然后枚举对面,中间四个是一个环,方案数是$5 \times 3 ! = 30$.

Problem19

$f ( x ) = \lfloor 2 x \rfloor + \lfloor 4 x \rfloor + \lfloor 6 x \rfloor + \lfloor 8 x \rfloor , x \in \mathbb{ R }$,求其不超过$n = 2024$的正整数取值有多少种.

Solution19

显然$f ( x + 1 ) = f ( x ) + 20$,因此我们先考虑$x \in [ 0 , 1 )$的情况.

手动枚举一下知道此时$f ( x )$有$12$种不同的取值,前六种是$\{ 0 , 1 , 2 , 4 , 5 , 6 \}$,后六种对应了前六种$+ 10$.而$2024 = 101 \times 20 + 4$,所以共有$101 \times 12 - 1 + 4 = 1215$种取值.

Problem20

从$[ 1 , n ] , n = 2024$中分别独立随机两个正整数(可以相同)$a , b$,则求$3^a + 7^b \equiv 8 \pmod{ 10 }$的概率.

Solution20

考虑$\varphi ( 10 ) = 4$,所以原题答案等价于$n = 4$的时候的答案.在这$16$中可能性中满足条件的只有三种,概率为$\frac{ 3 }{ 16 }$.

2023强基(部分)

Problem3

已知$a_1 = \frac{ 5 }{ 2 } , a_{ n + 1 } = a_n^2 - 2$,求$\lfloor a_n \rfloor \bmod 7 , n = 2023$.

Solution3

这个一看就不是好解的,想都别想直接数学归纳,注意到$a_n = \frac{ 4^{ 2^{ n - 1 } } + 1 }{ 2^{ 2^{ n - 1 } } }$,那么$\lfloor a_n \rfloor = 2^{ 2^{ n - 1 } }$.

而$\varphi ( 7 ) = 6 , \varphi ( 6 ) = 2$.由扩展欧拉定理,立刻有:$2^{ 2^{ 2022 } } \equiv 2^{ 2^{ 2022 } \bmod 6 } \equiv 2^{ 2^{ 6 } } \equiv 16 \equiv 2 \pmod{ 7 }$.

Problem4

$50$个队伍两两打比赛,胜一场积分$+ 1$,负一场积分不变,无平局.

且任取$27$支队伍,其中一定有一支队伍负于其它的$26$支,也一定有一支队伍胜于其它的$26$支.

问$50$支队伍最少有多少种不同的积分.

Solution4

答案是$50$.

因为是竞赛图,缩点之后是一条链.

如果所有强连通分量的大小都$\leq 27$的话,显然我们全选一个强连通分量就完蛋了.因此所有的强连通分量的大小都$> 27$,唯一的可能是所有点在一个强连通分量中,我们在其中取出一个长度为$k$的简单环,由鸽笼原理,剩下的$n - k$个点中至少有$\frac{ n - k }{ 2 }$个点对着$k$个点只输或者只赢(如果有输有赢就无所谓了),这样的话只需要$k + \frac{ n - k }{ 2 } \geq 27$即可,此时$k \geq 4$即可.由于这是竞赛图,显然存在长度为$4$的简单环.

还有一种更简单的做法,考虑取一个积分最多的点,假设为$u$.我们任意取一个击败过它的点(如果有的话),假设为$v$,再取$25$个被$u$击败的点(显然这些点存在),设这些点集为$S$.则$u , v , S$组成的集合中,有一个点可以击败其它所有点,根据假设,只能是$v$.由此,可以知道,只要是$u$能击败的点,$v$一定能击败,而且$v$能击败$u$,因此$\deg_v > \deg_u$,与假设不符.因此一定不存在一个$v$可以击败$u$.删掉$u$后做数学归纳,可知原图一定是拓扑图.

Problem8

一只蚂蚁第一天在$( 0 , 0 )$,第$k + 1$天向上下左右随机一个方向移动$\frac{ 1 }{ 4^k }$单位,求第$n$天的可能位置数量,$n = 2023$.

Solution8

不妨设第$n$天不同位置数量为$S_n$,显然只要前面岔开了,后面永远无法走到一个点.所以$S_1 = 1 , S_{ n + 1 } = 4 S_n , S_{ 2023 } = 4^{ 2022 }$.

Problem10

集合$U = \{ 1 , 2 , \cdots , n \} , n = 10$,求$U$中的满足元素两两互素的三元子集个数.

Solution10

集合是无序的,这个很难搞,我们先从$U$中把$1$去掉最后再加上.

先考虑可以重复放$1$的情况:

这个推下去感觉就头大了,退一步考虑暴力算吧.

先考虑全是奇数的情况,只能从$1 , 3 , 5 , 7 , 9$中选,答案应该是$1 + 2 \binom{ 3 }{ 2 } = 7$.

接下来考虑选一个偶数,如果选$2 , 4 , 8$是等价的,答案此时是$3 ( \binom{ 5 }{ 2 } - 1 ) = 27$.如果选$6$的话答案是$\binom{ 3 }{ 2 } = 3$.如果选$10$的话方案数是$\binom{ 4 }{ 2 } - 1 = 5$,加起来方案数是$42$.

Problem11

集合$U = \{ 1 , 2 , \cdots , n \} , n = 366$,则$U$的互不相交且各元素之和为$17$的倍数的二元子集最多有多少个?

Solution11

考虑$\lfloor \frac{ 366 }{ 17 } \rfloor = 21 , 366 \equiv 9 \pmod{ 17 }$.答案显然是$21 \times 8 + 10 + 1 = 179$个.

Problem12

三个互不相同的数的$\gcd = 20 , \text{ lcm } = 20000$,求选取这三个数的方案数(顺序不同算不同的方案).

Solution12

显然等价于$\gcd = 1 , \text{ lcm } = 1000 = 2^3 \times 5^3$.先只分析其中一个质因子,方案应该是$( 0 , 0 , 3 ) , ( 0 , 1 , 3 ) , ( 0 , 2 , 3 ) , ( 0 , 3 , 3 )$,打乱一下顺序的话就共有$3 + 6 + 6 + 3 = 18$种方案.如果可以重复,平方一下得到$324$.

接下来去掉重复的情况,只有可能两个质因子都相同才会重复,拿上面的三元组算一下,此时方案数共有$2 \times 2 \times 3 = 12$种,于是答案为$312$.

Problem14

求$\lfloor \frac{ k^2 }{ n } \rfloor , k \in [ 1 , n ] , n = 2023$种有多少个不同的元素.

Solution14

由于两个完全平方数的差是逐渐增大的,应该存在一个$k_0$,$\leq k_0$的$k$会扎堆,但是这些$d$全都能取到,$> k_0$的则不会有两个$k$得到相同的元素.所以前者统计不同的$d$,后者统计不同的$k$考虑$( k + 1 )^2 - k^2 = 2 k + 1$.分界线应该是$k_0 = 1011$.

所以答案应该是$n - k_0 + \lfloor \frac{ k_0^2 }{ 2 k_0 + 1 } \rfloor + 1 = 1012 + 506 = 1518$.

Problem15

对四元组$( a , b , c , d )$计数,满足$101 | ( a + b + c + d )$且$0 < a < b < c < d \leq 101$.

Solution15

这题真的厉害啊.

不妨设$S_k$为满足$( a + b + c + d ) \equiv k \pmod{ 101 }$的满足$0 < a < b < c < d \leq 101$的四元组数量.不难发现$\sum S_k = \binom{ 101 }{ 4 }$.

注意到$( a , b , c , d ) \mapsto ( a + 1 , b + 1 , c + 1 , d + 1 )$,注意这里是$\pmod{ 101 }$意义下的加法,这是一个双射,所以$S_{ k } = S_{ k + 4 }$,下标同样也是$\pmod{ 101 }$意义下进行的.又因为$\gcd ( 101 , 4 ) = 1$,所以所有的$S_k$均相等.$S_0 = \frac{ \binom{ 101 }{ 4 } }{ 101 } = 40425$.

Problem16

问方程$x \lfloor x \rfloor = 6$的解的个数.

Solution16

$6 = x \lfloor x \rfloor \geq \lfloor x \rfloor^2$,所以$\lfloor x \rfloor = \pm 1 , \pm 2$.显然都不可以.所以个数为$0$.

Problem17

设$R ( n ) = \sum_{ k = 2 }^{ 10 } ( n \bmod k )$,求满足$R ( n ) = R ( n + 1 )$的十进制下的两位数$n$的个数.

Solution17

从$R ( n )$到$R ( n + 1 )$,应该是加了若干个$1$,然后又丢了几个$k - 1$这样的.那就一定需要丢掉的数字之和为$9$.枚举一下,丢了的只有可能是以下情况:$( 9 ) , ( 7 + 2 ) , ( 6 + 3 ) , ( 5 + 4 ) , ( 4 + 3 + 2 )$,分别对应了$n + 1$应该是分别以下数的倍数$( 9 ) , ( 14 ) , ( 6 ) , ( 20 ) , ( 12 )$,并且和分别要求不是另一些数的倍数,这就去掉了其中的若干个,最后剩下的是:$( 7 + 2 )$,并且分别不能是以下数字的倍数$( 3 , 4 , 5 )$.

取一下的话$n + 1$可以是:$14 , 98$,$n = 13 , 97$,验证一下均合法,所以答案为$2$.

Problem18

已知$a < b < c < d$,而$x , y , z , w$是$a , b , c , d$的一个排列,求$( x - y )^2 + ( y - z )^2 + ( z - w )^2 + ( w - x )^2$得到的不同数个数.

Solution18

圆排列个数是$3 ! = 6$个,只需要判掉相同的圆排列即可.

显然翻转后是相同的,所以最多有三个不同数,排列分别是$( x , y , z , w ) , ( x , z , w , y ) , ( x , w , y , z )$.

考虑:

显然只要$xy + yz + zw + wx$不同,那么两个数就不同.不难判断上面三个数互不相同.

Problem19

已知$0 < x_1 < x_2 < \cdots < x_9$且$\sum_{ k = 1 }^9 x_k = 220$,在$\sum_{ k = 1 }^5 x_k$最大的前提下,最小化$x_9 - x_1$.

Solution19

不妨枚举一下$x_5$选啥,设$f ( S , m , k )$表示选出$k$个互不相同的数,使得它们$\leq m$且总和为$S$,是否可行.不难发现$f ( S , m , k ) = [ \frac{ k ( k + 1 ) }{ 2 } \leq S \leq \frac{ k ( 2 m - k + 1 ) }{ 2 } ]$.

那我们要求的就是:

立刻得到$x_5 = 24 , 25 , S = 110$,那么后面的选法就一定了,后面四个数一定是$26 , 27 , 28 , 29$,只需要让$x_1$最大即可

$x_5 = 24$时,此时最优显然是$20 , 21 , 22 , 23 , 24 , 26 , 27 , 28 , 29$,$x_9 - x_1 = 9$.

Problem20

有一个$n$边形,其中有$\binom{ n }{ 2 }$条对角线,不存在三线交于一点的情况,问这些对角线将该$n$边形分成了多少个部分.$n = 10$.

Solution20

平面图同样符合欧拉定理.

考虑内部一定多出来了$\binom{ n }{ 4 }$个点(任意四个点有且只有一种交法),每交一个点就会多出$2$条边,所以多出来了$2 \binom{ n }{ 4 } + \frac{ n ( n - 3 ) }{ 2 }$条边.

考虑内部的若干个部分一定是$a_3$个三角形,$a_4$个四边形,…,$a_k$个$k$边形,总之我们发现:

两式得到:$\sum_{ j = 3 }^k a_j = \frac{ ( n - 1 ) ( n - 2 ) }{ 2 } + \binom{ n }{ 4 }$.

$n = 10$的时候,答案为$246$.

2024强基(部分)

Problem1

求$\sum_{ i = 1 }^n \lfloor \frac{ 19^i }{ 20 } \rfloor \bmod 7 , n = 2024$.

Solution1

带入$n = 2024$并$\bmod 7$,原式为:

注意到$2024 \bmod 6 = 2$,原式$\equiv - 4 - 9 \equiv 1$.

Problem3

求长度为$n$的排列个数,使得排列中$\nexists i \in [ 1 , n - 1 ] , a_i = a_{ i + 1 } - 1$.$n = 8$.

Solution3

一眼容斥,也就是每个长度为$k$的连续段的容斥系数应该是$( - 1 )^{ k - 1 }$.那么设分成了$w$个段,总的容斥系数应该是$( - 1 )^{ n - w }$,答案就是$f_{ n ‘ } = \sum_{ w = 1 }^n ( - 1 )^{ n - w } w ! \binom{ n - 1 }{ w - 1 } = \sum_{ w = 0 }^{ n ‘ } ( - 1 )^{ n ‘ - w } \binom{ n ‘ }{ w } ( w + 1 ) ! = n ‘ ! \sum_{ w = 0 }^{ n ‘ } \frac{ ( - 1 )^w }{ w ! } ( n ‘ - w + 1 )$,此时已经能算出答案是$16687$.

注意到这个形式和错排非常像,类似错排去凑递推公式.设$g_n$为错排数量,显然有$f_{ n } = nf_{ n - 1 } + g_{ n }$,立刻算出答案是$16687$.

Problem4

已知数列$1 , 2 , 2 , 3 , 3 , 3 , 4 , 4 , 4 , 4 , \cdots$,求其第$n$项$\bmod 5$的值,$n = 2024$.

Solution4

考虑第一个值为$k$的地方应该在哪里.显然$a_{ \frac{ k ( k - 1 ) }{ 2 } + 1 } = k$.注意到$a_{ 2081 } = 65$,所以$a_n = 64$,其$\bmod 5 = 4$.

Problem5

求四元组$( a_1 , a_2 , a_3 , a_4 )$的个数,满足$a_1 , a_2 , a_3 , a_4 \in \{ 1 , 2 , 3 \}$,且$10 < a_1 a_2 a_3 a_4 < 20$.

Solution5

排个序按照字典序开搜,只有三种可能:$\{ 3 , 3 , 2 , 1 \} , \{ 3 , 2 , 2 , 1 \} , \{ 2 , 2 , 2 , 2 \}$,打乱顺序的话就有$25$种可能.

Problem8

求$\mathbb{ R }$上方程$x^2 - 13 \lfloor x \rfloor + 11 = 0$的解的个数.

Solution8

首先注意到$\lfloor x \rfloor = \frac{ x^2 + 11 }{ 13 }$,那么自然有方程组:

只需要解这个方程组即可.但是这个方程组很难搞.

先考虑$x^2 \equiv 2 \pmod{ 13 }$这个性质,由勒让德判别符号,算出该方程在整数范围内无解.

没办法,只能设$x = \sqrt{ 2 + 13 k }$的形式,带入有不等式:

冷静一下!注意到$0 \leq k \leq 13$,又根据第一个不等式得知大部分$k$应该会很大,开始暴力枚举一下,合法的情况有:$k = 0 , 9 , 10 , 11$,共有四个解.

Problem9

在一个体积为$1$的正方体内部找一个点,过这个点作平行于正方体的面的三个平面,这样整个正方体会被分为八个长方体,最小化这八个部分中,体积$\leq \frac{ 1 }{ 8 }$的长方体的个数.

Solution9

原本想考虑先横着切一刀,分为一个大部分一个小部分,大部分均分即可,小部分选一个很大的部分,剩下三个部分体积$\leq \frac{ 1 }{ 8 }$.考虑设这个点是$( x , x , h )$,那么必然有$\begin{cases}( 1 - h ) x^2 > \frac{ 1 }{ 8 } \ h ( 1 - x )^2 > \frac{ 1 }{ 8 }\end{cases}$,化简,只要$8 > \frac{ 1 }{ x^2 } + \frac{ 1 }{ ( 1 - x )^2 }$即可,这个根据基本不等式不可能满足,寄了.

但是四个肯定是好构造的,我们直接取$( 0 . 5 , 0 . 5 , 0 . 1 )$即可.那么是不是可以证明答案一定$> 3$呢?

考虑一个面上的四个长方体,其中较小的两个一定是相邻的.因此,最终体积$\leq \frac{ 1 }{ 8 }$的长方体肯定也是相连的.接下来证明三个的不行,只需要设这个点为$( x , y , h ) , x , y , h \leq \frac{ 1 }{ 2 }$,然后证明$8 > \frac{ 1 }{ xy } + \frac{ 1 }{ ( 1 - x ) ( 1 - y ) } , x , y \leq \frac{ 1 }{ 2 }$这个不等式无解即可.

由基本不等式,$\frac{ 1 }{ xy } + \frac{ 1 }{ ( 1 - x ) ( 1 - y ) } \geq 2 \sqrt{ \frac{ 1 }{ x ( 1 - x ) y ( 1 - y ) } } \geq 2 \sqrt{ 4 \times 4 } = 8$,不符题意.

这样就是最少是四个.

Problem11

设$S ( n )$表示正整数$n$的十进制数码和,求满足$S ( n ) \equiv S ( n + 1 ) \equiv 0 \pmod{ 5 }$的最小的$n$.

Solution11

显然必须发生进位,不妨设$n = 10^k a + 10^k - 1$,$a \ne 9 \pmod{ 10 }$,$S ( n ) = S ( a ) + 9 k , S ( n + 1 ) = S ( a ) + 1$,

此时显然有$9 k - 1 \equiv 0 \pmod{ 5 }$,$k \equiv 4 \pmod{ 5 }$.$n_{ \min } = 49999$.

Problem12

求满足以下条件的最大的正整数$n$:十进制下每一位数字互不相同,且$\forall m , 10^m \leq n , \lfloor \frac{ n }{ 10^m } \rfloor | n$.

Solution12

显然不可能是五位数及以上,而且如果是四位数的话最后一位必然是$0$.

不妨设其为$\overline{ ab }$,其中$b = 10 c$,$a$是$b$的因子,不妨枚举一下$k = \frac{ b }{ a }$.注意到因为$a$中不能有$0$,所以$k \in \{ 2 , 4 , 5 , 8 \}$.取$k = 2$试出来$3570$是合法的,而且显然$k \in \{ 4 , 5 , 8 \}$的时候不可能有更大的答案了.

Problem20

$a_1 = \sqrt{ 2 } , a_{ n + 1 } = \lfloor a_n \rfloor + \frac{ 1 }{ a_n - \lfloor a_n \rfloor }$,求$\sum_{ k = 1 }^{ n } a_k , n = 2024$.

Solution20

这一看就是个环,设$a_n = b_n + c_n \sqrt{ 2 }$.难点显然在下取整函数.

没想出太好的办法,选择使用数学归纳,注意到:

容易猜测$b_n = 2 ( n - 1 ) , c_n = 1$.也就是$a_n = 2 ( n - 1 ) + \sqrt{ 2 }$,数学归纳一下即可.

那么$\sum_{ k = 1 }^n a_k = n ( n - 1 ) + n \sqrt{ 2 }$,带入$n = 2024$即可.

2022图选

Problem1

问能否将有限个单位正方形摆放在平面上使得:

  1. 任意两个正方形至多有一个顶点重合

  2. 每个正方形的每个顶点都与其他某个正方形的顶点重合

Solution1

这个题传到我这里题面已经丧失了,但反正理解起来就两种情况

  1. 边不能相交.此时不可能.考虑扫描线,从上到下扫一条线,然后第一次扫到的最右边的那个顶点显然不可能和其它的某个正方形顶点重合.

  2. 边可以相交,放到正十二边形的边上.

Problem2

求$\lfloor ( \frac{ 1 + \sqrt{ 5 } }{ 2 } )^{ 12 } \rfloor$.

Solution2

考虑$( \frac{ 1 + \sqrt{ 5 } }{ 2 } )^3 = 2 + \sqrt{ 5 }$,$\lfloor ( \frac{ 1 + \sqrt{ 5 } }{ 2 } )^{ 12 } \rfloor = 161 + \lfloor 72 \sqrt{ 5 } \rfloor = 321$.

也可以考虑类似斐波那契数列,取$f_n = ( \frac{ 1 + \sqrt{ 5 } }{ 2 } )^{ n } + ( \frac{ 1 - \sqrt{ 5 } }{ 2 } )^{ n }$,其满足$f_n = f_{ n - 1 } + f_{ n - 2 } , f_0 = 2 , f_1 = 1$,取$f_{ 12 } - 1$就是答案$321$.

Problem3

对于一个加法乘法环,要求你利用:

  1. 乘法结合律、交换律、对加法的分配律、逆元.

  2. 加法结合律、逆元.

来证明加法的交换律.

Solution3

倒反天罡题.

注意到$( a + 1 ) ( b + 1 ) = ( b + 1 ) ( a + 1 )$,所以$a + b = b + a$.

Problem4

给你$n$个数集$a_i$,其中$| a_i | = i + 1$,要你选出$n$个两两不同的数字满足$x_i \in a_i$,求最少方案数.

Solution4

考虑从小的往大了选,每次可能会删掉一个可选择的数字,所以是$2^n$.

Problem5

Alice和Bob博弈.Alice先选一个数$m$,然后Bob选一个数$n ( n > m )$,并构造一个$n$个点的竞赛图.Alice如果能从中选出$m$个不同的点,满足不存在某个点$x$到这$m$个点都有出边,那么Alice赢,否则Bob赢.问是否有人存在必胜策略.

Solution5

一开始以为Alice肯定赢,结果被gank了.

其实Bob一定赢.为啥呢?考虑一对点合法的概率,应该是$( 1 - \frac{ 1 }{ 2^m } )^{ n - 2 }$,因此期望为$E = \binom{ n }{ m } ( 1 - \frac{ 1 }{ 2^m } )^{ n - 2 }$,只需$n$足够大的时候期望$< 1$,则说明一定存在$0$,也就是Bob总有必胜策略.

注意到只需证明$\exists n$,$\binom{ n }{ m } < ( \frac{ 2^m }{ 2^m - 1 } )^{ n - 2 }$,而$\binom{ n }{ m } = \frac{ n^{ \underline{ m } } }{ m ! } < n^m$.下面证明$\exists n , n^m < ( \frac{ 2^m }{ 2^m - 1 } )^{ n - 2 }$.

两边取$\ln$,不妨假设$n \geq 3$,有$m \ln n < ( n - 2 ) \ln ( \frac{ 2^m }{ 2^m - 1 } ) , \frac{ m }{ \ln ( \frac{ 2^m }{ 2^m - 1 } ) } < \frac{ n - 2 }{ \ln n }$,$\frac{ n - 2 }{ \ln n }$显然在$n \geq 3$的时候单增,所以一定存在这么一个$n$.

2023图选

Problem1

求单位正方形中能放下的最大的等边三角形的边长.

Solution1

首先肯定三角形有一个角卡在正方形的角上(不然可以平移过去),而且剩下两个角肯定卡在边上.

Problem2

求正整数拆分成有序的$1 , 2$序列的个数.

Solution2

显然为斐波那契数.

Problem3

定义$*$为集合$G$上的二元运算,已知:

  1. 满足结合律$a ∗ b ∗ c = a ∗ ( b ∗ c )$.

  2. 存在左单位元$e$,对任意$a$满足$e ∗ a = a$.

  3. 对任意$a$存在左逆元$b$,使$b ∗ a = e$.

问:

  1. 左单位元是否也为右单位元.

  2. 左逆元是否也为右逆元.

Solution3

看(2),考虑设$b$是$a$的左逆元,$c$是$b$的左逆元,则$cba = ce = a , ab = ceb = e$.

看(1),设$b$是$a$的逆元,$ea = aba = ae$,所以左单位元也是右单位元.

值得一提的是,这个题如果将条件(3)改为右逆元,则不一定构成群.

感性理解一下改前的题,如果存在左逆元的话,说明$ab$的时候$b$不能彻底损失信息,而观察$ab = eab$知道$a$也不能损失信息,于是应该是群.

但怎么构造反例呢?首先得造出来左单位元对吧.答案给了一种很聪明的构造方式:考虑运算$( a_1 , b_1 ) ( a_2 , b_2 )$,想办法让其损失掉$( a_1 , b_1 )$中的信息(这样使其不存在左逆元,但可以构造出左幺元).注意到$( a_1 , b_1 ) ( a_2 , b_2 ) = ( a_1 + a_2 , b_2 )$即可,存在左幺元为$( 0 , 0 )$,右逆元为$( - a , 0 )$.

Problem4

$f$的定义域和值域都是正整数并且$f ( xy ) = f ( x ) + f ( y ) - 1$,求:

  1. 是否存在这样的函数.

  2. 是否存在无数个这样的函数.

  3. 是否存在严格递增的函数.

Solution4

令$g ( x ) = f ( x ) - 1$,则$g ( xy ) = g ( x ) + g ( y )$.

对于(1),取$g ( x ) = 0 , f ( x ) = 1$即可.

对于(2),考虑$g ( p^k ) = kg ( p )$,只需要让$g ( p )$取不同的值即可.

对于(3),考虑$g ( 2^a ) = ag ( 2 )$,$g ( 3^b ) = bg ( 3 )$.

考虑构造$a , b$,使得$2^a < 3^b$但是$ag ( 2 ) \geq bg ( 3 )$.不妨取$a = \lceil \frac{ bg ( 3 ) }{ g ( 2 ) } \rceil$,那么必定有:

于是如果存在,必定需要$\frac{ g ( p_1 ) }{ g ( p_2 ) } \geq \log_{ p_2 } p_1 \land \frac{ g ( p_2 ) }{ g ( p_1 ) } \geq \log_{ p_1 } p_2$,也就是$\frac{ g ( p_2 ) }{ g ( p_1 ) } = \log_{ p_1 } p_2$.但是左边是有理数右边是无理数,不可能.

Problem5

对于任意$2 n - 1$个正整数(可重复),问其中是否一定有$n$个数的和能被$n$整除,这题$n = 50$.

Solution5

考虑当$n$是合数的时候,设$n = pq$,则可以将其拆成$q - 1$组每组$2 p$个数以及一组$2 p - 1$个数,因此只需要这些都可以找到$p$个数使得其是$p$的倍数,组合起来就行了.

只需要解决$n$是质数的情况.

感觉场上的最优解应该是解决$n = 2$和$n = 5$的情况然后拼成$n = 50$.

$n = 2$的时候显然是对的.

这谁想得到啊?

考虑反证,如果不存在的话,显然$S = \sum_{ } ( x_{ p_1 } + x_{ p_2 } + \cdots + x_{ p_n } )^{ p - 1 } \equiv \binom{ 2 n - 1 }{ n } \equiv 1 \pmod{ n }$.

但是考虑左边那个多项式的每一项,形如$c \prod_{ i = 1 }^k x_{ p_i }^{ e_i }$.注意到$c$一定是$\binom{ 2 n - 1 - k }{ n - k }$的倍数,而后者$\bmod n$为$0$.

这玩意到底咋想到的?

不过其实也合理,因为$1$并不是对称的,而左边是个对称式子,某个$x$增大也无所谓,这意味着左边应该是为$0$的,我们要做的就是去证明它是$0$.

2024图选

Problem1

问在双曲线$xy = 1$上有一个三个点都在上面的等边三角形,求其边长.

Solution1

不会做,取个特殊值知道答案应该是$[ 2 \sqrt{ 6 } , + \infty )$.

Problem2

我们称”能表示为两个数的平方和”的数是好的,求证:

  1. 如果$n , m$都是好的,那么$nm$是好的.

  2. $2024$不是好的.

Solution2

如果$n = a^2 + b^2 , m = c^2 + d^2$,那么$nm = a^2 c^2 + a^2 d^2 + b^2 c^2 + b^2 d^2 = ( ac - bd )^2 + ( ad + bc )^2$.

$2024 = 2^3 \times 11 \times 23$,使用反证法,不妨设其可以被表示为$a^2 + b^2$.

讨论一下:如果$a , b$均为奇数,那么$a^2 + b^2 \equiv 2 \pmod{ 8 }$,不符题意.

于是$a , b$应该均为偶数,那么就有$a ‘^2 + b ‘^2 = 506$.简单枚举一下就知道不存在.

当然这个题是个数竞结论,可以直接套用结论.

Problem3

对于集合$G$,$e \in G$,定义域为$G$的函数$f$满足以下性质:

  1. $e \in G$,但$e$不在$f$的值域中.

  2. $G$关于$f$封闭.

  3. 若$\exists A \subseteq G$,$e \in A$且$A$对$f$封闭,则$A = G$.

在$G$上定义二元运算$\circ$,满足$ae = a , af ( b ) = f ( ab )$.

求证:

  1. 存在幺元.

  2. 运算满足交换律.

  3. 运算满足结合律.

Solution3

只需要证明运算满足交换律即可.

考虑性质(3),我们不妨先往$A$里面扔个$e$,此时$A$一定不满足条件.我们不断从$A$中选出一个元素$w$满足$f ( w ) \notin A$,并把$A : = A \cup \{ f ( w ) \}$.不断做这个过程显然最后会得到$G$,这意味着任何一个元素$a$可以写成$f ( f ( f \cdots f ( e ) ) )$的形式.

不妨将$f$函数嵌套$k$次记作$f^{ ( k ) }$,那么我们要证明的是$a = f^{ ( A ) } ( e ) , b = f^{ ( B ) } ( e )$,$ab = ba$.

考虑$ab = f^{ ( A ) } ( e ) f^{ ( B ) } ( e ) = f^{ ( B ) } ( f^{ ( A ) } ( e ) e ) = f^{ ( A + B ) } ( e )$,因此证毕.

Problem4

给出一个具体函数满足:

  1. $f ( x + y ) = f ( x ) + f ( y ) + xy$.

  2. $f ( xy ) = f ( x ) f ( y ) + f ( x - 1 ) f ( y - 1 )$.

Solution4

先注意到$f ( 0 ) = 0 , f ( 1 ) = 1$.

以$x$为主元两边求导,立刻得到$f ‘ ( x + y ) = f ‘ ( x ) + y$,因此$f ‘ ( x )$是斜率为$1$的一次函数,立刻得到$f ( x ) = \frac{ x^2 }{ 2 } + \frac{ x }{ 2 }$.

Problem5

对于$r = \sqrt{ 2 }$,是否存在正整数$p$和整数$q$满足$| pr - q | < \frac{ 1 }{ 2024 }$且$p < 2024$.

Solution5

考虑取$0 , \sqrt{ 2 } , 2 \sqrt{ 2 } , 3 \sqrt{ 2 } , \cdots 2023 \sqrt{ 2 }$的小数部分,记作$a_0 , a_1 , \cdots a_{ 2023 }$.

由鸽笼原理,一定存在两个数$0 \leq x < y \leq 2023$满足$| a_x - a_y | < \frac{ 1 }{ 2024 }$,于是证毕.

2019茶选

Problem1

在一个数轴上,你站在$0$点,并按照如下算法寻找$x ( x > 0 )$点处的牛:

1
2
3
4
5
6
7
curpos = 0;
curdir = LEFT;
step = 1;
while (没有找到牛) {
沿着 curdir 方向，走 step 单位距离，如果找到牛就停止;
如果没有找到牛，回到原点并将 curdir 设为反方向，step = step * 2;
}

大约至少需要多少步才能找到牛?

A. $3 x$ B. $5 x$ C. $7 x$ D. $9 x$ E. 以上答案都不对.

Solution1

考虑找到牛的时候$step$为多少,应该为$2^{ 2 k }$,其中$k$满足$2^{ 2 k } \geq x > 2^{ 2 ( k - 1 ) }$.此时走的步数应该是$ans = 2 \sum_{ i = 0 }^{ 2 k - 1 } 2^i + x = 2^{ 2 k + 1 } - 1 + x$步.而$x \leq 2^{ 2 k } < 4 x$,所以$ans < 9 x - 1$.

Problem2

给定$10$个实数变量$x_1 , \cdots , x_{ 10 }$,满足它们均$\geq 1$且两两不同.你要寻找一组$\{ x \}$和一个实数$a$,使得存在尽可能多组$\langle b \rangle , b_i = \pm 1$,满足$\sum_{ i = 1 }^{ 10 } b_i x_i \in ( a , a + 2 )$.

最多存在多少组$\langle b \rangle$?

A. $512$ B. $252$ C. $504$ D. $684$ E.以上答案都不对.

Solution2

不妨猜测$x$全取$1$最优,此时的答案是$\binom{ 10 }{ 5 } = 252$.

能不能严格证明这个事情呢?我们不妨注意到一个事情:由于$x \geq 1$,所以如果存在两组$\langle b \rangle$,使得$A$组中选择取$+ 1$恰好是$B$组的子集,那么$S_A \leq S_B - 2$,不可能同时满足条件.

如果我们能选出若干个互不相交的集合呢?那我们显然可以让$x$尽可能接近$1$,这样就是满足条件的.所以问题变为对于一个大小为$10$的集合,要在其中挑选出尽可能多的子集使得这些集合两两之间没有包含关系,有结论说这个东西取$\binom{ 10 }{ 5 }$最优,即Sperner定理.其实也就是Dilworth定理的特例.

Problem3

给定无向图$G = ( V , E )$,我们称一个图是好的,如果:

  1. 每个点的度数均为$d$.

  2. 任何一个大小不超过$\frac{ | V | }{ 2 }$的联通集合$S$,其邻居(不属于$S$但和$S$中的某个点存在直接相连的边)的大小$\geq \frac{ 5 }{ 4 } | S |$.

求证:好的图中任意两个点$u , v$之间的最短路径长度$dis ( u , v ) = O ( \log | V | )$.

Solution3

考虑以$u$为起点一点一点往外扩张,这样一直扩张到$\frac{ | V | }{ 2 } + 1$时,集合中每个点到$u$的距离不超过$O ( \log | V | )$.

然后以$v$做同样的事,由于这两个集合大小之和大于$| V |$,说明一定有交,且存在一条路径长度为$O ( \log | V | )$的路径,最短路径肯定比这个还短.

Problem4

给你两个完全相同的鸡蛋和一个$n = 100$层的高楼,你每次可以将鸡蛋从某一层楼掉下去.问你最少用多少次操作才能测出能让鸡蛋摔碎的最低楼层.

Solution4

经典信息论题.考虑构造一棵左倾的决策树,从根到任何一个叶子节点最多向右走两步,并且有$101$个叶子节点(因为还有可能从最高层掉下去不碎).

设$f_{ i , 1 / 2 }$表示一棵有$i$个叶子的树,最多向右走$1 / 2$步,深度最低为多少.显然$f_{ i , 1 } = i - 1$.

不妨设最后的最大深度为$k$,需要满足$1 + \sum_{ i = 1 }^k i = 1 + \frac{ k ( k + 1 ) }{ 2 } \geq 101 , k ( k + 1 ) \geq 200$,$k_{ \min } = 14$.

Problem5

$n$个人要进行一场游戏.游戏设计者准备了$n$张卡片,正面分别写着$n$个人的名字,背面写了$[ 1 , n ]$共$n$个不同的数字.所有卡片都背面朝上放置在一个房间里.

当设计者准备完成后,$n$个人可以经过充分的讨论,并依次进入房间,一张一张地翻开$\lfloor \frac{ n }{ 2 } \rfloor$张卡片,并找到写有自己名字的卡片.当一个人操作结束后,他无法与其他人交流直到游戏结束.

只有所有$n$个人全部找到了写有自己名字的卡片,他们才能获胜.请问:是否存在一种策略,使得无论设计者怎样安排名字和数字的对应,他们均拥有超过$0 . 1$的胜率.

Solution5

这题真理元素讲过.做法是每个人先翻开自己编号的位置的卡片,假设卡片上数字是$a$,如果$a$就是自己的编号就下班;反之接下来翻开$a$位置的卡片.为了防止设计者刻意安排,可以提前自己随机一个数字的映射.这样失败当且仅当场上存在一个长度大于$\frac{ n }{ 2 }$的环.

考虑总方案数是$n !$.不妨枚举这个环的长度为$K$,则存在一个长度$= K > \frac{ n }{ 2 }$的环的方案数是$\binom{ n }{ K } ( K - 1 ) ! ( n - K ) ! = \frac{ n ! }{ K }$.所以此时的概率为$\frac{ 1 }{ K }$.

那么失败的概率就是$H_n - H_{ \frac{ n }{ 2 } } \approx \ln 2$.

2022茶选

Problem1

证明弱对偶定理,差不多就是:

提一个问题:最大化$z = 5 x_1 + 8 x_2 + 4 x_3$,其中:

  1. $x_1 , x_2 , x_3 \geq 0$

  2. $\frac{ 1 }{ 2 } x_1 + 5 x_2 + 9 x_3 \leq 3$

  3. $4 x_1 + 7 x_2 + 3 x_3 \leq 6$

再提一个问题:最小化$v = 3 y_1 + 6 y_2$,其中:

  1. $y_1 , y_2 \geq 0$

  2. $\frac{ 1 }{ 2 } y_1 + 4 y_2 \geq 5$

  3. $5 y_1 + 7 y_2 \geq 8$

  4. $9 y_1 + 3 y_2 \geq 4$

现在请你证明:$z \leq v$.

Solution1

下面乘一下配一下上面的系数,自然得证.

写成矩阵形式,设$X = \begin{bmatrix}x_1 & x_2 & x_3\end{bmatrix} , A = \begin{bmatrix}0 . 5 & 4 \ 5 & 7 \ 9 & 3\end{bmatrix} , Y = \begin{bmatrix}y_1 \ y_2\end{bmatrix}$,不难发现$z \leq XAY \leq v$.

Problem2

半径为$R$的球里放点,要求两两之间距离不能小于$1$,证明至多放$( 2 R + 1 )^3$个.

Solution2

要求两两距离不能小于$1$等价于往其中放半径为$0 . 5$的球,这种球体积为$\frac{ 4 }{ 3 } \pi \frac{ 1 }{ 8 }$.然后原球要扩大一圈,所以原球体积变为$\frac{ 4 }{ 3 } \pi ( R + 0 . 5 )^3$.除一下得到答案.

Problem3

一个无限长的数轴上有一辆车,它的初始坐标是个未知的整数$n$.

它每秒以$v$的速度行驶,其中$v$是个未知的整数(可以为负).

现在你每秒能进行一次这样的询问:询问整数$x$,你会得知此时车的坐标是否是$x$(Yes or No).

请给出一个策略,使得在有限的时间里可以获得一次Yes回答.

Solution3

第$t$秒的时候车应该在$n + vt$处.由于我们知道现在是第几秒,枚举$n , v$然后不断check即可.这个是经典的证明$\mathbb{ Z }^2$和$\mathbb{ N }$等势.按照$| n | + | v |$排序然后一个一个遍历.

Problem4

对满足$\forall i , | i - p_i | \leq 1$的排列计数.

Solution4

简单题,设$f_n$为答案,考虑$p_n$取什么.

当$p_n = n$时,方案数为$f_{ n - 1 }$.

当$p_n = n - 1$时,$p_{ n - 1 } = n$,方案数为$f_{ n - 2 }$.

于是,$f_1 = 1 , f_2 = 2$,$f_n = f_{ n - 1 } + f_{ n - 2 }$.

Problem5

你有一个$n \times n$的棋盘.初始所有格子都是白色的.

你可以选择$k$个格子染黑.此后,如果某个格子四联通的两个格子都是黑色,它自己也会变成黑色.

你要让所有格子最终都变黑.试证明:你一开始选择染黑的格子数$k$最小值是$n$.

Solution5

数学归纳了半天,屁用没用.

注意到在扩张过程中,黑色格子的周长不会变大,所以至少是$\frac{ 4 n }{ 4 } = n$个.

Problem6

设$F = \{ S_1 , S_2 , S_3 , . . . , S_{ | F | } \}$,定义一个集合$T$能被$F$ shattered为:$T$的任意一个子集(包括它自己和空集),都可以由$T \cap S_{ i_1 } \cap S_{ i_2 } . . .$表示.其中$S_{ i_j }$是$F$中的集合(就是说每个子集都等于$T$和某些$F$内集合的交.)

定义一个$F$的”VC-Dimension”是,能被他shattered的集合$T$的大小的最大值.

$F$中的集合们只会包含某$n$种不同的元素.证明:

  1. 任意一个$F$能shattered的$T$至少有$| F |$个.

  2. 对于一个VC-Dimension的大小为$k$的$F$,其$| F | \leq \sum_{ i = 0 }^k \binom{ n }{ i }$.

Solution6

显然只要证明了(1),那么(2)是显然的.

那么怎么证明(1)呢?考虑数学归纳.先考虑拎出所有的$S$,满足$S , S \cup \{ x \} \in F$,然后将这些$S \cap \{ x \}$拎出来,假设有$t$个,左边删去$x$后再进行数学归纳得到$| F | - t$个集合(由于拎出了所有满足上述条件的集合,不可能删出重复的集合),右边也有$t$个集合,在这$t$个集合添上$x$这个元素即可.

$t = 0$怎么办?我们自己造一组满足条件的就行了.每次加入一个集合:如果这个集合存在一个前面所有的集合都没有的元素,那么显然把这个元素拎出来就行了.又注意到如果一个元素全局都有的话,那么很废物对吧,我们把这个元素删掉继续做.此时不妨设新加入的集合为$S$(选取最大的那个集合为新加入的),我们在前面的集合中找到一个与$S$有交的集合$T$,根据上面的预处理,此集合显然存在.选出一个$x \in S \setminus T$,不妨设$S = S ‘ \cup \{ x \}$,令$T ‘ = S ‘ \cap T$,然后用$T ‘$代替原本的$T$即可.

2023茶选

Problem1

令$p ( x )$表示$x$的最大质因子,求所有$( x , y , z )$使得:

  1. $x < y < z$且$x + z = 2 y$.

  2. $p ( xyz ) \leq 3$.

Solution1

不妨令$g = \gcd ( x , y , z )$,令$x ‘ = \frac{ x }{ g }$,则只需要解:$x ‘ + z ‘ = 2 y ‘$.

我们有$y - x = z - y$,则$\gcd ( y ‘ , x ‘ ) = \gcd ( y ‘ , y ‘ - x ‘ ) = \gcd ( y ‘ , z ‘ ) = 1$,用这个能解决不少讨论.

此时有以下两种情况:

  1. $2 \nmid x ‘ , 2 \nmid z ‘$.

  2. $2 \mid x ‘ , 2 \mid z ‘ , 2 \nmid y ‘$.

先看(1),设$x ‘ = 3^a , z ‘ = 3^c , y ‘ = 2^b$.方程变为$3^a ( 1 + 3^{ c - a } ) = 2^{ b + 1 }$,一定有$a = 0$,只需解$1 + 3^{ c } = 2^{ b + 1 }$.

当$b \leq 2$的时候,经检验有$\begin{cases}c = 0 \ b = 0\end{cases}$(舍)和$\begin{cases}c = 1 \ b = 1\end{cases}$两组解.

当$b \geq 3$的时候,注意到$3^{ c } \equiv - 1 \pmod{ 4 }$,所以$c$是偶数.又注意到$3^{ c } \equiv - 1 \pmod{ 8 }$,但是奇数的平方$\bmod 8$应该是$1$,不符.

再看(2),设$x ‘ = 2^d , z ‘ = 2^e , y ‘ = 3^b$.

当$e = 1$时,显然不符.

当$d = 1 , e > 1$时,要解$2^{ e - 1 } + 1 = 3^{ b }$.当$e = 2$的时候有一组解$\begin{cases}e = 2 \ b = 1\end{cases}$.当$e \geq 3$的时候,有$3^b \equiv 1 \pmod{ 4 }$,说明$b$是偶数.

那必然有$2^{ e - 1 } = 3^b - 1 = ( 3^{ \frac{ b }{ 2 } } + 1 ) ( 3^{ \frac{ b }{ 2 } } - 1 )$.令$t = 3^{ \frac{ b }{ 2 } } - 1$,则$2^{ e - 1 } = t ( t + 2 )$.则要么$t = 2$,要么$t + 2 = 2$.解出$b - 2$,此时有$\begin{cases}e = 4 \ b = 2\end{cases}$.

综上,解出来的解有$\begin{cases}x ‘ = 2 \ y ‘ = 3 \ z ‘ = 4\end{cases} , \begin{cases}x ‘ = 1 \ y ‘ = 2 \ z ‘ = 3\end{cases} , \begin{cases}x ‘ = 2 \ y ‘ = 9 \ z ‘ = 16\end{cases}$.

但其实有更厉害一点的做法,考虑升幂引理.

先看方程$2^x + 1 = 3^y$,考虑两边$\bmod 3$知道$x$是奇数,于是$v_3 ( 2^x + 1 ) = v_3 ( 3 ) + v_3 ( x ) = y , 3^{ y - 1 } | x , x \geq 3^{ y - 1 }$,用这个放缩一下就行.

再看方程$2^x = 3^y + 1$.仍然考虑两边$\bmod 4$,知道$y$是奇数.$x = v_2 ( 3^y + 1 ) = v_2 ( 3 + 1 ) = 2$,当场下班.

Problem2

给定两个随机分布：

$x ∼ D_1$:从${ 0 , 1 , … , p − 1 }$中等概率随机一个$y$,令$x = y   \bmod  { 2^k }$.

$x ∼ D_1$:从${ 0 , 1 , … , 2^k - 1 }$中等概率随机一个$y$,令$x = y$.

定义二者的统计距离为:$SD ( D_1 , D_2 ) = \frac{ 1 }{ 2 } \sum_{ i = 0 }^{ 2^k - 1 } | P_{ D_1 } ( x = i ) - P_{ D_2 } ( x = i ) |$.

求证:$SD ( D_1 , D_2 ) ≤ \frac{ 2^k }{ 4 p }$.

Solution2

令$w = p \bmod{ 2^k }$.则$SD ( D_1 , D_2 ) = \frac{ w }{ 2 } ( P_{ D_1 } ( x = 0 ) - P_{ D_2 } ( x = 0 ) ) + \frac{ 2^k - w }{ 2 } ( P_{ D_2 } ( x = w ) - P_{ D_1 } ( x = w ) )$.

令$k = \lfloor \frac{ p }{ 2^k } \rfloor = \frac{ p - w }{ 2^k }$不难发现$P_{ D_1 } ( x = 0 ) = \frac{ k + 1 }{ p } , P_{ D_1 } ( x = w ) = \frac{ k }{ p }$.

则$SD ( D_1 , D_2 ) = \frac{ w }{ 2 } ( \frac{ p - w + 2^k }{ p 2^k } - \frac{ 1 }{ 2^k } ) + \frac{ 2^k - w }{ 2 } ( \frac{ 1 }{ 2^k } - \frac{ p - w }{ p 2^k } ) = \frac{ 1 }{ 2^{ k + 1 } } ( \frac{ w ( 2^k - w ) }{ p } + \frac{ w ( 2^k - w ) }{ p } ) = \frac{ w ( 2^k - w ) }{ p 2^k }$.

要证明$\frac{ w ( 2^k - w ) }{ p 2^k } \leq \frac{ 2^k }{ 4 p } \Leftrightarrow w ( 2^k - w ) \leq ( 2^{ k - 1 } )^2$.由基本不等式显然.

Problem3

给你一个单增函数$f$,满足定义域和值域都是$\mathbb{ N }$,并且$f ( f ( n ) ) = 3 n$,求$f ( 2023 )$.

Solution3

首先我们不妨先试一下$f ( f ( 1 ) ) = 3$.由于$f ( 1 ) \geq 2$,且$f ( 1 ) \ne 3$,所以$f ( 1 ) = 2 , f ( 2 ) = 3$.

考虑$f ( 3 n )$,必然存在一个$n < m < 3 n$,使得$f ( n ) = m , f ( m ) = 3 n$.

用这个找前几项,发现规律是把$n$写成三进制形式,如果首位是$1$就变成$2$,首位是$2$就改为$1$再在后面加个$0$.容易验证这是合法的$f$且$f ( 2023 ) = 3882$.

但问题没有解决,需要证明它是唯一的$f$.

考虑数学归纳假设现在$f ( x ) , x \in [ 1 , 3 k ]$都确定了.

注意到如果$f ( n ) = m , f ( m ) = 3 n , f ( 3 n ) = 3 m , f ( 3 m ) = 9 n$.所以如果$f ( n ) = m$,我们实际上有$f ( 3^k m ) = 3^{ k + 1 } n , f ( 3^k n ) = 3^k m$.数学归纳即可以证明$f ( 3 k + 3 )$一定是确定的.

接下来要证明$f ( 3 k + 1 )$和$f ( 3 k + 2 )$一定是确定的.

手玩发现确定它们的方式有两种:

  1. $f ( 3 k ) + 3 = f ( 3 k + 3 )$.

  2. $\exists n , f ( n ) = 3 k + w ( w \in \{ 1 , 2 \} )$.

如果我们能说明至少可以取二者其一就行.

由归纳假设,不难发现当$k$在三进制下首位如果是$2$,则一定满足(2).

当$k$在三进制下首位是$1$,则一定满足(1).

于是证毕.

Problem4

对于一个$n \times n$的包含$[ 1 , n^2 ]$各一个的矩阵(下称为排列矩阵),定义一次操作为:将每行都任意重排;或将每列都任意重排.求证:

  1. 如果一个排列矩阵满足每行恰有模$n$余$[ 0 , n - 1 ]$的数各一个,则称它是好的.求证:好的矩阵可以通过两次操作变为一个满足第$i$行第$j$列为$( i - 1 ) n + j$的矩阵(不妨称为有序矩阵).

  2. 求证:任意排列矩阵可以通过一次操作变为好的.

Solution4

这题原题啊,AGC037D.

(1)显然,注意到有序矩阵的每列$\bmod n$不相同,可以先将每行按照$\bmod n$排序,再每列排序即可.

(2)的话我们考虑一次列操作.将$\bmod n$不同的数字分类,然后建一个二分图:左侧的点是数字分的类,右侧的点代表行,注意到这个东西是$n$正则二分图,根据Hall定理一定存在完美匹配.

Problem5

有$n ( \geq 2 )$个硬币排成一个环.你被蒙上眼睛,你每次操作可以选择一个硬币的子集并将它们翻面.但是你每次操作之后,硬币的位置将会任意旋转(即变为原来的一个循环同构).如果你存在一种策略,使得对于任意初始局面和任意中途的旋转方案,有限步内一定可以令存在一个时刻所有硬币正面朝上,则称$n$是好的.求证:

  1. $4$是好的.

  2. 如果$n$是奇数,那么$n$不是好的.

  3. 求出所有好的$n$.

Solution5

首先可以证明$2$是好的.

这么干:如果一开始都正面向上就赢了.不然第一步全翻,这样如果一开始是反面向上也赢了.下一次随便翻一个,再下一次全翻,这样四次中至少赢了一次.

从上面的观察可以发现啊,我们场上一定会进行若干次全局翻转操作,并且最后一次一定是一个全局翻转,不然我们每次只需要让一个位置保持不被翻到就输麻了.

转全局太复杂了,考虑转操作,问题转化为现在你要排若干个操作,使得它们任意旋转后,仍然可以保证前缀异或和取到了所有的情况.注意到不妨让第一轮轮空,此时最少需要$2^n$步.

不妨每进行一次非全局操作就全局翻一次,这样$0$和$1$就没区别了.

先考虑全局异或和为偶数的时候:

注意到$1100$来一个$1010$之后啥也不变,但是$1010$来一个$1010$一定赢了.所以上来先来一个$1010$,如果赢了就下班,没赢就来个$1100$,这样$1100$要么下班,要么变成了$1010$,再重复上面的操作.

如果全局异或和为奇数,那就随便异或一下,再按照偶数的做.

总的来说,先按照偶数的操作,不会改变全局异或和.如果没结束说明是奇数,变一下重复以上操作.

总结一下的话就是操作序列是:$0000 , 1111 , 1010 , 1111 , 1100 , 1111 , 1010 , 1111 , 1000 , 1111 , 1010 , 1111 , 1100 , 1111 , 1010 , 1111$.

上面的构造启发我们手玩一下$n = 3$,注意到此时的问题在于$100$和$110$,都很完蛋.

我们先考虑弱化版问题:就是我们摘下了眼罩,但是选择策略在旋转之前.如果这种情况我们都做不到那蒙上眼更做不到了对吧.

我们不妨将所有的状态分为两类:一类叫做成功状态,即如果一个状态是成功的,那它可以通过有限次操作得到全$0$;另一类叫做失败状态,即只要初值是它,一定有一种旋转的方式使得一直得不到全$0$.

我们来仔细看一下这两个状态应该是啥样的:

对于一个成功状态,应该有一个固定的选择翻面策略,使得它可以在有限次操作内达到另一个更接近全$0$的成功状态.我们不妨令一个成功状态的度为$d$表示它可以经过$d$步到达全$0$,显然全$1$的$d = 1$,$n = 4$的时候,$1010$的$d = 2$,因为其可以通过一次操作转化为全$1$,$1100$的$d = 3$,因为其可以用一次操作转化为$1010$.

仔细思考上面的过程,也就意味着:任何一个成功状态的所有出边,必然要指向$d$比它更小的成功状态.

对于一个失败状态,应该有一个任意的选择旋转策略,使得它怎么翻都还是失败状态.

这个定义还是挺粗糙的,我们先看失败状态吧.

显然$n = 3$的时候,$\{ 110 , 100 \}$就是失败状态.

而对于$n$取任意来说,一定得存在一个$d = 2$的成功状态.一个显然的$d = 2$的成功状态要满足的条件是,假设它是$a$,那么存在一个数$b$,使得$a \oplus b$是全$1$或者全$0$.既然$a$和$b$旋转后只有两种结果,那么$b$的循环节必定为$2$,也就是$b$一定要是$101 \cdots 010$这样的,于是$n$是奇数的时候一定不符合,这就证明了(2).

同理寻找$d = 3$的成功状态,现在我们已知的四种成功状态是$111 \cdots 111$,$000 \cdots 000$,$101 \cdots 010$,$010 \cdots 101$,所以考虑构造一个循环节长度为$4$的串,使得异或完它是这上面四种其一,注意到$1100 \cdots 1100$就是一个合法的串.

做到这里发现上面那个东西完全无法扩展啊.更要命的是我们现在还是睁着眼的,甚至没证明闭着眼是一样的.

找qyc讨论了一下得到了另一个思路的做法:

先证明$n = 2^k$一定是好的.考虑数学归纳,不妨这么干:构造一个长度为$2^{ k - 1 }$的串$b$,使得其$b_i = a_i \oplus a_{ i + 2^{ k - 1 } }$.然后由数学归纳,可以造出$b$全$0$的情况.而如果$b$全$0$,则原串一定存在长为$2^{ k - 1 }$的循环节,并且消除循环节的过程不会改变$b$的值,仍然是数学归纳下去就做完了.

不然,设$n = 2^k m$,

模仿上面的过程,不妨使用数学归纳证明其不成立.仍然是构造$b$数组,由于$b$数组都不可能全$0$,显然也不可能成立.

这个能不能顺便证明$n$是奇数一定不行呢?还真可以.

考虑你现在要卡掉蒙眼的对手的构造,你选出一个位置来备用,剩下了$n - 1$个位置.

接下来无论对手怎么出,你都可以通过乱搞这个备用的位置,来保证前$n - 1$个位置的异或值为$1$.因此对手一定不能完成任务.

2024茶选

Problem1

连续扔一枚硬币,连续扔出三个正面则停止.假设硬币扔出正面反面的概率都为$50 \%$,求期望停止时间.

Solution1

简单题,设$f_0 , f_1 , f_2 , f_3$,然后有$\begin{cases}f_3 = 0 \ f_2 = \frac{ 1 }{ 2 } f_3 + \frac{ 1 }{ 2 } f_0 + 1 \ f_1 = \frac{ 1 }{ 2 } f_2 + \frac{ 1 }{ 2 } f_0 + 1 \ f_0 = \frac{ 1 }{ 2 } f_1 + \frac{ 1 }{ 2 } f_0 + 1\end{cases}$,算出$f_0 = 14$.

Problem2

Alice和Bob玩游戏,一共有三轮.每一轮中,Alice选择一个实数,Bob将这个数填到下式中任意一个框中.进行三轮后,如果下式方程有三个不同的整数解则Alice赢,反之Bob赢,求是否有必胜策略.

Solution2

纯粹的构造.

简单分析一下,不妨设三个解为$- A , - B , - C$,方程应该可以写作$( x + A ) ( x + B ) ( x + C ) = 0$.

拆开有$x^3 + ( A + B + C ) x^2 + ( AB + AC + BC ) x + ABC = 0$.

这么对称,不妨猜一手Alice先选择$0$,讨论一下:

  1. Bob令$ABC = 0$.不妨令$C = 0$.

此时方程变为$x^2 + ( A + B ) x + AB = 0$.直接秒了,随便选一个数就行(比如选$3$,如果Bob令$AB = 3$,就再选$4$;如果令$A + B = 3$,就再选$2$)

  1. Bob令$A + B + C = 0 , C = - A - B$.

不妨令$C ‘ = - C , D = AB$,则$AB + AC + BC = D - C ‘^2 , ABC = DC ‘$.

接下来Alice要选择一个数字$k$,如果Bob又令$D - C ‘^2 = k$,发现在此时如果$k$是一个负的完全平方数,并且Alice接下来选择$0$,当场就下班了.

所以不妨直接让$k = - n^2$,然后看当$DC ‘ = - n^2$的时候如何去解.此时有$AB ( A + B ) = n^2$.不难发现取勾股数就很优秀.

总结一下就是,Alice第二步选择$- 3^2 \times 4^2 \times 5^2$,这样就赢了.

  1. Bob令$AB + AC + BC = 0 , C = - \frac{ AB }{ A + B }$.

我是构造不出来了.但我可以抄答案,答案是你接下来选择$6^2 \times 7^3$,两种情况如下:

后来又找人讨论了一下这个是咋得出来的啊.考虑$ABC \ne 0$,我们有的条件其实是$\frac{ 1 }{ A } + \frac{ 1 }{ B } + \frac{ 1 }{ C } = 0$.方程现在是$x^3 + ( A + B - \frac{ AB }{ A + B } ) x^2 - \frac{ A^2 B^2 }{ A + B } = 0$.不妨令$a = A + B , b = AB$,方程实际上是$x^3 + ( a - \frac{ b }{ a } ) x^2 - \frac{ b^2 }{ a } = 0$.最好能让$a$小一点,因此我们不妨直接取$a = 1$,此时$A = - n , B = n + 1 , C = n ( n + 1 )$,只要能构造这样的两组$A , B , C$使得它们的$a_1 - \frac{ b_1 }{ a_1 } = - \frac{ b_2^2 }{ a_2 }$即可.直接造看上去没啥前途,但是不难发现$A = - nk , B = ( n + 1 ) k , C = n ( n + 1 ) k$依然合法.此时有$k_1 = a_1 , b_1 = - n ( n + 1 ) a_1^2 , k_2 = a_2 , b_2 = - n ( n + 1 ) a_2^2$,我们有$a_1 ( n^2 + n + 1 ) = - n^2 ( n + 1 )^2 a_2^3$.取$n = 2$试试看!此时有$7 a_1 = - 36 a_2^3$.取$a_2 = 7 , a_1 = - 6^2 \times 7^2$,这就是上面那组答案的构造过程.

Problem3

人们之间可能会有讨厌的情况,讨厌关系是相互的.一个人最多讨厌另外$3$个人.现在希望将全部的人分成两组,使得每个人在自己的组内至多只讨厌$1$个人.这是一定可以办到的吗?

Solution3

考虑增广,对于一个不合法的点,它应当连了两个同色点.不妨将这个点反色,那么同色边的数量一定减少,因此一定存在操作终点.而只要当前不合法就一定可以继续操作,因此操作终点一定合法.

Problem4

有公式:

其中$f$是任意一个将$\{ 0 , 1 \}^n \rightarrow \{ 0 , 1 \}$的函数,$\oplus$是二进制意义下的异或运算,$R$是$\{ 0 , 1 \}^n$上的均匀分布,$R_i$表示第$i$位.再定义$\chi_S ( r ) = \prod_{ i \in S } ( - 1 )^{ r_i }$.

按照下面的步骤证明上面的式子,也就是说,求证:

  1. $\chi_S ( r ) \times \chi_S ( r ‘ ) = \chi_S ( r \oplus r ‘ )$.

  2. 当$r \ne 0$时,$\sum_{ S \subseteq \{ 1 , \cdots , n \} } \chi_S ( r ) = 0$.

  3. $[ f ( r ) \oplus \bigoplus_{ i \in S } r_i = 0 ] - [ f ( r ) \oplus \bigoplus_{ i \in S } r_i = 1 ] = ( - 1 )^{ f ( r ) } \chi_S ( r )$.

  4. 证明原命题.

Solution4

(1)显然.

(2)也很经典,挑选一个$j$,使得$r_j = 1$,然后所有的集合分为两类:一类是包含$j$,一类不包含,两类集合一一对应并且$\chi$互为相反数.

(3)显然.

来看(4),注意到$P ( f ( R ) \oplus \bigoplus_{ i \in S } R_i = 0 ) = \frac{ 1 }{ 2^n } \sum_{ r } [ f ( r ) \oplus \bigoplus_{ i \in S } r_i = 0 ]$,而$\sum_{ r } [ f ( r ) \oplus \bigoplus_{ i \in S } r_i = 0 ] - [ f ( r ) \oplus \bigoplus_{ i \in S } r_i = 1 ] = \sum_r ( - 1 )^{ f ( r ) } \chi_S ( r )$,要证明的只是$\sum_{ S } \frac{ 1 }{ 4^n } ( \sum_r ( - 1 )^{ f ( r ) } \chi_S ( r ) )^2 = 1$,而:

于是证毕.

Problem5

Alice在手心上写了两个不同的实数.你可以看其中一只手上的,然后猜哪边的数大.设计一种策略使得不论两个数是什么,猜对的概率都严格大于$50 \%$.

Solution5

我对这个题有亿点小疑问,但是先说策略.

随机(无需均匀)一个数$x$,然后随机一只手,看上面的数字$a$,如果$a \geq x$就认为$a$大,反之认为$b$大.只要随机到一个区间内的实数的概率不为$0$即可.

但是怎么随机实数呢?好像可以按照正态分布随机,我其实也不太懂.

Problem6

使用一些长方形的砖头搭墙.如果每块砖头都有至少一条边的长度是整数,且搭出的墙面是没有缝隙的长方形,求证:这个长方形也至少有一条边长是整数.

Solution6

这个题是经典知乎题,下面搬一下知乎上面整理的这个题的答案:

数论证明:令$p$为素数,把整个图形放大$p$倍(也就是长度$1$变成长度$p$).下面把每个交叉点$( x , y )$换成其整数部分$( \lfloor x \rfloor , \lfloor y \rfloor )$,我们就得到了一个新的大矩形,它被划分为很多两边长均为整数的小矩形,而且每个小矩形有一边长能被$p$整除.这样这个新的大矩形的面积也能被$p$整除,所以它的有一边长能被$p$整除.这条边只是被换成了它长度的整数部分,所以变化不超过$1$,所以在放大之前这条边的长度和某个整数相差不超过$1 / p$.因为素数有无穷多个,所以原来的大矩形某一条边长度与某个整数相差无限小,证毕.

图论证明:令所有的交叉点为顶点.每个小矩形都有一边长为整数,我们把这两条边长为整数的边在图上标出(允许两顶点之间的重复边),另外两条边不连.这样除了大矩形的四个角以外每个顶点有$2$条边或者$4$条边(这是因为这个点,要么是处于一个丁字路口(两条边),要么是十字路口(四条边)),而大矩形四个角每个角只连了一条边.所以从大矩形一角开始存在一条欧拉路径在另一个角结束.因为图上连边的边长都是整数,把这个欧拉路径投影到大矩形的长宽,我们就得到了大矩形至少有一边长为整数.

组合证明:考虑Sperner引理(和染色有关的那个).假设结论不成立.把每个小矩形画上对角线,然后把所有交叉点$( x , y )$染色:如果$x$是整数,染X颜色.如果$x$不是整数但$y$是整数,染Y颜色.如果都不是整数,染Z颜色.由Sperner引理,三顶点被染不同颜色的三角形有奇数个(简单来说就是,你考虑大矩阵的左侧两个点都是X颜色,右侧一个是Y一个是Z,并且在最下面这条边(两个端点分别被染成了X颜色和Y颜色)上面只可能出现X和Y两种颜色,由于这两种颜色交替出现,那么连接不同颜色的边就会有奇数个,同理对于全局来说,三条边上连接不同颜色的边总共奇数个,内部的每一条边会在两个三角形中被各算一次,因此三个顶点染成不同颜色的三角形应该有奇数个),但由题目条件这种三角形不存在(如果一个点被染成了X颜色,那么上面的点如果存在也该被染成了X颜色,Y颜色同理,俩总会矛盾一个),矛盾.

扫描线证明:设大矩形为$[ 0 , a ] \times [ 0 , b ]$,并假设$b$不是整数.把所有小矩形的下边界去掉,然后令$f ( t )$为所有上边界$y$坐标不是整数,并且与直线$y = t$相交的小矩形的$x$方向边长之和.那么$f ( 0 ) = 0$,而且当$f ( t )$变化的时候,它一定会变成另一个整数(原因在于一个小矩阵(假设已加入扫描线)上方的矩阵,如果想要退出扫描线,则必然横向长度是整数.同理对于一个没有加入扫描线的小矩阵上方的矩阵,如果想要加入扫描线,也需要横向长度是整数).所以$f ( b )$是整数.而因为$b$不是整数,$f ( b )$就是最靠上的所有小矩形的宽之和,等于$a$,所以$a$是整数.