Maths Olympiad Prep

Library / /409 of 428

, 2025

Combinatorics Difficulty 3.8 AMC 10/12 Find the answer Canada

In the diagram, circles are connected if they are joined
by a line segment.

Figure 0

Each circle is filled with one integer so that

the positive difference between each pair of integers in
connected circles is dd, and the sum of the five integers in the circles is 5454. For how many different values of dd between 11 and 2020 inclusive can the circles be filled in
this way?

Pick one

Solution

Suppose the integer in the centre circle is aa. Then each integer in a circle connected to the centre circle is either dd more than aa, which is a+da+d, or it is dd less than aa, which is ada-d. The integers in the two circles connected to the centre could both be a+da+d, as in Figure 1 below, or they could both be ada-d, as in Figure 2, or one could be ada-d and one could be a+da+d, as in Figure 3. We note that in the last case (Figure 3), swapping locations of the ada-d and the a+da+d does not change the integers in the final two empty circles (since they still depend on a+da+d and ada-d), and thus does not change the sum of the five integers. [[IMAGE0]] Figure 1 [[IMAGE1]] Figure 2 [[IMAGE2]] Figure 3 Next, we explain why it is possible to place integers into the remaining two circles (in each of the three cases above) so that the positive difference between each pair of integers in connected circles is dd. For the case that began in Figure 1, the integers in the two empty circles are either dd more than a+da+d, which is a+2da+2d, or they are dd less than a+da+d, which is aa. These integers could both be a+2da+2d, as in Figure 1a below, or they could both be aa, as in Figure 1b, or one could be a+2da+2d and one could be aa, as in Figure 1c. We note that in the last case (Figure 1c), swapping locations of the final two integers, a+2da+2d and aa, does not change the sum of the five integers. [[IMAGE3]] Figure 1a [[IMAGE4]] Figure 1b [[IMAGE5]] Figure 1c For the case that began in Figure 2, the integers in the two empty circles are either dd more than ada-d, which is aa, or they are dd less than ada-d, which is a2da-2d. These integers could both be aa, as in Figure 2a below, or they could both be a2da-2d, as in Figure 2b, or one could be aa and one could be a2da-2d, as in Figure 2c. We again note that in the last case (Figure 2c), swapping locations of the final two integers, aa and a2da-2d, does not change the sum of the five integers. [[IMAGE6]] Figure 2a [[IMAGE7]] Figure 2b [[IMAGE8]] Figure 2c Finally, for the case that began in Figure 3, each integer in an empty circle must have a positive difference of dd with both ada-d and a+da+d. The integer dd more than ada-d is aa, and the integer dd less than ada-d is a2da-2d. The integer dd more than a+da+d is a+2da+2d, and the integer dd less than a+da+d is aa. Thus, aa is the only integer that has a positive difference of dd with both ada-d and a+da+d, and so the integers in the two empty circles must each be equal to aa, as shown in Figure 3a. [[IMAGE9]] Figure 3a Suppose that the sum of the five integers in the circles is SS. For Case 1a (which corresponds to Figure 1a), adding the five integers in the figure, we getS=a+(a+d)+(a+2d)+(a+d)+(a+2d)=5a+6dS=a+(a+d)+(a+2d)+(a+d)+(a+2d)=5a+6d. In the table below, we determine the value of SS for each of the 77 cases. Case 1a Case 1b Case 1c Case 2a Case 2b Case 2c Case 3a S=5a+6dS=5a+6d S=5a+2dS=5a+2d S=5a+4dS=5a+4d S=5a2dS=5a-2d S=5a6dS=5a-6d S=5a4dS=5a-4d S=5aS=5a We must determine the number of different integers dd, between 11 and 2020 inclusive, for which at least one of the seven expressions for SS is equal to 5454 and aa is an integer. Consider Case 1a, from which we get 5a+6d=545a+6d=54. Since both aa and dd are integers, and dd is between 11 and 2020 inclusive, we can systematically substitute values of dd into this equation, and then solve for aa to determine if aa is an integer. For example if d=1d=1, we get 5a+6×1=545a+6\times1=54 or 5a=485a=48. However, there is no integer aa for which 5a=485a=48 and so d=1d=1 is not a possible value of dd in Case 1a. Substituting d=2d=2 and d=3d=3 similarly give non-integer values of aa. When d=4d=4, we get 5a+6×4=545a+6\times4=54 and so 5a=305a=30 or a=6a=6. In this case, the pair of integers d=4d=4 and a=6a=6 satisfy the equation 5a+6d=545a+6d=54. Substituting d=4d=4 and a=6a=6 into Figure 1a, we get the following diagram. [[IMAGE10]] We can confirm that the positive difference between each pair of integers in connected circles is 44 (an integer between 11 and 2020 inclusive), and the sum of the five integers in the circles is 5454, as required. Thus d=4d=4 is a possible value satisfying the given conditions. We can systematically continue to substitute d=5,6,7,,20d=5,6,7,\dots, 20 into 5a+6d=545a+6d=54 and solve the equation to determine which values of dd give integer values of aa. The next smallest value of dd for which aa is an integer is d=9d=9. In this case, we get 5a+6×9=545a+6\times9=54 and so 5a=05a=0 or a=0a=0. We could continue in this systematic way, however since there are 2020 possible values of dd and 77 cases to check, this would take a while to complete. Instead, we might recognize that d=4d=4, a=6a=6 and d=9d=9, a=0a=0 are both solutions to 5a+6d=545a+6d=54. Notice that from the first solution to the second, the value of dd increases by 55, and the value of aa decreases by 66. Can you see why increasing dd by 55 and decreasing aa by 66 gives the next possible pair of integers for which 5a+6d=545a+6d=54? (Hint: Take a close look at the left side of the equation.) If we increase dd by 55 again, and decrease aa by 66, we get d=9+5=14d=9+5=14 and a=06=6a=0-6=-6, and since 5a+6d=5×(6)+6×14=30+84=545a+6d=5\times(-6)+6\times14=-30+84=54, then d=14d=14 and a=6a=-6 is a solution to the equation (and in fact, this is the next smallest value of dd that works). The final integer value of dd between 11 and 2020 inclusive for which 5a+6d=545a+6d=54 is d=14+5=19d=14+5=19, and in this case a=66=12a=-6-6=-12 or (d,a)=(19,12)(d,a)=(19, -12) Therefore, Case 1a gives d=4,9,14d=4,9,14, and 1919, or 44 values of dd which satisfy the given conditions. We continue in this way for each of the first four cases, and summarize all possible integer solutions for those cases in the table below. Case 1a 5a+6d=545a+6d=54 $(d,a)=(4,6),
(9,0), (14, -6), (19, -12) d=4,9,14,19Case1b Case 1b 5a+2d=54 (d,a)=(2,10),
(7,8), (12,6), (17,4) d=2,7,12,17Case1c Case 1c 5a+4d=54 (d,a)=(1,10),
(6,6), (11, 2), (16, -2) d=1, 6, 11,
16Case2a Case 2a 5a-2d=54 (d,a)=(3,12),
(8,14), (13, 16), (18,18) d=3, 8, 13,
18 Notice that after the first four cases shown above, all possible values of

