ACEE数学建模作业+小测提示(2024版)#

考虑到很多同学这门课对于一些作业可能需要一些提示，这里我为大家提供一些视角和参考，注意内容仅供参考，请勿抄袭～

周期一 雪灾浙大作业#

(之前写的有点谜语人，考虑改清楚点)

T1:排序问题#

标签

keywords:分类讨论，三角不等式

• 问1:略
• 问2:
  • 法一：分类讨论正偏态和负偏态情况，强行展开绝对值
  • 法二：三角不等式硬上，利用绝对值的差和差的绝对值，以及绝对值的和和和的绝对值之间的关系解题。可以找一个中转点，$A\leqslant 2B\Leftrightarrow A-B\leqslant A$
• 问3:
  • 中位数$\mu$是整数无限制下的最优解，$\sigma'$是排列意义下对$\mu$的逼近，$\sigma^*$是排列限制下最优解
  • 在这个意义上我们可以利用三角不等式，通过建立中间点来实现拆项
  • 对于$\beta$我们没有更好的性质，考虑用问2来搭桥

T2:赛程计分问题#

标签

keywords:递推，向量表示

第二题可能需要提示的是第四问，很容易想到向前递推，这里需要考虑清楚的是第一步的边贡献次数是多少。

tip

在给出答案前，想一想你真的能化简吗?

具体过程如下：

周期一 慕课作业#

单循环赛break下限证明#

pattern互不相同，只有两种能不出break

砍竹子问题#

TIP

竹子最高高度存在上界，其对偶表述是总高度增加量存在下界

反证法，每个时刻总量增加总是H-当前砍伐高，你总能拉上去

小测一 线性规划转化问题#

TIP

本题的核心是引导大家利用01变量去刻画常规的多种关系，具体而言，要习惯于用对指标枚举去表示某些特定的数值/数值集合，也就是从是多少到有没有的转化。

可以借鉴的是这本书

NOTE

Boolean	Linear
$z= x\ \mathrm{OR}\ y$	$x\leq z,\ y\leq z,\ z\leq x+y$
$z= x\ \mathrm{AND}\ y$	$x\geq z,\ y\geq z,\ z+1\geq x+y$
$z= \mathrm{NOT}\ x$	$z=1-x$
$x\implies y$	$x\leq y$

有$n$个小区需要服务，$m$处可以开设服务，开设服务费费用为$f_i$，提供服务的费用为$c_{i,j}$，每个最小化费用 不相容约束，某些小区不能同时由某一个服务点提供服务，记为:$\{a_k,b_k\}(k=1,2,\cdots,s)$ 双指派约束，每个小区有两个服务点提供服务，且某些小区对有一个公共服务点:$\{c_w,d_w\}(w=1,2,\cdots,t)$

$x_i=[i$有服务$]$

$y_{ij}=[i$有点且在$j$小区服务$]$

$z_{i,t}=[i$为$c_t,d_t$的公共点$]$

则显然可以直接写出

老师给的答案如下，实际上并不优秀，因为约束数反而变多了

周期二 慕课作业#

T1 吉祥三宝#

在杭州迎接2022年第19届亚洲运动会时，n名同学正在老师的带领下与亚运会吉祥物“江南忆”做游戏。游戏开始前，同学可以商定在游戏中采取的策略，但游戏进行过程中，同学之间不能互相交流。游戏开始时，老师在每位同学的背后贴上印有三个吉祥物“琮琮”、“宸宸”和“莲莲”之一的图案，不同同学背后的图案可以不同。每个同学不能看到自己背后的图案，但能看到除他自己外所有其他同学的图案。

（1）现老师要求所有同学分站为3列。每列所有同学背后的图案均完全相同时，视为 “成功”。试给出一种策略，使成功的可能性尽可能大；

（2）现老师要求每位同学同时在纸上画出自己背后的图案。一位同学所画的图案与自己背后的图案相同时视为该同学“成功”。试给出一种策略，使该策略能确保成功的同学数量尽可能多。

