第一届全球数学竞赛阿里巴巴数学竞赛预选赛试题与答案

1第一题A.「双十一」期间，一家电商店铺A有满60返5块的优惠券，可叠加使用（比如，买120块的东西，用两张优惠券，只需付120-5*2=110块）。此外，电商平台全场提供满299减60的优惠券（可凑单），每单限用一张，可与店铺的优惠券叠加使用（比如，原价299块的一单，最终价格是299-5*4-60=219）。原价不满299则不能减去全场折扣60，不足299时，用户可以在别家商店凑单。请问：小明打算在这家店铺买一款250块的耳机和600块的音箱，怎么买最划算？B.现在您开了一家电商店铺，卖与A店同款的耳机和音箱，标价相同，您 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 提供满99返x的优惠券，x为大于0，小于99的整数，与A店不同的是，您的优惠券每单限用一张（比如，买250块需付250-x块，而不是250-2x块）。双11期间，电商平台全场满299减60依然适用。请问：x至少等于多少时，小明在您的店铺买耳机和音箱其中一种会更便宜（至在下面的所有小题中，不考虑退货得满分。组委会会选择前300名进入决赛。第一届阿里巴巴全球数学竞赛试题与答案预选赛具体形式是应用题&建模题&数学基础题，共三题，每题三问，需要提供解题步骤。第一题30分，第二题40分，第三题30分，全部正确解决问题2少1元）？又请问：x至少等于多少时，小明在您的店铺既买耳机又买音箱总和会更便宜（至少1元）？C.建模题。对比单卖和捆绑销售下的利润期望。假设耳机（产品1）和音箱（产品2）的单件销售的单位成本分别是c1和c2（包含生产、存储、运输、促销等所有成本）。一个访问店铺的客户对两件产品的心理价值分别是均匀分布在[0，u1]，[0，u2]的区间上随机变量S1和S2。假设S1和S2相互独立。本题有三小问。1、如何分别设定产品价格p1和p2，以最大化每个到访客户带来的利润期望。这里假设c1<u1；当且仅当p1<=S1时，客户会购买一件商品1；用户不买的话不计损失。对产品2做类似假设。请以公式形式给出最优价格p1*和p2*以及对应的最大利润期望r1*和r2*。2、现在假设产品1和2捆绑销售，成本是c12=t（c1+c2）。因为节省了包装和运输成本，假设0<t<1。其余的条件不变。请以公式形式给出捆绑下的最优价p12*。3、单卖和捆绑销售，哪个利润更优，还是不一定？为什么？3第二题a.附图中有一个无向图，其中圈内数字代 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 一个地点，边e上的数字代表长度Le（双向相同）。一位外卖小哥在起点A，要去3个商家（B1，B2，B3）取餐，送到3个对应的地方（C1，C2，C3），即B1至C1，B2至C2，B3至C3。小哥的电动动力车的箱子同时最多装下2份外卖。请问：小哥该怎么走最短路径？这个最短路径的长度是多少，这里A是出发点，最后一餐（不限次序）送达地为终点。为了简化问题，假设商家已经准备好了外卖，小哥取餐送餐不用等。又假设每份外卖重量大小一样。b.此题与上图无关，而是考虑一个一般的图，图中有很多点和边。外卖小哥刚刚取了一份外卖，计划通过图上的边e1、e2...em送给目的地，途中经过每条边e的时候，以概率Pe[0,1]会收到送至相同地点的另一单外卖。（一条边上收到另4两单及以上的概率小，暂忽略不计）。假设对应边e1、e2...em的概率为P1、P2...Pm。请问：送一次外卖，小哥平均能收到几个送去相同地址的新单（不考虑电动车的箱子容量）？小哥收到至少一个区相同地址的新单的概率是多少？c.此题延续上题，但不再固定路径，而是对路线进行优化。假设小哥每送一单外卖有固定收益r，但是总路径长度l（途中经过的每边e的长度le之和）是成本。总收益是r-l。（为了简化，这里设成本系数为L）。现在小哥刚刚出发，车上只有一份外卖，箱子最大容量仍设为两份外卖，请问怎么走才能最大化收益？（提示：这里不但要考虑路径长短，还要考虑可能收到送至相同地点的另一单外卖而带来的无额外成本的收益r。假设0<=Pc<=min{le/r，1}）。第三题a.马教授的领域内有n个不同但是等价的逻辑陈述，A1，A2，...，An，现在需要证明它们是等价的。每个学期，马教授选两个不同的陈述Ai和Aj，以「Ai->Aj」的证明作为研究课题，指导一位本科生完成。假设每个学期只完成一个证明。要注意的是，在「Ai->Aj」和「Aj->Ak」被证明之后，「Ai->Ak」也已经被自动的证明了，因此不能再作为一个新的课题让学生去完成。总之，如果一个课题是之前若干学生已经完成课题的直接推论，则不能作为新课题发给另一个学生。随着越来越多的推出关系被证明，剩下可选择的课题也越来越少。请问，马教授可以最多依次指导多少个学生呢？为什么？5b.H是一个nxn的方阵，其第i行第j列的元素是hij，所有hij的取值集合为{1，-1}，并且H的任意不同的两行看作向量是相互垂直的（即，他们的 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 内积为0）。假设H有一个axb的子矩阵（1<=a,b<=n），子矩阵内的元素均为1。请证明a，b<=n。c.G是一个群。e是该群的单位元。定义G的一个子集：F={h属于G|存在自然数m>=1，使得hm=e}。假设集合F内的元素是有限多个的。证明：存在一个自然数n>=1使得对所有g属于G和h属于F，我们都有：以上就是全部预选赛试题。6答案：第一题答案A.709元人民币。为了得到这个答案，我们必须要使用其它店铺的优惠券。如果所有的优惠券都来自店铺A，那么付款金额可以减少到705，但在实际中，这个是行不通的。下面是如何得到709人民币的具体步骤：下面我们来比较耳机和音箱一起买与耳机和音箱分开买这两种购买 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，其中，分开购买可以获得更小的支付金额，也就是709元。在同一个订单中购买耳机和音箱：耳机250元，加上音箱的600元也就是850元，由于在店铺A每满60可以使用一张5元优惠券，60*14=840，因此可以在店铺A使用14张优惠券。此外，电商平台全场提供的满299减60的优惠券也可以使用。于是，在同一个订单中购买耳机和音箱总共需要花费的金额为：850-14*5-60=720元耳机和音箱分两个订单中购买：这种方案最终的花费为709，具体的购买方法如下：7耳机的价格是250元，因此可以凑单一件49元的商品，这样就可以使用4张5元优惠券，以及一张满299减60的优惠券。算下来需要的花费为250+49-4*5-60=219元。音箱的价格是600元，可以使用10张满60减5元的优惠券和1张满299减60元的优惠券。于是需要花费的金额为600-60-10*5=490元。因此，耳机和音箱分别购买需要的总花费为219+490=709元。综上所述，最小花费是709元，采用的方案是耳机和音箱分两单购买，并且耳机那个订单要凑单一件49元的商品。B.问题1答案为：如果使用其它店铺的优惠券，那么x为21；如果只使用店铺A的优惠券，那么x为25。问题2答案为：如果使用其它店铺的优惠券，那么x为36；如果使用店铺A的优惠券，那么x为38。具体步骤为：问题1：为了在你的店铺里面买一副耳机，某个人需要支付的钱数为250-x+49（凑单品价格）-60（平台提供的满299减60优惠券）=（239-x）元。对于音箱，我们也用同样的方法计算，得到的这个人需要支付的金额为（540-x）元。为了减少你的店铺在耳机上的花费，x必须满足的条件为239-x<=219，或者8x>=21；为了让你的店铺减少在音箱上的花费，x必须满足540-x<=490-1，或者x>=51。当x为21时，我们可以保证购买耳机是便宜的，但是此时，音箱并不是最便宜的。问题2：如果在你的店铺里面买耳机和音箱，那么分两单分别购买耳机和音箱更划算，因为这样可以获得的总折扣金额为2x。这两个订单的金额分别为（239-x）和（540-x）。它们的总金额肯定比709元要小，那么第二个问题的答案是什么？在这里，x满足的条件为（239-x）+（540-x）<=709-1，或者x>=35.5。因为x必须是整数，所以我们求得这个问题的答案为x=36。C.题目1答案：最优价格为，期望利润为，i=1，2。在i为1或者2的时候，步骤都是一样的。我们用R表示利润这个变量，它随着S的变化而变化。公式为：同样的，我们也可以算出期望利润作为产品的利润，（p-c），购买的可能性为(u-p)/u。函数是一个凹二次曲线函数，因此它的极大值点p*如果在[0，9u]这个区间取得，则满足条件，此时，p*=(u+c)/2，如果c<=u，那么在该点处函数取得最大值。否则，在p*=u处取得最大值。当p*=(u+c)/2时，我们可以得到。题目2答案：价格的最大值为：注意到是关于的分段函数，分成了三段，我们可以算出每个邻域内的边界点。同样我们注意到，计算结果并不是唯一的，学生可以画出函数的曲线图，根据这个曲线图来找出正确答案。不管用什么方法，我们需要三步来计算出。步骤1：定义变量，计算的分布并记为，这个分布并不是均匀分布。步骤2：计算期望利润，为10对于，当时，有。步骤3：对于每个区间来说，最大值就是期望利润，也就是说，必须要找到在每个区间的最大值。当的取值区间为[0，u1]时，的倒数为画出函数的曲线或者检查它的二阶导数，可以很容易地看出上面的的极大值。从，可以得到，在这种情况下，是期望利润的最大值。采用相同的步骤，我们可以求出在另外两种情况下的值和它对应的的值。题目3答案：不一定，没有哪一种策略比其余的策略好。可以使用两个例子来证明这一点，第一个策略采用的方法比第二个好，第二个策略采用的方式比第一个好。有很多这样的例子，我们就不具体举例了。11第二题答案题目a答案：最短的路径长度是16。获得这个数值的方法是采用下面的顺序进行送餐：A->B2->C2->B1->B3->C3->C1具体来说，有两种送餐路线可以使路径长度为16，它们有轻微的不同，即：路线1：路线2：这两条路线都可以经过所有的取餐点。罗列出所有的路线并计算他们的路径长度是一件非常繁琐的工作，然而，在这个题目里面我们不需要这样做。因为这个图是一个平面图，并且路线的方向和目的地的距离总是90度。这就意味着，任意两个点之间的最短路径都是很容易求得的。要手动计算出这个问题的答案，首先可以大致估算一下{B1,C1,B2,C2,B3,C3}的顺序并计算出路径长度。实际上，有很多排序方式可以让路径的长度为17，如果12你算出的值比这个稍微高一点儿，那么就是一个好的排列顺序。这个距离是最短距离的上限。然后罗列{B1,C1,B2,C2,B3,C3}的顺序并计算出路径长度，一旦长度达到17，就排除这个路线。当你找到一条总长度为16的路线时，上限改为16，这个策略叫做分支界限法。题目b答案：对于问题1来说，P1+P2+...+Pm。我们让的取值为0或者1，边界为，对于i=1,2,...,m来说，我们可以通过下面的方法来计算答案：对于问题2来说，是。在这里，（1-Pi）是在ei处没有外卖的概率，并且我们可以根据概率论知识知道，是整个路线上都没有外卖的概率，因此，1减去这个概率值是最少可以在这条路线上取到一个外卖的概率。同时，可以使用条件概率来得到的递归公式为，在e1之后最少可以获得一单新外卖的概率为，也就是，通过不断的递归，可以得到最终的式子为，这个递归也是一个正确答案。上面的两个答案都可以和下面这个式子等同：13题目c答案：假设我们不考虑一般性的情况，现在有T个节点，并且T是目的节点。首先，对于每个节点i，找到去T的最短路线和对应的路线长度（如果具有相同长度的不同路线之前有相互关系，一定要解除他们之间的关系）。对于i=T，我们有。接下来，使用，在每个节点计算最优预期回报，使用下面给出的极大值公式（3）来计算。对于，假设是i的相邻节点，并且在该点处能取得极大值（同样地，如果节点之间有关联，打破这个关联）。外卖小哥的最优路线被下面的每个点决定了：在节点i的时候，如果外卖小哥还没有拿到额外的一单，那么移动到；如果外卖小哥拿到了额外的一单，那么他车上的外卖箱子已经装满了，因此只需要走从i到T的最短路线。注意到上面的路线并不是事先计划好的，而是由外卖小哥自己决定的。也就是说，这是一个策略问题。这种方式比事先计划好路线要好，因为是否会有额外的外卖单是未知的，而这会影响路线、影响到T的距离。当外卖小哥在节点i并且取到了第二个外卖的时候，外卖小哥决定去哪里采用的方法是去这个地方获得的收益的期望值，这个收益值又被获取外卖的可能性和到T节点的距离所影响。14定义在取到额外的外卖前，在节点i的最优预期收益为。当i=T时，我们让，这个是固定的收益。假设我们计算了i的相邻节点。在节点i的时候，如果我们要移动到节点j，那么预期收益将会变成：，如果在i、j两点之间出现外卖；，如果在i、j两点之间不出现外卖。设i、j之间的边长度为，则有：（3）这就是众所周知的贝尔曼方程。根据和式子（3），我们可以计算出，你可以使用动态规划或者更具体的图，贝尔曼·福特算法或者迪杰特斯拉算法（请看下面的说明）。它们都从开始，并且决定了这个集合里面的元素。对于或者，必须要避免「正面奖励」的存在，这可以避免外卖小哥为了获得额外的报酬而不停地在这些路线走来走去，直到取到额外的一单外卖这种不现实的情况。15我们注意到，在实际中，学生们更倾向于使用迪杰特斯拉算法。这种算法要求边长必须是非负的值。因此，如果一个人使用这个算法去计算，必须要满足这个条件。对于我们的这个问题，这里必须要满足：（4）在满足假设条件的条件下，这种情况确实存在。为什么呢？既然最坏的情况也就是外卖小哥沿着最短路径到达T节点处（而不是选择使收益最大化的节点），我们可以得到：于是可以得到第二个不等式：第一个不等式的假设条件是不大于，我们可以结合上面的不等式得到式子（4）。第三题答案题目a答案：我们首先指导0.5(n+2)(n-1)个学生，下面，我们将证明这个答案。解释：首先，(n-1)个学生证明A1->Ai，其中i为2到n的整数；然后，(n-2)个学生证明A2->Ai，其中i为3到n的整数。一直这样做，直到最后一个学16生证明An-1->An。然后，(n-1)个学生证明An->An-1，An-1->An-1，...，A2->A1。它们的总数为：让。最优性证明：假设图G=（N，E）的节点为N={1,2，...，n}，其有向边为E={（i，j）|Ai->Aj已经被证明了}。完成一个课题，意味着给E加上一条边。假设E':={（i,j)|其中，Ai->Aj和Aj->Ai在前面已经被证明了}是对偶边，是集合E的子集，子图G’=（N，E'）最多有2(n-1)个有向边；否则，必然存在一些对偶边包含无效课题。G最多有n(n-2)/2对节点，去掉对偶边上的节点，正如前面所证明的，此时最多有2(n-1)个有向边，因此最多有(n-1)对有向边，也就是说，有n(n-1)/2-(n-1)=(n-2)(n-1)/2对节点之间是单向边或者是没有边的。因此，最多有(n-2)(n-1)/2个单向边。因此，加上单向边和对偶边的最大数得：题目b答案：对于任何a行b列的矩阵A，都有：（5）17设||A||为矩阵的谱范数，为矩阵的Frobenius范数。在我们的题目中，既然H是n行n列的正交矩阵，则有。对于H的任何子矩阵A来说，都有。当子矩阵A为a行b列矩阵，且其元素全部为1时，则有和rank(A)=1，于是可以得到：题目c答案：证明：取。设满足，让。由于：由F的定义，我们可以得到：因此，可以得到，。对于来说也是一样的。F是有限的，对于每个h，存在，使得。取，对任何属于F的h，n是的倍数，也就是说，。因此，从，我们可以得到：进而可以得到：