Figure for this problemdfrom from 1to to 20 inclusive satisfy the given conditions with the exception of

Figure for this problemd=5,10,15,and, and 20.InCase3aweget,. In Case 3a we get, 5a=54andso and so aisnotaninteger.Next,considerCase2b, is not an integer. Next, consider Case 2b, 5a-6d=54.Eachvalueof. Each value of dlefttocheck( left to check (d=5,10,15, 20)isamultipleof) is a multiple of 5,andso, and so 6disamultipleof is a multiple of 5 for each of these possible values of

Figure for this problemd.Since. Since 5aisalsoamultipleof is also a multiple of 5 for all possible integers

Figure for this problema,then, then 5a-6d is the difference between two multiples of

Figure for this problem5,andthusisamultipleof, and thus is a multiple of 5. However, the right side of the equation

Figure for this problem5a-6d=54isnotamultipleof is not a multiple of 5andso and so dcannotbeequaltoamultipleof cannot be equal to a multiple of 5.Inthefinalcase,. In the final case, 5a-4d=54, it is similarly not possible for

Figure for this problemdtobeequaltoamultipleof to be equal to a multiple of 5.Thus. Thus dcanbeequaltoeachofthefirst can be equal to each of the first 20 positive integers with the exception of

Figure for this problem5,10,15,and, and 20,andsothereare, and so there are 20-4=16differentpossiblevaluesof different possible values of d. It is worth noting that there are many different ways to find the integer solutions to each of the

Figure for this problem7 equations (cases) above. For example, the value of each of the terms

Figure for this problem6d,, 2d,, 4d,, -2d,, -6d,, -4d,, 0d is even for all integers

Figure for this problemd, and the right side of each equation,

Figure for this problem54, is also even. This means that in each equation, the value of

Figure for this problem5amustbeeven,andso must be even, and so aiseven.Further,when is even. Further, when aiseven,theunitsdigitof is even, the units digit of 5ais is 0. Since the units digit of

Figure for this problem54is is 4, what do we now know about the units digit of each term containing a

Figure for this problemd, and in each case, what does that tell us about the possible values of

Figure for this problemd$?

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.