为了方便说明，我们将背后贴上印有三个吉祥物“琮琮”、“宸宸”和“莲莲”的图案的同学分别符号化为A，B，C

(1)

【法一】

下面我们将说明存在策略，成功的可能性为$1$

具体而言

我们设每个同学看到的A,B,C个数为$a,b,c$

则显然$a+b+c=n-1$，且具体而言，设所有同学中A,B,C个数为$a_0,b_0,c_0$

则$a=a_0-[\mathtt{self.c=A}],b=b_0-[\mathtt{self.c=B}],c=c_0-[\mathtt{self.c=C}]$

我们构造排队方法

假设$(a-b)\mod 3\equiv 0$，其归到$1$队

假设$(a-b)\mod 3\equiv 1$，其归到$2$队

假设$(a-b)\mod 3\equiv 2$，其归到$3$队

在这种策略下，

• 本身是$\mathtt A$ : $(a-b)\equiv (a_0-b_0-1)\mod 3$
• 本身是$\mathtt B$ : $(a-b)\equiv (a_0-b_0+1)\mod 3$
• 本身是$\mathtt C$ : $(a-b)\equiv (a_0-b_0)\mod 3$

容易发现不同属性（即背后吉祥物不同）会有不同的计算结果，因此会被分到三个队列中

【法二】

首先，我们为每个人分配一个序号$i$，我们设$h_i$表示第$i$个人的颜色译码，设为

则我们将$i$分到$(\sum _{j\neq i}h_j\mod 3)+1$队列，则为一个合法的安排

证明和上面基本相同，这里不再赘述

hint

$-1\equiv 2\mod 3$

(2)

延续(1)【法二】的定义，我们用0,1,2表示A,

设$n=3k+r(0 \leqslant m <3)$,即$k=\lfloor\frac{n}{3}\rfloor$

考虑如下策略

• $1\leqslant i\leqslant k$，猜测图案为$-\sum \limits _{j\neq i} h_j\pmod 3$
• $k+1\leqslant i\leqslant 2k+[r\geqslant 1]$，猜测图案为$1-\sum \limits _{j\neq i} h_j\pmod 3$
• $2k+1+[r\geqslant 1]\leqslant i\leqslant 3k+[r\geqslant 1]+[r\geqslant 2]$，猜测图案为$2-\sum \limits _{j\neq i} h_j\pmod 3$

容易证明

前$k$名同学，中间$k+[r\geqslant 1]$名同学，后面$k+[r\geqslant 2]$名同学 这三组同学，至少有完整的一组选择正确（证明基于分类讨论反证即可）

因此能保证至少$k=\lfloor\frac{n}{3}\rfloor$个成功

T2 假币识别问题#

(1)

某种硬币单枚质量为$W$克。现有$N$堆该种硬币，依次标记为$1，2,...,N$。其中可能有若干堆，每堆均是伪币。所有伪币质量均相同，且不为$W$。伪币所在堆的指标集记为$I$。为求出$I$，现用一可精确测得质量的电子秤称量两次。第一次从每堆硬币中各取1枚，称得总质量为$M_{1}$克，第二次从第i堆硬币中取$p^i$枚，i=1,2,…,N,称得总质量为$M_2$克，这里p为正整数(假设每堆硬币数量足够多)。 (1)试给出$M_1,M_2$和W的某个函数，其值仅与I和p有关，而与伪币的质量无关； (2)为能用上述方法通过两次称量求出指标集I，p应满足什么条件？试给出某个满足条件的p 值；并说明若取$\mathfrak{p}=2$,可能无法用上述方法通过两次称量求出I。

有

因此我们

可以构造函数

更好理解的形式是

我们已经给出了符合要求的函数

(2)

首先我们给出能够通过两次称量求出$I$的量化条件

对于

若对给定的$p$，$\forall I_1\neq I_2,G_p(I_1)\neq G_p(I_2)$

则我们称可以还原$I$

下面取$p=N+1$（实际上$p$可以任意取$>N$的正整数），证明还原性存在

