2018年阿里巴巴全球数学竞赛预选赛赛题及参考答案.docx

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 there are multiple answers to each question. If you submitted different answers, you may still get points. We try to write the answers rather thoroughly. It does not mean your answers 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 off 60 RMB” stackable coupons. “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 off 299 RMB” coupon, limited to one per order. This coupon applies to the list price and is stackable with any individual store coupons. For example, to a product listed at 299 RMB in a T store, one pays only 299 RMB - (the store discount based on 299 RMB) - 60 RMB. If the total list price is slightly below 299RMB, customers often adds filler item(s) (such as socks or tissues) from other T stores 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 T Store A. Xiao Ming has unlimited access to the two types of coupons described. What is the least amount that he must pay?Answer: 709 RMB. To get this answer, we have used filler items from other store(s). The answer will be reduced to 705 RMB if there are filler items solely from Store A (but this is less likely to hold in practice.) Below, we explain the steps to get 709 RBM.Below we compare buying both items in one order and buying them in two separate orders. The latter at 709 is cheaper.Buy the two items in one order: The final cost is250 (headphones list price) + 600 (speaker sets list price)60 14 × 5 apply (l 250+600 J = 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 following two orders: The headphone pair costs60250 4 × 5 (apply l 250 = 4 store coupons)+ 49 (filler items to reach 299 total list price) 60 (shopping cart coupon)= 219.(1)1change log: “50 RMB off 299 RMB” is corrected to “60 RMB off 299 RMB”1If one forgets to use filler items, s/he will pay 250 20 = 230, which is 11 more. The speaker set costs60600 10 × 5 (apply l 600 = 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 and speaker set at the same list prices as Store A does. Your store sells only these two models.You plan to issue “x RMB off 99 RMB” coupons, limited to one per order, where x is an integer greater than 0 and smaller than 99. (For example, the discount for an order of 250 RMB is x RMB, not 2x RMB). The T “60 RMB off 299 RMB” coupon can be applied to purchases at store B and can be stacked with your “x RMB off 99 RMB” coupon.What is the minimal number x such that Xiao Ming can spend at least 1 RMB less on either the 250 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 buying both the 250 RMB pair of the headphones and the 600 RMB speakers set in your Store B than in 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 using filler items from Store A; 2nd question: 36 for the 2nd question if using filler items from other stores and 38 if using filler items from Store A. Below, we give the steps assume 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 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 cheaper to buy them in two separate orders since we can apply the coupon to each order to get a total discount of 2x.2The part above has the formulas for the two orders: (239x) and (540x). Their total must be cheaper than 709, which is the answer in part 2. That is (239x) + (540x) 709 1, or x 35.5. Since x is an integer, we set x = 36 for this question .c. Mathematical modeling of product bundling. Suppose that the total costs of Item 1 and Item 2 are c1 and c2 (including production, storage, transportation, promotion, etc.), respectively. When a customer visits the T store, s/he perceives the values of these items at S1 and S2, respectively. We suppose that S1 and S2 are random variables that are independently and uniformly 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, because there, one may understand that one might not have to buy both items in your store or both items in store A.111. What is the value for p1, the price for Item 1, that maximizes the expected profit for each visiting customer? Here, assume that a visiting customer will purchase one piece of Item 1 if S1 p1, and if so, your profit is (p1 c1). Please provide a formula. Similarly, what is the value for p2 that maximizes the expected profit for each visiting customer?2Answer: optimal price p = ui+ci and expected profit r = (uici)for i = 1, 2.i2i4uiSince the steps are identical for i = 1, 2, we drop i for brevity. Let R be the random variableof profit, which depends on S. We calculate its expectation:r = ES(R) = ES(p c)buy）r= ES(p c)pS）u10=(p c)ps · uds1s s=u= (p c) u s=p= (p c)(u p) . uuAlternatively, we can obtain the same expected profit directly as the product of profit, (p c), and the probability of buying, up .u2The function r(p) := (pc)(up) is a concave quadratic function, so its maximum is attained at the point p such that rt(p) = 0 if p is on the interval of its allowed values, 0, u. Indeed, rt(p) = 0 yields p = u+c , which is the maximizer if c u (otherwise, p = u,which is a trivial case).With p = u+c , we get r = r(p) = (uc)2 .24u2. Assume we are going to sell a bundle item including one unit of Item 1 and one unit of Item 2 at price p12. The total cost of this item is t(c1 + c2), where 0 < t < 1. Assume a visiting customer will purchase one piece of this bundle if (S1 + S2) p12, and if so, your profit is p12 t(c1 + c2). Determine the price p12 to maximize the expected profit for each visiting customer. Please provide a formula.Answer: the price p12 that maximizes the expected return is3122 1 (c12 + c2 + 6u1u2）, c12 0, 3 u1 u212422p =1 (u1 + 2u2 + 2c12）,c12 3 u1 u2, u2 1 u132 1 (u1 + u2 + 2c12),c12 u2 1 u1, u1 + u2.12Note that p is continuous with respect to c12, including one the boundary points of threeintervals, so one can include each boundary point in either or both of the neighboring intervals.Also note that the calculation is not unique. Students can find the right answer by drawing a picture and using geometry.12No matter which approach is used, it takes the following three steps to compute p .Step 1. Define random variable S12 := S1 + S2. Compute the distribution of S12, denoted by p12. This is not a uniform distribution.r u1 +u2s u1 u2,s 0, u1p12(s) := Pr(S = s) = 1 u2p1(z y)p2(y)dy = · · · =,s u1, u2u1 u22120 u1 +u2 s , s u , u+ u .Step 2. Compute the expected profit as a function of S12, which isES12(p12 c12)buy） =u1 s ( r+u uu2 1r+uu1 +u2 u1 + u2 sru u(p12 c12)p12 s12 ds1201 2u12u21 2122u1 u21211 p2 ,p 0, u u22u2= · · · = (p12 c12) ×1 p12 + u1 , p12 u1, u22u1 u212212 (u1 +u2 p12 )2 ,p u , u+ u .(）For p12 / 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 profit12maximizer p within each of the intervals.p22u1 u2For p12 0, u1, setting the derivative of (p12 c12)(1 12 ) to 0 yields1231212p = 1 (c+ c2+ 6u u ）.1212Draw the curve or check the second derivative, and it is easy to see the above pis a123maximizer. From p u1, we get c12 u1 u2, which is the condition under which the212above p is the maximizer of the expected profit.12Using similar steps, we obtained pin 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 strategy is always better than the other.To establish this claim, it is sufficient to use a pair of examples, one showing one strategy better than the other, and the other showing the other way around. There are many such examples, so we do not specify one.Problem 2:a. The attached figure is an undirected graph. The circled numbers represent the nodes, and the numbers along the edges are their lengths (symmetrical in both directions).11223141225161B271811139310111 C222112213114115AB1B3C1C3An Alibaba Hema Xiansheng carrier starts at point A and will pick up three orders from merchants B1, B2, B3 and deliver them to three customers C1, C2, C3, respectively. The carrier drives a scooter 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 this question, assume no waiting time during each pickup and delivery.Answer: The shortest travel distance is 16, attained by the carrier taking the following stops:A -v- B2 -v- C2 -v- B1 -v- B3 -v- C3 -v- 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(C3) 12(C1).Either route will receive the full points.Enumerating all the full routes and computing their lengths would be exhaustive. However, this problem can be solved without a complete enumeration because the graph is a planar graph and the edge lengths are such that the travel direction is always with 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 out of B1, C1, B2, C2, B3, C3 and calculate its travel distance. Indeed, there are several sequences that all lead to a distance of 17. If you get a slightly higher one, it is fine. The distancebecomes an upper bound of the shortest distance. Then, start enumerating all the sequences from 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 the new upper bound. This procedure is called branch and bound.b. This question is unrelated to the graph shown in part a; instead, we consider a general graph of many nodes and edges. Suppose that the carrier just picked up an order (we call it the original order ) and will travel through the edges e1, e2, . . . , em 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 destination from a merchant located somewhere on this edge, at probability Pe 0, 1. Such probabilities corresponding to the edges e1, e2, . . . , em are P1, P2, . . . , Pm. We ignore the probability of two or more 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 pick up over the given route (disregarding the trunk capacity)?What is the probability that s/he picks up at least one new order for the same destination over the given route?Answer: For the 1st question, P1 + P2 + · · · + Pm. Let ui 0, 1 be the number of pickup over 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 (1 P1)(1 P2) . . . (1 Pm). Here, (1 Pi) is the probability of no pickup over ei and, by statistical independence, (1 P1)(1 P2) . . . (1 Pm) is that of no pickup over 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 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 tomkX=1k+1(1)Xdistinct i1,.,ik1,.,mPi1 Pi2. . . Pi .k c. This question is a followup of part b. In this question, we no longer fix the route in part b but find one to maximize the carriers profit. Suppose that the carrier receives a fixed reward of r for each delivery and spends £, which equals the total lengths of the edges that s/he travels from pickup to delivery. In total, s/he makes a profit of r £ on this delivery. (We have set the cost factor of travel distance to 1, for simplicity.)Suppose that the carrier just picked up the original order and has this order only. What is his/her optimal route assuming the scooters trunk has a capacity of 2 orders? You shall consider both the travel distance as a cost and the possible additional profit of r for picking up a new order. Because any new order has the same destination, its travel cost is ignored. Also, suppose that 0 Pe min£e/r, 1, where £e is the length of edge e and Pe is defined in part b.Answer: Assume, without