《2018阿里巴巴全球数学竞赛预选赛赛题及参考答案.pdf》由会员分享，可在线阅读，更多相关《2018阿里巴巴全球数学竞赛预选赛赛题及参考答案.pdf（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、The Alibaba Global Mathematics Competition(Hangzhou 2018)consists of 3 problems.Each consists of 3 questions:a,b,and c.This document includes answers for your reference.It is important to note that thereare multiple answers to each question.If you submitted different answers,you maystill get points.
2、We try to write the answers rather thoroughly.It does not mean youranswers need to be as detailed.This document is neither a rubric nor a grading guide.The authors of these answers are not the graders.(correction 11)Problem 1.a.During the Alibaba 11.11 Shopping Festival,Store A issues“5 RMB off60 RM
3、B”stackablecoupons.“Stackable”means the multiple coupons can be applied to a single order.For example,an order of 120 RMB at list price,can be reduced to 110 RMB by applying two such coupons.Store A is part of T.T issues a“60 RMB off299 RMB”coupon,limited toone per order.This coupon applies to the l
4、ist price and is stackable with any individual storecoupons.For example,to a product listed at 299 RMB in a T store,one pays only 299RMB-(the store discount based on 299 RMB)-60 RMB.If the total list price is slightly below299RMB,customers often adds filler item(s)(such as socks or tissues)from othe
5、r Tstores to reach 299RMB and then apply the coupon.Xiao Ming will buy a 250 RMB pair of headphones and a 600 RMB speaker set from TStore A.Xiao Ming has unlimited access to the two types of coupons described.What is theleast amount that he must pay?Answer:709 RMB.To get this answer,we have used fil
6、ler items from otherstore(s).The answer will be reduced to 705 RMB if there are filler items solelyfrom Store A(but this is less likely to hold in practice.)Below,we explain the stepsto get 709 RBM.Below we compare buying both items in one order and buying them in two separate orders.Thelatter at 70
7、9 is cheaper.Buy the two items in one order:The final cost is250(headphones list price)+600(speaker sets list price)14 5 apply(?250+60060?=14“5-off-60”store coupons)60(shopping cart coupon)=720.Buy the two items separately:The two orders cost 709,which breaks down to the followingtwo orders:The head
8、phone pair costs250 4 5(apply b25060c=4 store coupons)+49(filler items to reach 299 total list price)60(shopping cart coupon)=219.(1)1change log:“50 RMB off299 RMB”is corrected to“60 RMB off299 RMB”1If one forgets to use filler items,s/he will pay 250 20=230,which is 11 more.The speaker set costs600
9、 10 5(apply b60060c=10 store coupons)60(shopping cart coupon)=490.(2)Hence all together 219+490=709 RMB.b.You plan to open your own T store,called“Store B,”selling the same headphones andspeaker set at the same list prices as Store A does.Your store sells only these two models.You plan to issue“x RM
10、B off99 RMB”coupons,limited to one per order,where x is an integergreater than 0 and smaller than 99.(For example,the discount for an order of 250 RMB is xRMB,not 2x RMB).The T“60 RMB off299 RMB”coupon can be applied to purchasesat store B and can be stacked with your“x RMB off99 RMB”coupon.What is
11、the minimal number x such that Xiao Ming can spend at least 1 RMB less on either the250 RMB pair of the headphones or the 600 RMB speakers set in your Store B than in Store A?What is the minimal number x such that Xiao Ming can spend at least 1 RMB less for buyingboth the 250 RMB pair of the headpho
12、nes and the 600 RMB speakers set in your Store B thanin Store A?To clarify,the comparison is between the costs with the coupons applied optimally.Answers:1st question:21 if using filler items from other stores and 25 if usingfiller items from Store A;2nd question:36 for the 2nd question if using fil
13、ler itemsfrom other stores and 38 if using filler items from Store A.Below,we give the stepsassume we use filler items from other stores.The 1st question.To buy a headphone pair in your store,one pays 250 x+49(filler)60(shopping cart coupon)=239 x.Similarly,we get 540 x for the speaker set.For your
14、store to cost less on the headphone pair,x must satisfy 239 x 219(1),or x 21.For your store to cost less on the speaker pair,x must satisfy 540 x 490 1(2),or x 51.When x=21,we ensure the headphone pair to be cheaper,not the speaker set though.The 2nd question.To buy both items in your store,it is ch
15、eaper to buy them in two separateorders since we can apply the coupon to each order to get a total discount of 2x.The part above has the formulas for the two orders:(239x)and(540 x).Their total mustbe cheaper than 709,which is the answer in part 2.That is(239x)+(540 x)709 1,orx 35.5.Since x is an in
16、teger,we set x=36 for this question2.c.Mathematical modeling of product bundling.Suppose that the total costs of Item 1 and Item2 are c1and c2(including production,storage,transportation,promotion,etc.),respectively.When a customer visits the T store,s/he perceives the values of these items at S1and
17、S2,respectively.We suppose that S1and S2are random variables that are independently anduniformly distributed on the intervals 0,u1 and 0,u2,respectively.There are three questions.2Due to different understanding of the Chinese version,both 36 and 51 can be taken as the correct answer,becausethere,one
18、 may understand that one might not have to buy both items in your store or both items in store A.21.What is the value for p1,the price for Item 1,that maximizes the expected profit for eachvisiting customer?Here,assume that a visiting customer will purchase one piece of Item 1if S1 p1,and if so,your
19、 profit is(p1 c1).Please provide a formula.Similarly,what isthe value for p2that maximizes the expected profit for each visiting customer?Answer:optimal price pi=ui+ci2and expected profit ri=(uici)24uifor i=1,2.Since the steps are identical for i=1,2,we drop i for brevity.Let R be the random variabl
20、eof profit,which depends on S.We calculate its expectation:r=ES(R)=ES?(p c)buy?=ES?(p c)pS?=Zu0(p c)ps1uds=(p c)su?s=us=p=(p c)(u p)u.Alternatively,we can obtain the same expected profit directly as the product of profit,(p c),and the probability of buying,upu.The function r(p):=(pc)(up)uis a concav
21、e quadratic function,so its maximum is attainedat the point p such that r0(p)=0 if pis on the interval of its allowed values,0,u.Indeed,r0(p)=0 yields p=u+c2,which is the maximizer if c u(otherwise,p=u,which is a trivial case).With p=u+c2,we get r=r(p)=(uc)24u.2.Assume we are going to sell a bundle
22、item including one unit of Item 1 and one unit of Item2 at price p12.The total cost of this item is t(c1+c2),where 0 t 1.Assume a visitingcustomer will purchase one piece of this bundle if(S1+S2)p12,and if so,your profit isp12 t(c1+c2).Determine the price p12to maximize the expected profit for each
23、visitingcustomer.Please provide a formula.Answer:the price p12that maximizes the expected return isp12=13?c12+pc212+6u1u2?,c12 0,32u1 u214?u1+2u2+2c12?,c12 32u1 u2,u212u113(u1+u2+2c12),c12 u212u1,u1+u2.Note that p12is continuous with respect to c12,including one the boundary points of threeintervals
24、,so one can include each boundary point in either or both of the neighboringintervals.Also note that the calculation is not unique.Students can find the right answer by drawinga picture and using geometry.No matter which approach is used,it takes the following three steps to compute p12.Step 1.Defin
25、e random variable S12:=S1+S2.Compute the distribution of S12,denotedby p12.This is not a uniform distribution.p12(s):=Pr(S=s)=Zu1+u20p1(z y)p2(y)dy=su1u2,s 0,u11u2,s u1,u2u1+u2su1u2,s u2,u1+u2.3Step 2.Compute the expected profit as a function of S12,which isES12?(p12 c12)buy?=?Zu10su1u2+Zu2u11u2+Zu1
26、+u2u2u1+u2 su1u2?(p12 c12)p12s12ds12=(p12 c12)1 p2122u1u2,p12 0,u11 p12u2+u12u2,p12 u1,u2(u1+u2p12)22u1u2,p12 u2,u1+u2.For p126 0,u1+u2,we have ES12?(p12 c12)buy?0 as long as c12 0.Step 3.Over each of the intervals,maximize the expected profit.That is to find the profitmaximizer p12within each of th
27、e intervals.For p12 0,u1,setting the derivative of(p12 c12)(1 p2122u1u2)to 0 yieldsp12=13?c12+qc212+6u1u2?.Draw the curve or check the second derivative,and it is easy to see the above p12is amaximizer.From p12 u1,we get c1232u1 u2,which is the condition under which theabove p12is the maximizer of t
28、he expected profit.Using similar steps,we obtained p12in the other two cases and their corresponding intervalsof c12.3.If you must choose between selling Items 1 and 2 separately and selling them in a bundle,which one do you choose?Is one strategy always better than the other?Why?Answer:Neither stra
29、tegy is always better than the other.To establish this claim,it is sufficient to use a pair of examples,one showing one strategybetter than the other,and the other showing the other way around.There are many suchexamples,so we do not specify one.4Problem 2:a.The attached figure is an undirected grap
30、h.The circled numbers represent the nodes,and thenumbers along the edges are their lengths(symmetrical in both directions).12A3B14B3567B2891011C212C113C31415121122311111131221211An Alibaba Hema Xiansheng carrier starts at point A and will pick up three orders from merchantsB1,B2,B3and deliver them t
31、o three customers C1,C2,C3,respectively.The carrier drives ascooter with a trunk that holds at most two orders at any time.All the orders have equal size.Find the shortest travel route that starts at A and ends at the last delivery.To simplify thisquestion,assume no waiting time during each pickup a
32、nd delivery.Answer:The shortest travel distance is 16,attained by the carrier taking the following stops:A B2 C2 B1 B3 C3 C1.There are two slightly different routes with the same length of 16:Route 1:2(A)6 7(B2)8 11(C2)8 3(B1)4(B3)15 14 13(C3)12(C1);Route 2:2(A)6 7(B2)10 11(C2)8 3(B1)4(B3)15 14 13(C
33、3)12(C1).Either route will receive the full points.Enumerating all the full routes and computing their lengths would be exhaustive.However,thisproblem can be solved without a complete enumeration because the graph is a planar graph andthe edge lengths are such that the travel direction is always wit
34、h 90 degrees of the destination.This means,the shortest path between any two nodes is easy to find.To solve this problem by hand,one can first guess a good(not necessarily optimal)sequence outof B1,C1,B2,C2,B3,C3 and calculate its travel distance.Indeed,there are several sequencesthat all lead to a
35、distance of 17.If you get a slightly higher one,it is fine.The distance5becomes an upper bound of the shortest distance.Then,start enumerating all the sequencesfrom B1,C1,B2,C2,B3,C3 but eliminate those once a part of their total distance reaches 17.When you find a route with distance 16,it becomes
36、the new upper bound.This procedure iscalled branch and bound.b.This question is unrelated to the graph shown in part a;instead,we consider a general graph ofmany nodes and edges.Suppose that the carrier just picked up an order(we call it the originalorder)and will travel through the edges e1,e2,.,em
37、in the graph to deliver this original order.When s/he travels through an edge e,s/he may pick up a new order for the same destinationfrom a merchant located somewhere on this edge,at probability Pe 0,1.Such probabilitiescorresponding to the edges e1,e2,.,emare P1,P2,.,Pm.We ignore the probability of
38、 two ormore such new pickups on each edge e as they tend to be very small.What is the expected number of new order(s)for the same destination that this carrier can pickup over the given route(disregarding the trunk capacity)?What is the probability that s/he picks up at least one new order for the s
39、ame destination overthe given route?Answer:For the 1st question,P1+P2+Pm.Let ui 0,1 be the number of pickupover edge ei,for i=1,.,m.We can get our answer fromE(u1+u2+um)=E(u1)+E(u2)+E(um)=P1+P2+Pm.For the 2nd question,1(1P1)(1P2).(1Pm).Here,(1Pi)is the probability of nopickup over eiand,by statistic
40、al independence,(1P1)(1P2).(1Pm)is that of no pickupover the entire route,so 1 minus this product is the probability of picking up at least one order.Alternatively,one can use conditional probability to obtain the recursion:P1+(1 P1)Pr(at least one new pickup after e1)=P1+(1 P1)?P2+(1 P2)Pr(at least
41、 one new pickup after e2)?=.=P1+(1 P1)?P2+(1 P2)?P3+.(Pm1+(1 Pm1)Pm)?.This recursion is also a right answer.Both of the above answers are also equal tomXk=1(1)k+1Xdistinct i1,.,ik1,.,mPi1Pi2.Pik.c.This question is a followup of part b.In this question,we no longer fix the route in part b butfind one
42、 to maximize the carriers profit.Suppose that the carrier receives a fixed reward of rfor each delivery and spends,which equals the total lengths of the edges that s/he travels frompickup to delivery.In total,s/he makes a profit of r on this delivery.(We have set the costfactor of travel distance to
43、 1,for simplicity.)Suppose that the carrier just picked up the original order and has this order only.What is his/heroptimal route assuming the scooters trunk has a capacity of 2 orders?You shall consider boththe travel distance as a cost and the possible additional profit of r for picking up a new
44、order.Because any new order has the same destination,its travel cost is ignored.Also,suppose that0 Pe mine/r,1,where eis the length of edge e and Peis defined in part b.6Answer:Assume,without loss of generality,there are T nodes and T is the desti-nation node.First,from every node i,find the shortes
45、t path to T and its shortesttravel distance ci(if there is a tie between multiple paths with the same distance,break it arbitrarily.)For i=T,we have cT=0.Next,using c1,c2,.,cT,compute the optimal expected future reward riat everynode i,using the maximization formula(3)given below.For i 6=T,let jibe
46、theadjacent node of i that attains the maximum(again,if there is a tie,break itarbitrarily.)The carriers best route is decided at each node as follows:at node i,if the carrierhas yet to pick up an extra order,travel to ji;if the carrier has picked up an extraorder,then his/her trunk has reached the
47、maximum capacity,so follow the shortestpath from i to T.Note that the above route is not predetermined but decided as the carrier travels.In other word,it is a strategy or policy.It is better than following any predetermined route because the bestway depends on whether an extra pickup is made or not
48、.When the carrier is at a node i and has not made a second pickup,deciding where the carriershould go uses the expectation of the“profit to go”,which further depends on both pickupprobabilities and travel distance to T.Define rias the optimal expected future profit at node i before an extra pickup.F
49、or i=T,welet rT=r,which is the fixed reward.Suppose we have calculated rjfor the adjacent nodes of i.At i,if we travel to the adjacent node j,then the expected future profit becomes:(2r cj)(i,j),if a pickup occurs over(i,j),happening with probability P(i,j);rj(i,j),if a pickup does not occurs over(i
50、,j),happening with probability 1 P(i,j),where(i,j)is the length of edge(i,j).The maximum over all the adjacent nodes isri=maxj is adjacent to i?P(i,j)(2r cj)(i,j)+(1 P(i,j)(rj(i,j)?=maxj is adjacent to i?(1 P(i,j)rj+P(i,j)(2r cj)(i,j)?.(3)This is known as the Bellman equation.Given rT=r and(3),we ca