2001 字
10 分钟
ACEE数学建模作业+小测提示(2024版)

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

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

周期一 雪灾浙大作业#

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

T1:排序问题#

标签

keywords:分类讨论三角不等式

  • 问1:略
  • 问2:
    • 法一:分类讨论正偏态和负偏态情况,强行展开绝对值
    • 法二:三角不等式硬上,利用绝对值的差和差的绝对值,以及绝对值的和和和的绝对值之间的关系解题。可以找一个中转点,A2BABAA\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
BooleanLinear
z=x OR yz= x\ \mathrm{OR}\ yxz, yz, zx+yx\leq z,\ y\leq z,\ z\leq x+y
z=x AND yz= x\ \mathrm{AND}\ yxz, yz, z+1x+yx\geq z,\ y\geq z,\ z+1\geq x+y
z=NOT xz= \mathrm{NOT}\ xz=1xz=1-x
x    yx\implies yxyx\leq y

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

xi=[ix_i=[i有服务]]

yij=[iy_{ij}=[i有点且在jj小区服务]]

zi,t=[iz_{i,t}=[ict,dtc_t,d_t的公共点]]

则显然可以直接写出

mini=1mfixi+i=1mj=1ncijyij\min \sum _{i=1}^m f_ix_i+\sum _{i=1}^m\sum _{j=1}^n c_{ij}y_{ij} s.t.xi{0,1},yij{0,1},zi,w{0,1}yijxii=1myij1(=2)yiak+yibk1ziwyi,cwziwyi,dwziw+1yicw+yidwi=1mziw1\begin{align}s.t. x_i\in \{0,1\},y_{ij}&\in \{0,1\},z_{i,w}\in \{0,1\}\\y_{ij}&\leqslant x_i\\\sum _{i=1}^my_{ij} &\geqslant 1(=2)\\y_{ia_k}+y_{ib_k}&\leqslant 1\\z_{iw}&\leqslant y_{i,c_w}\\z_{iw}&\leqslant y_{i,d_w}\\z_{iw}+1&\geqslant y_{ic_w}+y_{id_w}\\\sum _{i=1}^m z_{iw}&\geqslant 1&\end{align}

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

s.t.xi{0,1},yij{0,1}yijxii=1myij1(=2)yiak+yibk1xi1cw+xi2cwxi1dw+xi2dw1i=1mziw1\begin{align}s.t. x_i\in \{0,1\}&,y_{ij}\in \{0,1\}\\y_{ij}&\leqslant x_i\\\sum _{i=1}^my_{ij} &\geqslant 1(=2)\\y_{ia_k}+y_{ib_k}&\leqslant 1\\x_{i_1c_w}+x_{i_2c_w}&\geqslant x_{i_1d_w}+x_{i_2d_w}-1\\\sum _{i=1}^m z_{iw}&\geqslant 1&\end{align}

周期二 慕课作业#

T1 吉祥三宝#

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

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

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

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

(1)

【法一】

下面我们将说明存在策略,成功的可能性为11

具体而言

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

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

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

我们构造排队方法

假设(ab)mod30(a-b)\mod 3\equiv 0,其归到11

假设(ab)mod31(a-b)\mod 3\equiv 1,其归到22

假设(ab)mod32(a-b)\mod 3\equiv 2,其归到33

在这种策略下,

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

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

【法二】

首先,我们为每个人分配一个序号ii,我们设hih_i表示第ii个人的颜色译码,设为

hi={0selfi.c=A1selfi.c=B2selfi.c=Ch_i=\begin{cases}0&\mathtt{self_i.c=A}\\1&\mathtt{self_i.c=B}\\2&\mathtt{self_i.c=C}\end{cases}

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

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

hint

12mod3-1\equiv 2\mod 3

(2)

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

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

考虑如下策略

  • 1ik1\leqslant i\leqslant k,猜测图案为jihj(mod3)-\sum \limits _{j\neq i} h_j\pmod 3
  • k+1i2k+[r1]k+1\leqslant i\leqslant 2k+[r\geqslant 1],猜测图案为1jihj(mod3)1-\sum \limits _{j\neq i} h_j\pmod 3
  • 2k+1+[r1]i3k+[r1]+[r2]2k+1+[r\geqslant 1]\leqslant i\leqslant 3k+[r\geqslant 1]+[r\geqslant 2],猜测图案为2jihj(mod3)2-\sum \limits _{j\neq i} h_j\pmod 3

容易证明

kk名同学,中间k+[r1]k+[r\geqslant 1]名同学,后面k+[r2]k+[r\geqslant 2]名同学 这三组同学,至少有完整的一组选择正确(证明基于分类讨论反证即可)

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

T2 假币识别问题#

(1)

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

M1=(NI)W+IWM2=WiIpi+WiIpiM_1=(N-|I|)W+|I|W'\\M_2=W\sum _{i\notin I}p^i+W'\sum _{i\in I}p^i\\

(M1NW)+IiIpi(p(1pN)1pWM2)(M_1-NW)+\frac{|I|}{\sum _{i\in I}p^i}\left(\frac{p(1-p^N)}{1-p}W-M_2\right)

因此我们

可以构造函数

F(M1,M2,W,N,p)=(M1NW)(M2p(1pN)1pW)=IiIpiF(M_1,M_2,W,N,p)=\frac{(M_1-NW)}{\left(M_2-\frac{p(1-p^N)}{1-p}W\right)}=\frac{|I|}{\sum _{i\in I }p^i}

更好理解的形式是

F(M1,M2,W,N,p)=M2(p(1pN)1pW)(M1NW)=iIpiIF(M_1,M_2,W,N,p)=\frac{M_2-\left(\frac{p(1-p^N)}{1-p}W\right)}{(M_1-NW)}=\frac{\sum _{i\in I }p^i}{|I|}

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

(2)

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

对于

F(M1,M2,W,N,p)=iIpiI=Gp(I)F(M_1,M_2,W,N,p)=\frac{\sum _{i\in I }p^i}{|I|}=G_p(I)

若对给定的ppI1I2,Gp(I1)Gp(I2)\forall I_1\neq I_2,G_p(I_1)\neq G_p(I_2)

则我们称可以还原II

下面取p=N+1p=N+1(实际上pp可以任意取>N>N的正整数),证明还原性存在

若存在I1I2,Gp(I1)=Gp(I2)I_1\neq I_2,G_p(I_1)= G_p(I_2)

iI1piI1=iI2piI2\frac{\sum \limits_{i\in I_1}p^i}{|I_1|}=\frac{\sum \limits_{i\in I_2}p^i}{|I_2|}

I2iI1pi=I1iI2pi|I_2|\sum \limits_{i\in I_1}p^i =|I_1|\sum _{i\in I_2}p^i

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

I1I2,Gp(I1)Gp(I2)\forall I_1\neq I_2,G_p(I_1)\neq G_p(I_2)

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


对于p=2p=2

我们可以构造一些NN,和对应的I1,I2I_1,I_2使得可还原性被破坏

反例如下

p=2N=7I1={2,23,27}Gp(I1)=46I2={2,22,25,26,27}Gp(I2)=46p=2\\ N=7\\ I_1=\{2,2^3,2^7\}\Rightarrow G_p(I_1)=46\\ I_2=\{2,2^2,2^5,2^6,2^7\}\Rightarrow G_p(I_2)=46

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

因此22不一定能称出来

ACEE数学建模作业+小测提示(2024版)
https://zzw4257.cn/posts/acee-course/math-modeling/acee-homework/
作者
zzw4257
发布于
2024-10-06
许可协议
CC BY-NC-SA 4.0