若存在$I_1\neq I_2,G_p(I_1)= G_p(I_2)$

则

即

容易发现由于$p=N+1>\max\{|I_2|,|I_1|\}$,因此等式两侧是一个$p=N+1$进制数的不同位权表达，这与位权展开的唯一性违背，因此矛盾。

故$\forall I_1\neq I_2,G_p(I_1)\neq G_p(I_2)$

$p=N+1$为一个可行的取法

对于$p=2$

我们可以构造一些$N$,和对应的$I_1,I_2$使得可还原性被破坏

反例如下

即在$N=7$时存在两个指标集合我们函数获取的值一样，无法区分。

因此$2$不一定能称出来

周期三 慕课作业#

T1 变形格雷码#

一电灯由n个开关控制。每个开关有“开”、“关”两种状态，但开关当前状态未知。每按一次开关可改变开关的状态，当且仅当所有开关均处在“开”状态时电灯才能开启。

（1）若当前电灯未开启，至多按开关多少次总可开启电灯；

（2）给出n=4时的一种实现方式，并将其推广到n为任意值的情形。

(1)

这里给出一个简单的放缩

设$0,1$分别表示关和开，则$1^n$表示全部开启状态即目标状态

一个不执行冗余操作的方案中，每次翻转状态均可以产生一个没有出现的状态，则至少需要$2^n-1$次能够开启点灯

(2)

一个合法方案的本质是一个格雷码，即生成$n$长度所有的$2^n$个01串的排列，使得两两相邻串间相差一位

其中要求最后一个串为1111…

这里我们可以反过来生成从$0^n=0000...0000$出发的01串序列，使得相邻串相差一位

具体而言

对于$n=3$，我们先生成：

000,001,011,010,110,111,101,100

然后将其01翻转并序列倒转得到

011,010,000,001,101,100,110,111

这样我们就从一个电灯未开启的状态通过$2^3-1=7$步到达了$111$即电灯开启的状态

对于$n=4$是类似的

我们先生成

0000 → 1000 → 1100 →0100 → 0110 → 1110 → 1010 → 0010 → 0011 → 1011 → 1111 → 0111 →0101 → 1101 → 1001 → 0001

最终方案为

1110 → 0110 → 0010 → 1010 → 1000 → 0000 → 0100 → 1100 → 1101 → 0101 → 0001 → 1001 → 1011 → 0011 → 0111 → 1111

假设$S_k$为长度为$k$的字符串的一种方案，则$S_k=(\mathrm{rev}(S^R_{k-1})||0)+(S^R_{k-1}||1)$

即可以通过将$S_{k-1}$的每个字符串倒置，然后复制一遍在后面，对前$2^{k-1}$个串做序列反转，并填0，后半字符串填1即可得到$S_k$

换句话说，本题的答案序列是倒置且01翻转的标准格雷码

存在通用的数学表示 ，长度为$k$的串的第$i$个串为$S_k(i)=2^{k}-\left((2^{k}-1-i)\oplus \lfloor\frac{2^{k}-1-i}{2}\rfloor\right)$

这个结果看似复杂，也的确比较复杂（

T2#

现有六堆硬币，每堆32枚。硬币有真伪两种，真币每枚重100克，伪币每枚重99克。同一堆硬币要么全是真币，要么全是伪币。现需用可显示重量的电子秤称重一次判断出每堆硬币的真假，试给出称量方案，并说明其正确性。若每堆仅有24枚，是否仍存在可行的称量方案？

方案如下，对于第$i$堆，我们取$2^{i-1}$枚$(1\leqslant i\leqslant 6)$

则我们取的集合为$S=\{1,2,4,8,16,32\}$

任意两个子集的和不同，因此可以根据取出的硬币的质量和$63\times 100$作差即可获取伪币所在的堆编号

而假设只有24枚，我们可以取$S=\{11, 17, 20, 22, 23, 24\}$,，容易发现中任意含 $i + 1$ 个元素的子集元素之和大于含 $i$ 个元素的子集之和，仍可以通过与标准值求差确定子集，因此存在称量方案。

周期四 慕课作业#

T1#

基尼系数（Gini Index）是衡量经济不平等的一个主要指标。在这个问题中，我们考虑家庭收入 $x$ 服从离散分布，其分布律为 $P(X=y_i) = \frac{1}{n}$，其中 $i = 1, \ldots, m$，并且 $a \leq y_1 \leq y_2 \leq \ldots \leq y_n \leq b$。

定义 $L_i$ 为收入不超过 $y_i$ 的家庭的总收入占整体家庭总收入的比例。约定 $L_0 = 0$，在 Oxy 平面上连接点 $\left(\frac{i}{n}, L_i\right)$，$i = 0, 1, \ldots, n$ 的分段线性函数 $L$ 称为洛伦兹曲线（Lorenz Curve）。洛伦兹曲线 $L$ 与线段 $y = x, 0 \leq x \leq 1$ 围成的区域记为 $S$。洛伦兹曲线 $L$ 与 x 轴和线段 $x = 1, 0 \leq y \leq 1$ 围成的区域记为 $B$。

基尼系数 $G$ 定义为区域 $S$ 的面积 $A$ 的两倍。我们需要给出 $G$ 的表达式，并简要说明 $G$ 如何反映家庭收入差异程度。

首先，根据定义，我们有：

区域 $B$ 的面积 $S_B$ 可以表示为：

进一步简化得到：

因此，基尼系数 $G$ 可以表示为：

由于 $y_1 \leq y_2 \leq \ldots \leq y_n$，故 $L_i \leq \frac{i}{n}$，即洛伦兹曲线 $L$ 总在直线 $y = x$ 的下方。基尼系数 $G$ 越大，说明洛伦兹曲线在横坐标较小时增长较慢，在横坐标较大时增长迅速，这表明少部分人占有收入比例很高，家庭收入差异大。

T2#

小剧场一排有 $n$ 个座位。由于各排之间空隙较小，如果某座位已有人入座，则入座者必须起身才能让后来者通过该座位。若一与会者进入会场时该排有若干个座位可供其选择，则他以相等的概率选择其中一个座位就坐。

1. 若该排座位只有左侧一个入口，所有与会者一旦就坐就不愿起身让后来者通过。记 $E_n$ 为该排最终入座人数的期望，试写出 $E_n$ 满足的递推关系，并求 $E_n$。

2. 若该排座位在左右两侧均有入口，所有与会者以 $p$ 的概率起身让后来者通过，以 $1-p$ 的概率不让后来者通过。记 $F_n$ 为该排最终入座人数的期望，试写出 $F_n$ 满足的递推关系。

若进入会场时有 $n$ 个座位可供选择，他选择每个座位的概率均为 $\frac{1}{n}$。若他选择了第 $i$ 个座位，下一个进入会场者只有其左侧的 $i-1$ 个座位可供选择。因此，可得递推关系：

$E_n = 1 + \frac{1}{n} \sum_{i=1}^n E_{i-1}$

由上式可得：

$n E_n = n + \sum_{i=1}^n E_{i-1}$

$(n+1) E_{n+1} = n+1 + \sum_{i=1}^{n+1} E_{i-1}$

两式相减可得 $(n+1) E_{n+1} - n E_n = 1 + E_n$，即：

$E_{n+1} - E_n = \frac{1}{n+1}$

由 $E_1 = 1$ 可得：

$E_n = \sum_{i=1}^n \frac{1}{i}$

记 $G_n$ 为只有一侧有入口时最终入座人数的期望，则 $G_n$ 满足递推关系：

$G_n = 1 + p G_{n-1} + (1-p) \cdot \frac{1}{n} \sum_{i=1}^n G_{i-1}.$

$F_n$ 满足递推关系：

$F_n = 1 + p F_{n-1} + (1-p) \frac{1}{n} \sum_{i=1}^n (G_{i-1} + G_{n-i}).$

周期四 概率问题#