Problems and solutions

Náboj Math 2026

Problem 1

At the fair’s special can-toss game, each can has a number. You may knock down any cans you want, and you win only if the sum of their numbers is exactly 50. Find such a set of cans from those shown in the picture below and list all of its elements in increasing order.

PIC

Solution

Answer:

6, 16, 28


Most of the numbers on the cans are multiples of 3. When 50 is divided by 3, the remainder is 2, so the sum of the chosen cans must also leave a remainder of 2 when divided by 3. Therefore, at least one number that is not divisible by 3 must be included. The only such numbers are 16 and 28.

Using only one such number is not possible: The number 16 leaves a remainder of 1 when divided by 3, and 28 also leaves a remainder of 1. Adding any number of multiples of 3 to either 16 or 28 does not change this remainder, so the total cannot equal 50. Hence, both 16 and 28 must be used. Their sum is 16 + 28 = 44, which leaves a remainder of 2 when divided by 3. To reach 50, we have to add 50 44 = 6, which is one of the cans and cannot be formed as a sum of any other cans. Therefore, the cans to knock down are 6, 16, and 28.

Statistics
1023
teams received
99.6%
teams solved
00:12:43
average solving time

Problem 2

Teresa has three standard six-sided dice: one red, one blue, and one yellow. Each die has faces numbered 1 through 6. After rolling all three dice once, she adds the three numbers to get the total. In how many different ways can she get a total of 8?

Solution

Answer:

21


There are five possibilities to get a total of 8 with three dice:

8 = 6 + 1 + 1 = 5 + 2 + 1 = 4 + 3 + 1 = 4 + 2 + 2 = 3 + 3 + 2.

In the case 6 + 1 + 1, the number 6 may be shown on the red die or on the blue die or on the yellow die. Therefore we have three possibilities in the case 6 + 1 + 1. By analogy, we also have three possibilities in the cases 4 + 2 + 2 and 3 + 3 + 2. In the case 5 + 2 + 1 we have 3 2 1 = 6 possibilities for the distribution of the numbers on the three colored dice. The same is true in the case 4 + 3 + 1. Therefore there are 3 3 + 2 6 = 21 possibilities in total.

Statistics
1023
teams received
94.1%
teams solved
00:28:19
average solving time

Problem 3

Adam has four children. He notices that his current age is equal to the sum of the ages of his three oldest children, while in six years, his age will be equal to the sum of the ages of his three youngest children. What is the age difference between Adam’s youngest and oldest child?

Solution

Answer:

12


Let a be the age of Adam and c1 c2 c3 c4 the ages of his children. The problem statement implies the equations a = c2 + c3 + c4 and a + 6 = (c1 + 6) + (c2 + 6) + (c3 + 6). Substituting the first equation into the second yields c2 + c3 + c4 + 6 = c1 + c2 + c3 + 18, which can be simplified to c4 = c1 + 12. Therefore the oldest child is 12 years older than the youngest child.

Statistics
1023
teams received
97.8%
teams solved
00:21:41
average solving time

Problem 4

A 24-hour digital clock displays times from 00:00 to 23:59. How many times during a full day does the display show exactly four out of the five digits 1, 2, 3, 4, 5 (in any order)?

Solution

Answer:

36


The hour must be a two-digit number not exceeding 23 with distinct digits picked from 1,,5; the only possibilities are 12, 13, 14, 15, 21, and 23. For each such hour, two digits have been used, leaving three remaining digits from which the minute must be formed using two distinct digits; this can be done in 3 2 = 6 ways, all of which are valid minutes. Hence each of the six allowable hours produces six valid times, giving 6 6 = 36 in total.

Statistics
1023
teams received
97.1%
teams solved
00:22:07
average solving time

Problem 5

If ABCDEFGH is a regular octagon, what is the size of the acute angle between the diagonals CF and EG in degrees?

PIC

Solution

Answer:

67.5


Let X be the intersection point of the two diagonals. Instead of computing ∠CXE, as suggested by the diagram, we compute the measure of ∠FXG, which is the same. To this end, first observe that ∠GFX = ∠GFC = 90, since BCFG is a rectangle. Moreover, as the triangle EFG is isosceles and ∠GFE = 135, we have ∠XGF = ∠EGF = 22.5. Therefore, from triangle FGX, we conclude that ∠FXG = 180 90 22.5 = 67.5.

Statistics
1023
teams received
88.3%
teams solved
00:31:46
average solving time

Problem 6

Let a, b, c, d, e be five distinct positive integers such that a < b < c < d < e and their arithmetic mean is 16. Determine the maximum possible value of d.

Solution

Answer:

36


Since

a + b + c + d + e 5 = 16,

it follows that a + b + c + d + e = 80. To maximize d, minimize the other terms subject to the ordering: The smallest possible values are a = 1, b = 2, c = 3, and e d + 1. Hence

80 = a + b + c + d + e 1 + 2 + 3 + d + (d + 1) = 7 + 2d,

so 2d 73 and therefore d 36 (d is an integer). This bound is attained by (a,b,c,d,e) = (1,2,3,36,38), which sums to 80 and satisfies the ordering condition. Thus the maximum possible value of d is 36.

Statistics
1023
teams received
96.0%
teams solved
00:16:13
average solving time

Problem 7

A traveler approached an ancient stone gate in the desert and found a sphinx blocking the way. The sphinx said, “Answer my riddle, and you may pass: I am thinking of a three-digit number with these properties:

What number did the sphinx choose?

Solution

Answer:

567


By divisibility by 9, the digit sum is 9 or 18. Since the number is odd, 6 cannot be the units digit, so it is in the hundreds or tens place. It cannot be the hundreds digit, since then the smallest possible digit sum is 6 + 7 + 8 = 21 > 18; hence 6 is the tens digit. Therefore the units digit is at least 7, so the digit sum must be 18, and the hundreds and units digits must sum to 12. The increasing possibilities are (3,9), (4,8), and (5,7): the first is excluded because deleting the 9 yields 36, still divisible by 9; the second is excluded because it gives an even number; thus (5,7) is the only valid choice. Hence the sphinx’s number is 567.

Statistics
1023
teams received
99.6%
teams solved
00:11:55
average solving time

Problem 8

Two equilateral triangles are positioned as shown in the diagram. Their corresponding sides are parallel, and they share the same circumcenter. The side lengths are 17cm (larger triangle) and 11cm (smaller triangle). The region common to both triangles is a hexagon (shaded in the diagram). Determine the perimeter of this hexagon (in cm).

PIC

Solution

Answer:

28


The overlap creates three smaller and three larger congruent equilateral triangles outside the shaded hexagon. Set AB = x and BC = y. Then the side length of the larger triangle is 2x + y = 17 and the side length of the smaller one is x + 2y = 11. Adding the two equations yields 3x + 3y = 28, which is exactly the perimeter of the hexagon.

PIC

Alternative solution. This solution provides a proof without words by mapping the sides of the hexagon onto one side of each of the two given equilateral triangles. Therefore the perimeter of the hexagon is exactly the sum of the side lengths of the given equilateral triangles, namely 17 + 11 = 28.

PIC

Statistics
1023
teams received
75.4%
teams solved
00:38:58
average solving time

Problem 9

Anna wants to get dressed for her sports club. She must wear exactly one T-shirt, one pair of shorts, one pair of socks, and one pair of sneakers, and she may optionally wear a ribbon in her hair. Each pair of socks and each pair of sneakers Anna wears is a matching pair (both items in the pair have the same color). She owns T-shirts in white, yellow, green, blue, and red; shorts and ribbons in white, black, and gray; socks in white, red, and orange; and sneakers in white and black. She wears white socks only if her entire outfit is white (including the ribbon, if she wears one). In how many different ways can Anna dress for her sports club?

Solution

Answer:

242


We count all admissible outfits by cases. Anna must wear exactly one shirt, one pair of shorts, one pair of socks, and one pair of sneakers, and may optionally wear a ribbon.

First consider white socks. By the given condition, white socks may be worn only if the entire outfit is white. Thus the T-shirt, shorts, and sneakers must all be white, and the ribbon is either not worn or white. This gives 2 outfits.

Now consider nonwhite socks (red or orange), giving 2 choices. In this case there are no further restrictions. There are 5 choices for the T-shirt, 3 for the shorts, 2 for the sneakers, and 4 choices for the ribbon (none, white, black, or gray). Hence this case yields

5 3 2 4 2 = 240

outfits.

Adding both cases, the total number of possible outfits is 240 + 2 = 242.

Statistics
1021
teams received
78.3%
teams solved
00:32:55
average solving time

Problem 10

Find a four-digit number satisfying the following properties:

Solution

Answer:

1239


Let ABCD denote the number, where A, B, C, and D are its digits; the conditions give B = 2A and D = 3C. Then

A2 + B2 + C2 + D2 = A2 + (2A)2 + C2 + (3C)2 = 5A2 + 10C2 = 95,

which simplifies to A2 + 2C2 = 19. Since the right-hand side is odd, A must be odd; moreover, A is a digit and A2 19, leaving only A {1,3}. Testing these values yields only A = 1, giving 2C2 = 18 and thus C = 3. Hence B = 2, D = 9, and the number is 1239.

Statistics
1013
teams received
97.9%
teams solved
00:10:42
average solving time

Problem 11

Alice is a positive person, so she wants to fill in the boxes in the expression

12345

with either a plus sign or a minus sign so that the result is a positive number. In how many ways can she do that?

Solution

Answer:

16


We first note that the sum ± 1 ± 2 ± 3 ± 4 ± 5 can never be 0; this is true since 1 + 2 + 3 + 4 + 5 = 15 is odd, and changing any sign changes the total by an even number, so the result is always odd. Now, if we take any choice of signs and switch every plus to a minus and every minus to a plus, the value changes from positive to negative or vice versa, giving a perfect pairing between positive and negative results. For each of the five boxes we may independently choose either a plus or a minus sign, giving 2 choices for each position and therefore 25 = 32 total sign choices. Since none produce zero, exactly half must be positive, so Alice can obtain a positive result in 16 ways.

Statistics
1976
teams received
93.3%
teams solved
00:27:50
average solving time

Problem 12

In the column addition shown below, each letter represents a decimal digit. Identical letters represent the same digit, and different letters represent different digits.

A A A + A A B + A C C 2 0 2 6

Find the three-digit number ABC.

Solution

Answer:

619


Since the first digit of all three numbers is the same, A must satisfy 3A 20 and 3A 18, as there cannot be a carry over of more than 2 when adding three digits. Therefore, A = 6. It follows that in the units column the digits B and C add up to 10. Thus, there is a carry over of 1 from the units column to the tens column. Therefore, we need C = 9 and it follows that B = 1. Hence ABC = 619.

Statistics
1972
teams received
98.0%
teams solved
00:13:41
average solving time

Problem 13

The diagram shows a square of side length 2 divided into four rectangles. If the rectangles all have equal area, find the sum of their perimeters.

PIC

Note: A segment common to two rectangles is included in both perimeters.

Solution

Answer:

53 3 = 172 3


Since the square has area 4, each rectangle must have area 1. This immediately gives that the width of the right rectangle is 1 2, so the width of the lower left rectangle is 2 1 2 = 3 2, and hence its height is 13 2 = 2 3. Consequently, the common height of the two remaining rectangles is 2 2 3 = 4 3. To find the total of the four perimeters, take the perimeter of the outer square, 4 2 = 8, and add twice the total length of the interior segments, since each is counted in two rectangles. The interior lengths are 2, 3 2, and 4 3, so their doubled sum is 2 (2 + 3 2 + 4 3 ) = 29 3 . Therefore, the desired sum of the perimeters is 8 + 29 3 = 53 3 .

PIC

Statistics
1960
teams received
85.7%
teams solved
00:34:12
average solving time

Problem 14

Tim forms a long string of digits by writing the four-digit block 2026 consecutively 2026 times, according to the following rules. He begins by writing 2026, then continues with 6202, which is 2026 written in reverse order, omitting the repeated digit 6 at the junction. He proceeds by alternating between the normal and reversed order of 2026, each time using the final digit of the preceding block as the initial digit of the next block, so that adjacent blocks overlap in exactly one digit, as illustrated in the scheme below, which shows the first six of the total of 2026 blocks.

PIC

Determine the sum of the digits of the resulting number.

Solution

Answer:

12158


The digit sum after writing 2026 once is 10. After the first one, every even numbered block will add the digits 202, for an increase in the digit sum of 4, and every odd numbered block will add 026, increasing the sum by 8.

This way, every time two blocks are added after the first one, which occurs 1012 times (1 + 2 1012 = 2025), the sum is increased by 12. At the end, we are left with the 2026th block, which is an even number, so it increases the sum by 4. In total, we get 10 + 1012 12 + 4 = 12158.

Statistics
1943
teams received
86.8%
teams solved
00:26:18
average solving time

Problem 15

It is 8:00 AM. What time will it be after 260320261998 hours have passed, assuming there are no clock changes (such as daylight saving time) during this interval?

Solution

Answer:

14 = 2 PM


Since a day has 24 hours, the time of day repeats every 24 hours. Thus it is enough to find the remainder when N = 260320261998 is divided by 24. This could be done by long division, but it is simpler to compute the remainders upon division by 3 and by 8 separately and combine the results.

Because the sum of the digits of N is divisible by 3, the number N itself is divisible by 3. For division by 8, the remainder is determined by the final three-digit block; here it is 998, and 998 leaves remainder 6 upon division by 8, so N also leaves remainder 6 upon division by 8. Therefore the remainder upon division by 24 must be a number less than 24 that is divisible by 3 and leaves remainder 6 when divided by 8; the only possibility is 6.

Hence after N hours, the clock advances by the same amount as after 6 hours. Starting from 8:00 AM, adding 6 hours gives 14:00 (or 2 PM).

Statistics
1927
teams received
93.4%
teams solved
00:20:19
average solving time

Problem 16

There is a bunch of grapes arranged as shown in the picture. A grape may be eaten only if all of the grapes directly below it (i.e. the one or two grapes it touches underneath) have already been eaten. For example, grape D must be eaten before A and B. In how many different orders can the entire bunch be eaten?

PIC

Solution

Answer:

16


As it stands, the only grape that can be eaten is grape F, leaving grapes A,B,C,D, and E.

At that point, we can either eat grape D or E. The situation is obviously symmetrical, so let us start with E, leaving grapes A,B,C, and D. Then, we can eat grapes C or D:

  • If we choose C, then we have to eat D, followed by either A or B (2 possibilities)
  • If we choose D, we can eat A,B, or C next, followed by the remaining two in any order (3 2 possibilities)

Thus, we always start with F, then choose between D or E, and then have 2 + 6 = 8 distinct possibilities. This totals 1 2 8 = 16 possible ways to eat the grapes.

Statistics
1907
teams received
96.9%
teams solved
00:15:42
average solving time

Problem 17

Let x be a positive integer such that

lcm(x,25 33 54 72) = 26 33 54 72andlcm(x,28 34 53 7) = 28 34 53 72.

How many distinct values can gcd(x,22 34 52 73) take?

Note: gcd(a,b) and lcm(a,b) denote the greatest common divisor and the least common multiple of integers a and b, respectively.

Solution

Answer:

12


The number x has to be of the form 2a 3b 5c 7d (no other primes can appear, or they would show up in the LCMs). The first condition is equivalent to a = 6, b 3, c 4, and d 2, while the second condition translates to a 8, b 4, c 3, and d = 2. This implies that in the prime factorization of gcd(x,22 34 52 73), the exponent of 2 is equal to 2, the exponent of 3 can be any number between 0 and 3, the exponent of 5 can be any number between 0 and 2, and the exponent of 7 is equal to 2. We conclude that there are 4 3 = 12 such numbers.

Statistics
1889
teams received
54.2%
teams solved
00:29:45
average solving time

Problem 18

A point is located inside a rectangle as shown in the diagram. Three angles are marked. Find the measure of the angle marked with a question mark (in degrees).

PIC

Solution

Answer:

71


Computing complements to 90 at the two vertices on the right, we conclude that the given interior point lies on the common axis of the two vertical sides of the rectangle. Therefore the whole configuration is symmetric with respect to this axis. We conclude that the desired angle equals 90 19 = 71.

PIC

Statistics
1873
teams received
92.0%
teams solved
00:16:43
average solving time

Problem 19

Alina wants to assemble a necklace using two types of beads. She purchased a total of 100 beads, with more cheap beads than expensive ones. The total cost of all the cheap beads was 459 florins. Additionally, each expensive bead costs 13 florins more than each cheap bead. All prices in florins are positive integers. How many florins did Alina pay for the expensive beads?

Solution

Answer:

1078


Let c be the number of cheap beads and p their (integer) price in florins. Then cp = 459 and since there are 100 beads in total with more cheap ones than expensive ones, we have 50 < c < 100. Since the price is an integer, c must be a divisor of 459 = 33 17 lying strictly between 50 and 100, and the only such divisor is c = 51. Thus p = 45951 = 9, and each expensive bead costs p + 13 = 22 florins. The number of expensive beads is 100 51 = 49, so Alina paid 49 22 = 1078 florins for the expensive beads.

Statistics
1845
teams received
88.6%
teams solved
00:20:26
average solving time

Problem 20

In the equation

M A T H N A B O J = G A M E,

each letter represents a digit, distinct letters represent distinct digits, and the symbol denotes multiplication. How many different values can the product M A N G O take?

Solution

Answer:

1


There are 10 distinct letters (M, A, T, H, N, B, O, J, G, E), so the digits 09 are all used exactly once, meaning one letter equals 0. It follows that both sides of the equality are necessarily equal to 0. In particular, 0 appears on both sides while not occurring in the denominator of the fraction. The only such letter is M, hence M = 0. Therefore, M A N G O = 0 regardless of the values assigned to the remaining letters, so the product can take exactly one value.

Statistics
1812
teams received
67.7%
teams solved
00:31:52
average solving time

Problem 21

Three lighthouses lie on a straight shoreline. The distance between each pair of adjacent lighthouses is 13 km. A ship at sea is 10 km from one of the two end lighthouses and 13 km from the middle lighthouse. How far (in km) is the ship from the other end lighthouse? Disregard the curvature of the Earth.

Solution

Answer:

24


Let S denote the position of the ship, let A and B be the two end lighthouses, and let M be the middle lighthouse. Since MS = MA = MB = 13, the points A, B, and S all lie on a circle with center M. Moreover, the segment AB is a diameter of this circle. By Thales’ theorem, the triangle ABS is therefore right-angled at S. Since AB = MA + MB = 26 and AS = 10, the Pythagorean theorem yields

BS = AB2 AS2 = 262 102 = 576 = 24.

Hence, the distance from the ship to the other end lighthouse is 24km.

Statistics
1770
teams received
88.9%
teams solved
00:18:15
average solving time

Problem 22

In how many ways can one assign one of three colors to each of the 10 pieces of a pyramid of height 4 so that each subpyramid of height 2 (oriented upwards) is colored using either all three colors, or only one color? An example of such coloring can be seen in the picture.

PIC

Solution

Answer:

81


Under the given conditions, the coloring of the pyramid is completely determined by the coloring of the bottom row, since every coloring of the bottom row can be uniquely completed to a coloring of the whole pyramid. Because three colors can be chosen for each building block, there are a total of 34 = 81 possible colorings.

Statistics
1723
teams received
43.3%
teams solved
00:37:50
average solving time

Problem 23

Each vertex of a regular 100-gon is assigned a distinct number from 1,2,,100 so that the absolute value of the difference between the numbers at each pair of opposite vertices is the same fixed number n. Find the sum of all possible distinct values of n.

Solution

Answer:

93


Let n be a positive integer for which such an arrangement exists. Then the number 1 must be paired with n + 1 (in the sense of being assigned to two opposite vertices; we will refer to such pairs simply as pairs in the sequel). Next, 2 must be paired with n + 2, and continuing in this way, we see that k must be paired with n + k for all k = 1,2,,n. In particular, n is paired with 2n.

Thus every number from the block {1,2,,2n} is paired with another number from the same block, and this block can be separated from the remaining numbers {2n + 1,,100}. If 2n = 100, the process terminates. Otherwise, we repeat the same argument starting from 2n + 1, which must be paired with 3n + 1, and continue analogously.

Eventually, the set {1,2,,100} splits into disjoint blocks of length 2n. This is possible if and only if 100 is divisible by 2n, that is, if and only if n is a positive divisor of 50.

It is easy to see that this construction yields a valid pairing for every such divisor (by assembling 100 2n blocks as above). Therefore, the answer is the sum of all positive divisors of 50, which is

1 + 2 + 5 + 10 + 25 + 50 = 93.
Statistics
1665
teams received
43.8%
teams solved
00:35:20
average solving time

Problem 24

Take two copies of the right triangle with side lengths 5, 12, and 13 and place them on each other so that they share the vertex with the smallest angle and partially overlap along their edges, as shown in the diagram. What is the area of one of the triangles forming the non-overlapping region?

PIC

Solution

Answer:

6 5 = 1.2


The grey triangle is similar to the large right triangle with the length of the shortest side equal to 13 12 = 1, since both are right triangles and share another angle (the top one in our diagram).

Therefore, the similarity ratio between the two right triangles is 1 : 5 and the second leg in the grey triangle has a length of 12 5 . As a consequence, the area sought is

1 2 1 12 5 = 6 5.
Statistics
1574
teams received
76.4%
teams solved
00:26:41
average solving time

Problem 25

Each of the seven dwarves chose a positive integer. All of them know the numbers chosen by the others. Snow White asked each dwarf what number he had chosen.

It is known that the sum of the seven chosen numbers is 46. It is also known that exactly one dwarf lied; all other dwarves made statements referring to the numbers actually chosen, not to the numbers reported. Find all numbers the lying dwarf could have chosen.

Solution

Answer:

7, 14


Let the dwarves’ numbers be a1,a2,,a7. We first observe that the liar must be either the 6th or the 7th dwarf.

Indeed, if the 7th dwarf told the truth, then a7 = a1 + + a6, so the total sum satisfies a1 + + a7 = 2a7 = 46, hence a7 = 46 2 = 23. If the 6th dwarf were also telling the truth, then similarly a6 = a1 + + a5, so a7 = a1 + + a6 = 2a6, which would force a6 = 23 2 , a contradiction since a6 must be an integer. Thus, in this situation the 6th dwarf must be the liar.

Therefore the first five statements are true, giving

a2 = a1,a3 = a1 + a2 = 2a1,a4 = a1 + a2 + a3 = 4a1,a5 = a1 + + a4 = 8a1,

so a1 + + a5 = 16a1. Moreover, at least one of a6 or a7 (namely the one corresponding to a truthful dwarf) is greater than or equal to a1 + + a5 = 16a1, and hence

a1 + + a7 16a1 + 16a1 = 32a1.

Since the total sum is 46, this implies 32a1 46, so a1 = 1 (a1 is a positive integer), and consequently a2 = 1, a3 = 2, a4 = 4, and a5 = 8. In particular, we obtain a1 + + a5 = 16.

Now consider the last two dwarves. If the 6th dwarf told the truth, then a6 = 16, so to obtain the total sum 46 we must have a7 = 46 (16 + 16) = 14. If instead the 6th dwarf lied, then the 7th dwarf is truthful and a7 = a1 + + a6 = 16 + a6. By the earlier computation, a7 = 23 in this case, which leads to a6 = 7.

Both configurations satisfy the requirement that exactly one dwarf lies, so we conclude that the lying dwarf could have chosen either 7 or 14.

Statistics
1468
teams received
63.1%
teams solved
00:30:16
average solving time

Problem 26

For communication with an orbital satellite, six distinct channels are chosen from the set {1,2,,13}, and only the set of channels matters – two selections are considered the same if they contain the same six channels, regardless of order. To achieve the best transmit rate, the selection must include at least one pair of channels whose numbers differ by an odd integer. How many such sets of channels are possible?

Solution

Answer:

1708


Two chosen channels differ by an odd number exactly when they have opposite parity. Rather than counting directly, we count the complement: we subtract the selections that have no odd differences from all possible selections.

A set of six channels has no odd differences precisely when every pair has even difference, which happens only if all six channels have the same parity. In {1,2,,13} there are seven odd channels and six even channels, so the number of all-odd or all-even selections is (7 6) +( 6 6) = 8.

Since there are (13 6) = 1716 total choices of six channels, the number of sets with at least one odd difference is 1716 8 = 1708.

Statistics
1352
teams received
47.9%
teams solved
00:23:42
average solving time

Problem 27

Let N be a 7-digit number that is divisible by each of its digits. If all the digits of N are different and non-zero, find the sum of the digits of N.

Solution

Answer:

36


Since N has seven distinct non-zero digits, at least one is even, so N is even. If 5 were a digit, then divisibility by 5 would force N to end in 0, contradicting that all digits are non-zero; hence 5 is excluded. Now N uses seven digits from {1,2,3,4,6,7,8,9}, so it omits exactly one digit from this set. It cannot omit 9: if 9 were omitted, the digit set would be {1,2,3,4,6,7,8} with sum 31, so N would fail the divisibility-by-3 test despite containing the digit 3, a contradiction. Hence 9 must appear among the digits of N, so N (and thus its digit sum) is divisible by 9, and since 1 + 2 + 3 + 4 + 6 + 7 + 8 + 9 = 40, we must omit 4 to obtain the digit sum 36, the only possible multiple of 9. One example of such a number is N = 9867312.

Statistics
1202
teams received
85.4%
teams solved
00:17:00
average solving time

Problem 28

A truncated octahedron is made by cutting off the vertices of a regular octahedron in such a way that what remains is a polyhedron with eight regular hexagonal faces and six square faces. As a fraction of the volume of the original octahedron, what is the volume of the truncated octahedron?

PIC

Note: A regular octahedron is a solid with eight identical equilateral triangular faces.

Solution

Answer:

8 9


A regular octahedron with edge-length a has volume ka3 for some constant k (in fact, it is not difficult to show that k = 23, but this is not needed in the solution). To make the truncated octahedron we remove half an octahedron (a square-based pyramid) of edge-length a3 from each of the 6 vertices of the octahedron. The volume removed is equivalent to that of three octahedra each with edge length a 3 . The total volume removed is therefore 3 k (a 3 ) 3 = ka39. So the volume of the truncated octahedron as a fraction of the volume of the original octahedron is

1 ka3 (ka3 1 9ka3) = 8 9.
Statistics
1128
teams received
53.6%
teams solved
00:25:03
average solving time

Problem 29

Find all real solutions of the equation

8 (4x + 4x) 54 (2x + 2x) + 101 = 0.
Solution

Answer:

± 1, ± 2


Let a = 2x + 2x. Then 4x + 4x = a2 2. Substituting into the equation gives

8(a2 2) 54a + 101 = 0

which simplifies to

8a2 54a + 85 = 0.

Solving this quadratic equation leads to

a1,2 = 54 ±542 4 8 85 2 8 = 54 ±2916 2720 16 = 54 ±196 16 = 54 ± 14 16

with the results

a1 = 17 4  and a2 = 5 2.

In the first case, we have

2x + 1 2x = 17 4 ,

which leads to 2x = 4 or 2x = 1 4, giving x = 2 or x = 2. In the second case, we have

2x + 1 2x = 5 2,

which leads to 2x = 2 or 2x = 1 2, giving x = 1 or x = 1. Therefore the solutions to the original equation are x = ±1,±2.

Statistics
1018
teams received
41.6%
teams solved
00:28:22
average solving time

Problem 30

On the cuboidal planet Railbox Prime there are eight cities, one at each corner, and railroads run along every edge so that cities joined by an edge are directly connected; in addition, there are four “tunnel railroads” that bore through the planet, each linking a pair of opposite corner cities. A visitor starts in one corner city A and wants to reach a neighboring corner city B (one edge away) by taking exactly five railroad segments, never visiting any city more than once, and stopping upon arrival; if the visitor wishes to use at least one tunnel railroad along the way, how many such routes are possible? The diagram shows an example of one such route.

PIC

Solution

Answer:

28


Let us color the eight corner cities in two colors like a 3D checkerboard so that every railroad segment (whether it is an edge railroad or a tunnel) always goes from a city of one color to a city of the other color. Since the visitor starts at a city of one color and must end at a neighboring city of the other color in exactly five segments, the route must alternate colors and therefore visit exactly two intermediate cities of each color, with all visited cities distinct. Moreover, in the present configuration with tunnels, every pair of cities of different colors is directly connected by a railroad segment.

First we count all length-5 routes, disregarding the tunnel condition. Each route has the form

A o1 e2 o2 e3 B,

where o1, o2 are distinct cities of B’s color, and e2, e3 are distinct cities of A’s color. There are 3 2 = 6 ways to choose the ordered pair (o1,o2) from the three cities of B’s color other than B, and likewise there are 3 2 = 6 ways to choose the ordered pair (e2,e3) from the three cities of A’s color other than A. Hence there are 6 6 = 36 length-5 routes in total.

Let us now subtract the routes that use no tunnel at all, i.e. routes using only edge railroads. The first move cannot go directly to B, so only two first moves are possible. From each of these two first moves there turn out to be exactly 4 ways to complete a length-5 route to B using only edges, giving 2 4 = 8 edge-only routes.

Therefore, the number of length-5 routes that use at least one tunnel is 36 8 = 28.

Statistics
898
teams received
27.6%
teams solved
01:17:41
average solving time

Problem 31

Consider an election with 2026 voters and four candidates: A, B, C, and D. Candidate A performed the worst, receiving one-sixth as many votes as candidate B. Candidate C received exactly 446 fewer votes than the combined total of all the other candidates. Candidate D won the election with fewer than 800 votes. Each voter cast exactly one vote for one of the four candidates. How many votes did candidate A receive?

Solution

Answer:

63


Denote the individual numbers of votes by a, b, c, and d. These are nonnegative integers satisfying

a + b + c + d = 2026, b = 6a, c = (a + b + d) 446, a,b,c < d < 800, a < b,c,d.

If we add c to both sides of the third relation, we obtain

2c = a + b + c + d 446 = 2026 446 = 1580.

Therefore c = 790, from which it further follows that

a + b + d = 2026 790 = 1236.

Substituting for b, we get

a + 6a + d = 1236ord = 1236 7a.

Since d < 800 and at the same time d > c = 790, we have 791 d 799. Hence

791 1236 7a 799or437 7a 445.

The only number divisible by 7 in the given interval is 441 = 7 63. Therefore the answer is a = 63. One can then compute that b = 378, c = 790, d = 795, and all the conditions from the problem are indeed satisfied.

Statistics
792
teams received
74.0%
teams solved
00:28:50
average solving time

Problem 32

Three squares ABCD, EFGH, and KGIJ are arranged as shown in the figure: Points E and F lie on segment AB, points I and J lie on segment CD, and point K lies on segment GH. Moreover, the centers of the three squares lie on a single straight line. Given that AD = 7 and HK = 1, find FB.

PIC

Solution

Answer:

127


Let a and b be the side lengths of the squares EFGH and KGIJ. From the problem statement, we get the equations 7 = AD = JK + HE = a + b and 1 = HK = HG KG = a b. The solutions of this system of linear equations are a = 4 and b = 3.

The straight line passing through the centers of all the three squares divides the area of each square into two halves. Therefore, the area of the rectangle FBCI can be computed by

1 2(a + b)2 1 2a2 1 2b2 = ab.

The area of the rectangle FBCI is also given by FB (a + b). From these two equations, we obtain FB = ab a+b = 12 7 .

Statistics
701
teams received
44.1%
teams solved
00:26:32
average solving time

Problem 33

Several numbers are written on a blackboard, one of which is 2026. If 2026 is erased, the arithmetic mean of the numbers on the board decreases by 6. If instead an additional 2026 is written on the blackboard, the arithmetic mean increases by 4. Find the sum of the numbers originally written on the blackboard.

Solution

Answer:

10010


Let the sum of the initial n numbers be S. Then

S 2026 n 1 = S n 6, S + 2026 n + 1 = S n + 4.

These equations can be simplified to

S = 2032n 6n2, S = 2022n 4n2.

Subtracting the second identity from the first gives

0 = S S = (2032 2022)n + (6 + 4)n2 = 10n 2n2 = 2n(5 n).

Since n0, it follows that n = 5. Therefore, S = 2022n 4n2 = 10010.

Statistics
619
teams received
53.2%
teams solved
00:19:19
average solving time

Problem 34

A flea jumps along the circumference of a circle. Its first jump subtends a central angle of 1 (that is, the angle between the radii to the endpoints of the jump is 1). Each subsequent jump is in the same direction and subtends 2, then 3, and so on. On which jump does the flea first land back at its starting point?

Solution

Answer:

80


After n jumps, the flea will have covered

1 + 2 + + n = 1 2n(n + 1)

degrees. We are looking for the smallest n such that this number is a multiple of 360; equivalently, we want n(n + 1) to be a multiple of 720 = 16 9 5. Each of the three factors has to divide either n or n + 1, since any two consecutive numbers are coprime. Let us start looking at multiples of the largest factor 16 – this gives candidates for n: 15, 16, 31, 32, 47, 48, 63, 64, 79, and finally 80, which is itself divisible by 5 and n + 1 = 81 is divisible by 9. We conclude that 80 is the sought number of jumps.

Statistics
538
teams received
50.6%
teams solved
00:41:55
average solving time

Problem 35

In the kingdom of Naboia, there are three magical guilds: the Guild of Fire, the Guild of Water, and the Guild of Wind. Each guild consists of two master mages and two apprentice mages. To defend the realm, four battle pairs must be formed, each consisting of one master and one apprentice, but no pair may contain two mages from the same guild. In addition, each guild must contribute at least one master and at least one apprentice to the four pairs. In how many ways can the battle pairs be formed?

Note: Each master and apprentice is a distinct individual, so which particular mage appears in each pair matters, but the order in which the four pairs are listed is irrelevant.

Solution

Answer:

768


Since four apprentices are selected and each guild must contribute at least one apprentice, the apprentice distribution among the guilds must be (2,1,1) in some order. Similarly, four masters are selected and each guild must contribute at least one master, so the master distribution must also be (2,1,1).

There are two cases, according to how the guild that contributes two apprentices relates to the guild that contributes two masters.

In the first case, a single guild supplies both two apprentices and two masters; let us denote this guild by X. There are 3 possible choices for X. From the remaining two guilds, the apprentices can be chosen in 2 2 = 4 ways, and likewise the masters can be chosen in 2 2 = 4 ways.

For each such selection, the two apprentices from X must be paired with the two masters coming from the other two guilds, which can be done in 2 ways. Once this is fixed, the remaining two apprentices must be paired with the two masters from X, which can again be done in 2 ways. Therefore, there are 2 2 = 4 valid ways to pair masters with apprentices in this case. Hence this case contributes 3 4 4 4 = 192 pairings.

In the second case, one guild (X) supplies two apprentices, while a different guild (Y ) supplies two masters. There are 3 choices for X and, once it is fixed, 2 choices for Y . The remaining apprentices can be chosen from the two guilds different from X in 2 2 = 4 ways, and the remaining masters can be chosen in the same number of ways. For any such selection, there are 3 2 = 6 admissible ways to form the master–apprentice pairs: the two apprentices from X may be assigned to any two of the three available masters, and once this choice is made the remaining apprentices and masters are forced to pair in a unique way. Consequently, this case contributes 3 2 4 4 6 = 576 pairings.

Adding both cases yields 192 + 576 = 768 possible battle pair formations.

Statistics
462
teams received
22.7%
teams solved
01:16:55
average solving time

Problem 36

Let x, y be non-zero real numbers such that x + 1 y = 23 and y + 1 x = 343. Determine the value of x2y + 1 xy2 .

Solution

Answer:

323


Notice that

x2y + 1 xy2 = (xy + 1 xy ) (x + 1 y ) x 1 y.

Further,

xy + 1 xy = (x + 1 y ) (y + 1 x ) 2 = 3 2 2 = 4.

Hence,

x2y + 1 xy2 = 423 23 = 323.
Statistics
377
teams received
58.1%
teams solved
00:41:16
average solving time

Problem 37

Let ABCD be a cyclic quadrilateral with ∠ADB = 48 and ∠BDC = 56. A point X is chosen inside triangle ABC such that ∠XCB = 24, and the ray AX bisects ∠BAC. Find the measure of ∠CBX in degrees.

Note: A cyclic quadrilateral is a quadrilateral whose four vertices all lie on a single circle.

Solution

Answer:

38


The angles ∠ADB and ∠ACB are equal since they subtend the same arc. Hence

∠ACX = ∠ACB ∠XCB = ∠ADB ∠XCB = 48 24 = 24 = ∠XCB.

Therefore CX is the bisector of ∠ACB and X is in turn the common intersection of all three angle bisectors of ABC (known also as the incenter of triangle ABC).

PIC

Now we compute the desired angle:

∠CBX = ∠CBA 2 = 180∠BAC ∠ACB 2 = 180 56 48 2 = 38,

where we used that ∠BAC = ∠BDC, which follows (analogously to the very first angle equality) from the fact that they both subtend the same circular arc.

Statistics
327
teams received
59.3%
teams solved
00:11:55
average solving time

Problem 38

Nabionicula simplex has a very primitive brain divided into left and right hemispheres, each consisting of two types of cells: neurons and glia. No cell is connected to any other cell in the same hemisphere, but between each pair of cells from different hemispheres there is exactly one two-way connection. In one Nabionicula simplex there are 168 neuron–neuron connections, 48 glia–glia connections, and 191 neuron–glia connections. What is the total number of neurons in this specimen?

Solution

Answer:

29


Let n1 and g1 denote the number of neurons and glia in one of the hemispheres and n2 and g2 in the other one. We know that n1n2 = 168, g1g2 = 48, and n1g2 + n2g1 = 191. Therefore

(n1 + g1)(n2 + g2) = 168 + 48 + 191 = 407 = 11 37,

so, since there must be at least one cell of each type on each hemisphere, without loss of generality, we can state that n1 + g1 = 11. Likewise

(n1 g1)(n2 g2) = 168 + 48 191 = 25,

which, together with the fact that n1 is a divisor of 168 and g1 is a divisor of 48, easily implies that n1 = 8, g1 = 3, hence n2 = 1688 = 21, and the total number of neurons is n1 + n2 = 29.

Alternative solution. Let us use the notation as in the previous solution. The number n1g2 + n2g1 is odd, so one of the two summands is odd; without loss of generality, let it be n1g2. This implies that both n1 and g2 are odd. On the other hand, since 168 = 23 21 and 48 = 24 3, n2 must be divisible by 23 and g1 by 24. Therefore n2g1 is a multiple of 23 24 = 27 = 128, and as it is smaller than 191, it must equal 128, with n2 = 23 = 8 (and g1 = 24). We conclude that n1 = 1688 = 21, and the result follows.

Statistics
278
teams received
68.7%
teams solved
00:15:00
average solving time

Problem 39

Agnes has five identical straight trimino (“I”-shaped) tiles and wishes to form a continuous path on a 7 × 9 rectangular grid connecting the bottom-left corner to the top-right corner. Each trimino consists of one central square and two end squares, and the path must be formed so that any two consecutive triminos touch along exactly one shared grid edge, which must be a side common to an end square of each trimino. One such path is shown in the figure below. In how many distinct ways can Agnes form such a path?

PIC

Solution

Answer:

75


Because Agnes has only five triminoes, the path cannot ever move south or west: any such backward move would waste grid distance that cannot be recovered with only five pieces. Thus the endpoint of the growing path always progresses northward and/or eastward. We count the paths by filling a 7 × 9 table: In each grid square we write the number of trimino paths whose current endpoint (the free end square of the last trimino) lies in that square.

After placing the first trimino from the bottom-left corner, the endpoint must be exactly two squares away: either two to the right (horizontal first trimino) or two up (vertical first trimino). Therefore we place a 1 in the squares (0,2) and (2,0) (coordinates counted from the bottom-left).

Now fill the rest of the table moving from bottom-left toward top-right. To determine the value at a square (x,y), consider the ways a trimino can end there. A trimino ending at (x,y) may be vertical or horizontal, and in either case it must attach to the previous trimino at an end square. This gives four possible predecessor endpoints: (x,y 3) and (x 1,y 2) in the vertical case, and (x 3,y) and (x 2,y 1) in the horizontal case. Each of these corresponds to a valid way to extend an existing path by one trimino. Therefore, the value written in (x,y) is the sum of the values already written in the squares

(x 3,y),(x 2,y 1),(x 1,y 2),(x,y 3),

with any square outside the grid contributing 0.

PIC

After filling all squares this way, the value 75 in the top-right corner square is exactly the number of valid trimino paths from the bottom-left corner to the top-right corner.

Alternative solution. Place the five I-triminoes end-to-end starting at the bottom-left corner (0,0) in the following “skeletal” way: consecutive triminoes meet only at a corner (end-square corner to end-square corner). Each trimino advances the endpoint by either (+1,+3) (an “up” trimino) or (+3,+1) (a “right” trimino). After 5 triminoes the endpoint is (x,y) with x + y = 20. If U is the number of up triminoes and R the number of right triminoes, then U + R = 5 and (x,y) = (U + 3R,3U + R).

To turn the corner-touching chain into a valid path where consecutive triminoes share an edge, we “fix” each of the 4 joints between consecutive triminoes. Let the i-th joint be the connection between triminoes i and i + 1; at each joint we choose one of two operations: either shift the entire suffix of triminoes i + 1,i + 2,,5 one unit to the left, or shift that suffix one unit downward. This ensures that triminoes i and i + 1 share a full grid edge instead of just a corner.

Let be the total number of joints at which we choose a left shift, and let d be the total number of joints at which we choose a downward shift. Since there are exactly 4 joints, we have + d = 4. After performing all 4 shifts, the endpoint (x,y) of the skeletal chain is translated to (x ,y d). To obtain a valid path from (0,0) to the top-right corner (9,7), this final endpoint must satisfy (x ,y d) = (9,7).

Let us now check the six (U,R) cases:

  • (5,0): (x,y) = (5,15) cannot reach (9,7) by 4 left/down shifts.
  • (4,1): (x,y) = (7,13) is impossible to fix, too.
  • (3,2): (x,y) = (9,11) requires = 0, d = 4 (all shifts down). There are (5 3) = 10 skeletal chains and only 1 fix, giving 10 valid paths.
  • (2,3): (x,y) = (11,9) requires = 2, d = 2. There are (5 2) = 10 skeletal chains and (4 2) = 6 ways to choose which joints shift left (the rest shift down), giving 10 6 = 60 valid paths.
  • (1,4): (x,y) = (13,7) requires = 4, d = 0 (all shifts left). There are (5 1) = 5 skeletal chains and 1 fix, giving 5 valid paths.
  • (0,5): (x,y) = (15,5) is impossible to fix.

Therefore, the total number of valid paths is 10 + 60 + 5 = 75.

Statistics
238
teams received
33.2%
teams solved
00:24:53
average solving time

Problem 40

Let a, b, c, d be real numbers such that a + b + c + d = 2 and a2 a+2b + b2 b+2c + c2 c+2d + d2 d+2a = 2026. Find the value of

b2 a + 2b + c2 b + 2c + d2 c + 2d + a2 d + 2a.
Solution

Answer:

507


Let X = a2 a+2b + b2 b+2c + c2 c+2d + d2 d+2a = 2026 and Y = b2 a+2b + c2 b+2c + d2 c+2d + a2 d+2a.

Since we have a + 2b in the denominator, we can try to simplify it if we have a (a + 2b)(a 2b) = a2 4b2 as the numerator, and so on for the remaining fractions. Then:

X 4Y = a2 4b2 a + 2b + b2 4c2 b + 2c + c2 4d2 c + 2d + d2 4a2 d + 2a = (a 2b) + (b 2c) + (c 2d) + (d 2a) = = a b c d = (a + b + c + d) = 2.

From this we obtain X 4Y = 2, hence Y = 1 4(X + 2) = 2026+2 4 = 507.

Statistics
213
teams received
40.8%
teams solved
00:14:50
average solving time

Problem 41

In a cuboid box with a square base of side length 3 and height a, there are two ping-pong balls, each of radius 1. The first ball is positioned so that it touches two adjacent vertical faces of the box, the bottom face of the box, and the second ball. The second ball is positioned so that it touches the other two adjacent vertical faces of the box, the top face of the box, and the first ball. Determine the height a of the box.

Solution

Answer:

2 + 2


Denote by C1 and C2 the centers of the two balls, and let d be the horizontal distance between the two centers, i.e. the length of the projection of the segment C1C2 onto the top (or bottom) face of the box. Viewing the configuration from above, we obtain a square of side length 3, where C1 is at distance 1 from two adjacent sides and C2 is at distance 1 from the other two adjacent sides.

PIC

Hence, in this top view, the projections of C1 and C2 lie at opposite corners of a square of side length 1. Therefore, d = 2.

Next, consider the vertical plane perpendicular to the base that passes through C1 and C2. The intersection of this plane with the box is a rectangle of the sought height a, and the segment C1C2 lies in this plane. Let x denote the vertical distance between C1 and C2.

PIC

Since the two balls touch each other and each has radius 1, the distance between their centers is C1C2 = 2. In the right triangle with horizontal leg d and vertical leg x, we have C1C22 = d2 + x2, so x = 22 d2 = 2.

Finally, the first ball touches the bottom face and the second ball touches the top face, so the height of the box is the sum of the radius of the first ball, the vertical distance between the centers, and the radius of the second ball: a = 1 + x + 1 = 2 + 2.

Statistics
183
teams received
67.8%
teams solved
00:11:16
average solving time

Problem 42

In how many ways can a 3 × 3 table be filled with digits 0,1,,9 such that each cell contains exactly one digit, no digit is used more than once, and the six sums formed by the three rows and three columns are either all even or all odd? An example of a valid table in which all row and column sums are even is shown below:

1 2 3 5 4 7 6 0 8
Solution

Answer:

259200


Since 0 + 1 + + 9 = 45 is odd, omitting an odd digit yields an even sum over the whole table and hence all the row and column sums must be even. That can be arranged using 4 odd and 5 even digits only if one row and one column (5 cells) contain exactly the even numbers. Hence we can count all such tables by choosing the omitted odd digit (5 ways), then choosing the row and column with only even digits (3 3 = 9 ways), then placing the odd digits in any order (4! = 24 ways) and finally placing the even digits in any order (5! = 120 ways).

Similarly, if we omit an even digit, the sum of all three rows will be odd, and hence all rows and columns must yield odd sums. The only way to place five odd digits in a 3 × 3 table so that each row or column contains one or three of them is to put them in one row and one column. The number of tables in this case is computed analogously as in the previous case, only with interchanged roles of even and odd digits. Therefore the total number equals 2 5 9 24 120 = 259200.

Statistics
161
teams received
62.1%
teams solved
01:00:36
average solving time

Problem 43

The sum of four pairwise distinct positive integers a, b, c and d is 20000. Find the smallest possible value of lcm(a,b,c,d), where lcm denotes the least common multiple.

Solution

Answer:

9600


Let L = lcm(a,b,c,d) and let a > b > c > d. These numbers are divisors of L, i.e. L = aa1 = bb1 = cc1 = dd1 for some positive integers a1, b1, c1, d1. It is clear that a1 < b1 < c1 < d1. Therefore a1 1, b1 2, c1 3, d1 4. This means that

a L,b L 2 ,c L 3 ,d L 4 .

As a result,

20000 = a + b + c + d L (1 + 1 2 + 1 3 + 1 4 ) = 25L 12 ,

that is, L 12 2000025 = 9600.

To show that L = 9600 is attainable, it is enough to set a = 9600, b = 9600 2 , c = 9600 3 , and d = 9600 4 , which are all integers. The sum of these four numbers is 9600 (1 + 1 2 + 1 3 + 1 4 ) = 20000. Hence 9600 is the sought minimum value of L.

Statistics
139
teams received
33.8%
teams solved
00:20:27
average solving time

Problem 44

Let a1,a2,a3, be a sequence defined by an = n2 1.001n. Find the value of n at which the sequence attains its maximum.

Solution

Answer:

2001


Notice that

an+1 an = (n + 1)2 1.001n2 = 1000(n + 1)2 1001n2 .

Then, an+1 > an or an+1an > 1 yields 2000n + 1000 > n2 and therefore, n(n 2000) < 1000. It is easy to verify that this condition holds when n 2000, as the left side would be non-positive, and fails for n 2001. Thus, the sequence is strictly increasing up to 2001 and, analogously, strictly decreasing from then on, that is a1 < a2 < < a2000 < a2001 > a2002 > . Hence, the maximum of the sequence occurs at a2001.

Statistics
125
teams received
58.4%
teams solved
00:15:39
average solving time

Problem 45

Five friends are choosing seats for a show. They all want to sit in one row, which has the following layout:

PIC

That is: a wall, four blocks of six seats separated by three aisles, and a second wall. The friends are shy, so they want to choose five seats such that, even if all others are occupied, they can leave their seats without having to ask any strangers to stand up. How many such five-element sets of seats exist?

Solution

Answer:

252


The condition “they can all leave without asking anyone to stand up” means that the chosen seats must form connected clusters adjacent to the aisles.

Place the five friends in a row. We want to separate them into three clusters (some of them possibly empty), corresponding to the three aisles. To do so, we insert 2 3 1 = 5 separators:

  • the odd separators represent the aisles themselves,
  • the even separators represent nonempty blocks of empty seats in blocks that are not adjacent to the walls.

We claim that these configurations are in one-to-one correspondence with all the valid seat choices. Take one such configuration, e.g. the sequence

̲F̲FF̲FF,

where F stands for a friend, ̲ for an aisle, and for a block of empty seats. Starting from the left, it reads as follows: No seats are chosen from the first block. In the second block, one seat adjacent to the second aisle is chosen. In the third block, the two rightmost seats are chosen and, finally, the two leftmost seats are chosen in the last block of seats. On the other hand, there is a unique way to encode any valid seat choice. If the clusters around adjacent aisles touched, i.e. a full block was occupied by friends, there would be several options to put the corresponding separator, but since there are five friends and six seats in each block, its position is always unique.

We are counting arrangements of five friends (indistinguishable as we do not care about which friend sits where within the chosen set of seats) and five separators (they have two different meanings, but these are fully determined by their order, so no further distinction for the sake of counting is in place). Hence we are choosing 5 positions out of 10 which gives

( 5 + 5 5) =( 10 5) = 252

possibilities.

Statistics
107
teams received
56.1%
teams solved
00:12:35
average solving time

Problem 46

Consider an equilateral triangle with sidelength 4. A circle of radius 1 is centered at each vertex of the triangle. Determine the radius of a larger circle that is tangent internally to two of these smaller circles and externally to the third one.

PIC

Solution

Answer:

33+1 2 = 43 31


Denote the equilateral triangle by ABC and let the required circle have center O and radius r. Suppose it is internally tangent to the circles at A and B, and externally tangent to the one at C. The altitude of the triangle is h = 3 2 4 = 23. Since OA = OB, the point O lies on the perpendicular bisector of AB. Let M be the midpoint of AB, so AM = 2 and CM = h.

PIC

From the tangency conditions, OA = OB = r 1 and OC = r + 1. As O lies on line CM, we have

OM = OC CM = r + 1 h.

(This assumes that O lies outside triangle ABC. If instead O were inside, then OM = CM OC rather than OM = OC CM; in either case we further use only OM2, which is unchanged.)

In the right triangle OMA, the Pythagorean Theorem implies

OA2 = OM2 + AM2or(r 1)2 = (r + 1 h)2 + 22.

Expanding and simplifying, we obtain

r = h2 2h + 4 2(h 2) .

Substituting h = 23 yields the desired result r = 43 31 = 33+1 2 .

Statistics
94
teams received
48.9%
teams solved
00:15:26
average solving time

Problem 47

Consider two rooms, one full of dwarves, each 1.2m tall, and the other full of cyclopes, each 4m tall. After 35 cyclopes and 24 dwarves moved from their room to the other one, the average height in both the rooms became exactly the same. What was the smallest total number of creatures for this to happen?

Solution

Answer:

117


Let d and c be the total number of dwarves and cyclopes, respectively. After the switch, we have d 24 dwarves and 35 cyclopes in the first room, and 24 dwarves and c 35 cyclopes in the second. For convenience, set d1 = d 24, c1 = 35, d2 = 24 and c2 = c 35, and denote the heights of a dwarf and a cyclopes by hd and hc, respectively. The average height will be

d1hd + c1hc d1 + c1 = d2hd + c2hc d2 + c2 .

Simplifying this equation, we obtain

(hc hd)(c1d2 d1c2) = 0.

Since hc is different from hd, this implies c1d2 d1c2 = 0 or c1 d1 = c2 d2 . Intuitively, this makes sense: in order for the average heights to be the same in both rooms, the ratio of dwarves to cyclopes must also be the same; the actual heights are irrelevant. Using the known values of c1 and d2, this gives

d1c2 = c1d2 = 35 24 = 840.

Our objective is to minimize the total number of creatures d + c, which is equivalent to minimizing d1 + c2, since d + c = d1 + c2 + 24 + 35. For two positive numbers with a fixed product, their sum is minimized when the numbers are as close as possible; this follows e.g. from the identity (d1 + c2)2 = (d1 c2)2 + 4d1c2. Hence we seek a factorization of 840 into two integers as close as possible. We easily find the optimal choice 840 = 28 30.

Therefore d1 and c2 are 28 and 30 (in either order), and the minimal total number of creatures is d + c = 28 + 30 + 24 + 35 = 117.

Statistics
78
teams received
30.8%
teams solved
00:23:59
average solving time

Problem 48

Six pirates enter a tavern and, after a chaotic shuffle, take seats at random around a round table, each having an inherent ferocity rank from 1 to 6 (all distinct) that determines every duel: the higher-ranked pirate always wins. To decide who commands the crew, they follow a clockwise challenge ritual: in each round, one remaining pirate is chosen at random to challenge the nearest remaining pirate in the clockwise direction, skipping any empty seats; the weaker pirate is eliminated and the stronger stays seated. After five rounds only one pirate remains; what is the probability the final duel is between the two strongest pirates, ranks 6 and 5?

Solution

Answer:

715


Seat the six pirates at random around the table, and fix attention only on pirates with ratings 5 and 6 (since 6 can never be eliminated). At any moment, list the remaining pirates clockwise as 5,A1,,Aa,6,B1,,Bb, where a is the number of surviving pirates strictly between 5 and 6 clockwise from 5 to 6, and b is the number strictly between 6 and 5 on the other arc. Let f(a,b) be the probability that the final duel is between 5 and 6 given this configuration. It is clear that this probability depends only on the numbers a and b, not on the specific identities or ranks of the pirates Ai and Bi. Indeed, every Ai and Bi has rank at most 4, so any duel involving 5 or 6 eliminates the weaker pirate regardless of which Ai or Bi it is, while duels among the Ai’s (respectively among the Bi’s) merely reduce the size of that block by one.

If a = 0 or b = 0, then 5 and 6 are adjacent with n = a + b + 2 pirates left. In that situation, at each turn exactly one choice of challenger (namely 5 or 6, depending on who is on the right) forces the duel 5 vs 6 immediately and eliminates 5; all other choices remove someone else. Hence the probability that 5 survives until the last duel telescopes as

f(a,0) = f(0,b) = n 1 n n 2 n 12 3 = 2 n = 2 a + b + 2.

Assume now a,b 1, and keep n = a + b + 2 for the number of remaining pirates. Consider the clockwise block of pirates starting at 5 and stopping at the pirate immediately before 6; this block has exactly a + 1 members, namely 5,A1,,Aa. If the randomly chosen challenger lies in this block, then the ensuing duel occurs within this block (the challenged pirate is the next clockwise pirate, still inside the block, except for Aa who challenges 6), and in every case the eliminated pirate is one of A1,,Aa. Thus choosing the challenger from this block decreases a by 1. By the same reasoning, the clockwise block starting at 6 and stopping immediately before 5 has b + 1 members, and choosing the challenger from that block decreases b by 1. Since the choice of challenger is uniform among the n remaining pirates, we obtain, for a,b 1,

f(a,b) = a + 1 n f(a 1,b) + b + 1 n f(a,b 1).

Initially a + b = 4. Using the boundary values f(0,4) = 2 6 = 1 3, f(0,3) = 2 5, f(0,2) = 1 2, f(0,1) = 2 3 and symmetry f(a,b) = f(b,a), the recurrence gives f(1,1) = 2 3, f(1,2) = 3 5, f(1,3) = 8 15, and f(2,2) = 3 5. Since the initial seating is uniform, the clockwise gap a between 5 and 6 is uniformly distributed on {0,1,2,3,4}, so the sought probability is

1 5(f(0,4)+f(1,3)+f(2,2)+f(3,1)+f(4,0)) = 1 5 (1 3 + 8 15 + 3 5 + 8 15 + 1 3 ) = 7 15.

Alternative solution. We will solve the problem in a more general form for n pirates instead of six. Let pn denote the probability that the last two surviving pirates are n and n 1. Our goal is to prove the recurrent formula

pn = (1 2 n(n 1) )pn1 (♠)

valid for n 3.

Consider the first step of the ritual. Pirate n 1 is eliminated immediately with probability 2 n(n1): indeed, the probability that n and n 1 sit next to each other is 2 n1, since if the pirates are seated starting from pirate n, then pirate n 1 has n 1 possible places to choose from, and exactly 2 of them are next to n. Once they are adjacent, the duel between n and n 1 happens with probability 1 n. Hence the probability is

2 n 1 1 n = 2 n(n 1).

Thus, with probability 1 2 n(n1), the first eliminated pirate is one of 1,,n 2. In that case, the remaining n 1 pirates are again seated around the table in a random circular order, with all such orders equally likely: if pirate k is eliminated, then any given resulting circular order can arise in exactly 2(n k) ways, since k must have sat next to and dueled one of the n k stronger pirates , either by challenging or by being challenged by . This number depends only on k and not on the resulting order, so after relabeling the survivors as 1,2,,n 1, we obtain the original problem with n 1 pirates. This proves the recurrence ().

It remains to compute p6. Since p2 = 1, repeated use of () gives

p6 = 14 15 9 10 5 6 2 3 = 7 15.

Therefore, the probability that the final duel is between pirates 6 and 5 is 7 15. More generally, one can also prove by induction from () that

pn = n + 1 3(n 1).
Statistics
62
teams received
38.7%
teams solved
00:13:59
average solving time

Problem 49

An L-shaped tetromino, formed by four congruent squares joined edge to edge, is inscribed in an isosceles right triangle as shown. What is the ratio of the area of the tetromino to the area of the triangle?

PIC

Solution

Answer:

80169


The points are named as shown in the diagram. If we set the side length of each of the small squares to 1, we only have to compute the length of one side of the triangle ABC, e.g. the hypotenuse AC.

PIC

Using the auxiliary line EF, we get the right triangle EFK with ∠EKF = 90 and the side lengths EK = 1,KF = 2, and EF = 5. Since GL = 2 and LF = 1 and ∠FLG = 90, the triangles EFK and FGL are congruent. From this we obtain GF = EF = 5. Let α be ∠LGF. Then ∠KFE = α as well and we conclude ∠GFE = 90 since α supplements ∠GFL to 90. This, however, means that triangle FEC is an isosceles right triangle with side length FC = 5. Now we introduce a second auxiliary line by dropping a perpendicular from point D to line AC creating point M on line AC. Due to ∠LGF + ∠MGD = 90, we get ∠GDM = α and therefore triangle MDG is similar to triangle FGL with a scaling factor 5. Therefore the side lengths of triangle MDG are MG = 1 5,MD = 2 5, and DG = 1. Since triangle MAD is an isosceles right triangle as well, we finally get AM = 2 5. Now we have

AC = AM + MG + GF + FC = 2 5 + 1 5 + 5 + 5 = 3 + 2 5 5 = 13 5.

Therefore the area of triangle ABC is

1 2AB2 = 1 2 (AC 2 )2 = 1 2 ( 13 10 )2 = 169 20

and the ratio sought is 4 169 20 = 80 169.

Statistics
52
teams received
26.9%
teams solved
00:22:55
average solving time

Problem 50

Consider the sequence (an)n=1 defined by a1 = a2 = a3 = 1 and for n 1 by an+3 = 3an+2 + 3an+1 + 3an. What is the remainder when a22 is divided by 49?

Solution

Answer:

11


The term a22 is a sum of powers of 3, whose value modulo 49 can be found using Euler’s Theorem: since gcd(3,49) = 1 and φ(49) = 42, the theorem ensures that

3an 3anmod42(mod49).

Thus to compute a22 = 3a21 + 3a20 + 3a19(mod49), it is enough to know a21,a20,a19(mod42). Using the Chinese remainder theorem, this is equivalent to finding these values modulo 6 and 7.

First, for n 4 each term an is a sum of three powers of 3, hence odd and divisible by 3, so an 3(mod6). Since 36 1(mod7) (Euler’s Theorem again), we infer 3an 33(mod7) for n 4. Taking n 7 (so that n 1,n 2,n 3 4), we have

an = 3an1 + 3an2 + 3an3 33 + 33 + 33 4(mod7).

Combining these congruences via the Chinese remainder theorem gives an 39 3(mod42) for n 7. Recalling Euler’s Theorem for the last time, this means 3an 33(mod49) for n 7, where the negative exponent denotes a power of the modular inverse. Finally,

a22 = 3a21 + 3a20 + 3a19 33 + 33 + 33 = 32 = 91 11(mod49),

since 9 11 = 99 1(mod49). Hence the sought remainder is 11.

Statistics
39
teams received
28.2%
teams solved
00:19:55
average solving time

Problem 51

Max starts with an empty fuel tank at the beginning of an infinite road. For every integer n 0, there is a trader located n2 miles from the starting point. Max can buy an integer number of fuel units from each trader. However, traders are reluctant to sell large amounts of fuel, so the cost per unit increases with each additional unit purchased: at each trader, the first unit costs $1, the second unit costs $2, the third unit costs $3, and so on. Each fuel unit allows Max to drive 1 mile. Both the traders’ supply and Max’s fuel tank capacity are unlimited. Given a budget of $730, what is the maximum distance that Max can travel along the road?

Solution

Answer:

123


To reach the trader at n2 miles, one can buy fuel from n earlier traders. The minimum theoretical cost is achieved by purchasing exactly n units from each trader, since any non‐uniform distribution increases the total cost.

However, we must verify that the plan “at each trader I meet, I buy n units of fuel” actually works (i.e. it allows Max to successfully reach mile n2); it must not happen that he runs out of fuel before reaching some earlier trader. We prove by a simple induction that this plan does not fail. The case n = 0 is clear: no fuel needs to be purchased to reach mile 0. Now assume we already know that it is possible to reach mile n2 by buying n units at each of the n traders. Then, if we instead buy n + 1 units, we certainly will not run out of fuel before mile n2. Hence we also manage to buy n + 1 units from the trader at n2, and after these n + 1 purchases of n + 1 units, we will successfully reach mile (n + 1)2.

This argument shows that the cost to reach n2 miles is at least

Cn = n(1 + 2 + + n) = nn(n + 1) 2 .

Since C11 = 726 730 < 936 = C12, it follows that 112 miles can be reached with the given budget, but 122 miles cannot. Using the remaining $4 to buy 2 more units at 112 miles allows reaching 123 miles; however, reaching 124 miles the same way would be $2 over budget. These constructions are cost‐optimal for 123 and 124: there is no point in buying more fuel than needed from the last trader, and increasing the total units purchased before 112 miles costs at least $12 more per extra unit, even if perfectly balanced.

Statistics
34
teams received
35.3%
teams solved
00:16:17
average solving time

Problem 52

Let ABCDEF be a regular hexagon with area 420. Let M, N, and P be the midpoints of sides DE, FA, and BC, respectively. The segments AM, BM, CN, DN, EP, and FP are drawn, enclosing a shaded region. Determine the area of this region.

PIC

Solution

Answer:

36


The shaded region can be decomposed into six congruent triangles; we will compute the area of one such triangle. Let O be the center of the hexagon, X the intersection of BM with CN, and Y the intersection of BM with PE (so that our goal is to find the area of triangle OXY ). Moreover, we introduce some auxiliary points: Q is the midpoint of CD, V the intersection of AD with CN, and W the intersection of PM with QN. We will show that OX : OP = 2 : 5 and OY : OQ = 2 : 7.

PIC

Since triangles NAV and CDV are similar and NA = 1 2CD, we have AV : V D = 1 : 2, hence OV = 1 3OA. Now triangle OV X is similar to PCX, and since PC = 1 2BC = 1 2OA, we get OV : PC = 2 : 3, which is also equal to OX : PX. Therefore OX : OP = 2 : 5.

To see that OY : OQ = 2 : 7, use the similarity of triangles OBY and WMY with WM = 3 4OB to conclude that OY : Y W = 4 : 3. Combining this with OW = WQ easily gives OY : OQ = 2 : 7.

Let us denote by square brackets the area of a triangle. Triangles OXY and OPQ share angle ∠POQ, so

[OXY ] [OPQ] = OX OP OY OQ = 2 5 2 7 = 4 35.

Moreover, triangle OPQ is equilateral with side 3 2 times the side of ABO, so [OPQ] = 3 4[ABO]. Therefore

[OXY ] [ABO] = 4 35 3 4 = 3 35.

Since the shaded region consists of six copies of OXY and the hexagon consists of six copies of ABO, the same ratio holds. We conclude that the area of the shaded part is 3 35 420 = 36.

Statistics
25
teams received
28.0%
teams solved
00:23:55
average solving time

Problem 53

Adele is a master of algebraic manipulation, so she has taken all the expressions ± a ± b ± c ± d (altogether, 16 expressions for all the possible sign combinations) and multiplied them together, obtaining a polynomial in the variables a, b, c, d. She then discarded all terms in which at least one of the variables was missing. What was the sum of the coefficients of the remaining terms?

Solution

Answer:

328


Let P be the polynomial from the statement (before discarding any terms). By assigning 1 to all four variables, the product contains (1 + 1 1 1) = 0 as a factor, hence the sum of all coefficients of P equals 0. Let us calculate the sum of the coefficients of the discarded monomials. We will calculate this by inclusion and exclusion.

To begin computing the sum of the coefficients of monomials missing at least one variable, we consider the case where a fixed variable is set to zero and then sum over all four choices, thereby counting each monomial lacking a variable at least once. To sum the coefficients of the terms not containing (for example) d, we compute the value of P with a = b = c = 1 and d = 0, obtaining

P(1,1,1,0) =((1+1+1)(1+11)(11+1)(111)(1+1+1)(1+11)(11+1)(111))2 = 92 = 81.

Summing over the four choices of the missing variable gives 4 81 = 324, but in this sum we count twice each term with only two variables, so we have to subtract P(1,1,0,0) = 0 six times, as there are six pairs of variables. Finally, we have to add back the terms with only one variable, so we add P(1,0,0,0) = 1 four times. Altogether, these coefficients sum up to 324 + 4 = 328; since the total sum of all coefficients of P is zero, the sum over the complementary set of monomials (those containing all four variables) is therefore 328.

Statistics
18
teams received
16.7%
teams solved
00:21:47
average solving time

Problem 54

Nicky has 9000 congruent equilateral triangles. How many different quadrilaterals can she assemble from them by arranging all 9000 triangles without overlap into a single quadrilateral? Quadrilaterals that are congruent are considered identical.

Solution

Answer:

30


A vertex made from the joining of equilateral triangles can only have an angle of amplitude 60 or 120. Since the sum of the inner angles of a quadrilateral must be 360, the four angles must be of 60,60,120 and 120. There are two types of quadrilaterals which can be assembled: parallelograms and isosceles trapezoids, depending on whether the equal angles are opposed or adjacent.

As for parallelograms, if its sides are a and b, then it is composed of 2ab triangles (it can be thought as ab parallelograms composed of just 2 triangles), so we’re looking for pairs {a,b} such that ab = 4500. There are 18 such pairs (as there are 36 divisors).

For trapezoids, note that it can be viewed as a difference of two large equilateral triangles. A triangle of side n consists of n2 triangles (seeing it split into layers, it is the sum of the first n odd numbers), so we want a2 b2 = (a + b)(a b) = 9000, where a represents the longer base of the trapezoid and b the shorter. We’re again looking for pairs of divisors, but in this case both a + b and a b have to be even for the system of equations to have an integer solution. The number 9000 has 24 even divisors such that the quotient is even, too (they correspond to divisors of 90004) and those lead to 12 valid pairs of a + b and a b, which correspond to 12 valid pairs for a and b.

In total, there are 18 + 12 = 30 possible quadrilaterals.

Statistics
14
teams received
28.6%
teams solved
00:25:26
average solving time

Problem 55

Alex hung a Christmas light string with 10 bulbs in the window, but unfortunately, not all the bulbs were lit. It is known that there are no four consecutive bulbs alternating between lit and unlit (i.e., lit, unlit, lit, unlit or unlit, lit, unlit, lit). How many different possible configurations could there be?

Solution

Answer:

548


Denote a lit bulb by 1 and an unlit bulb by 0, so the problem is to count binary sequences of length 10 that do not contain 0101 or 1010 as a contiguous block. Define a transformation that flips the entries in all even positions (replacing xi by 1 xi for even i and leaving odd i unchanged); applying this map twice produces the original sequence, hence it is a bijection. Moreover, this flip turns an alternating block 0101 or 1010 into a constant block 0000 or 1111, and conversely. Therefore the original sequences are in bijection with length-10 binary sequences containing no block of four consecutive equal bits, which is more convenient to count.

Let Bn denote the number of length-n binary sequences containing no block of four consecutive equal bits; we claim that for n > 3 these numbers satisfy Bn = Bn1 + Bn2 + Bn3. Given a valid sequence of length n, look at the maximal trailing block of equal digits; by the constraint its length is 1, 2, or 3, and these three cases are disjoint. If the trailing block has length k {1,2,3}, deleting the last k digits yields a valid sequence of length n k. Conversely, from any valid sequence of length n k, appending the unique length-k block that alternates with its last digit (i.e. first append the opposite digit, then continue with that same digit for a total of k appended digits) reconstructs a valid length-n sequence whose trailing block has length k. Thus valid sequences of length n are in bijection with valid sequences of lengths n 1, n 2, and n 3, giving the recurrence.

For n 3 the constraint is vacuous, so B1 = 2, B2 = 4, and B3 = 8 (all length-n binary sequences are allowed). Using the recurrence Bn = Bn1 + Bn2 + Bn3, we compute successively B4 = 14, B5 = 26, B6 = 48, B7 = 88, B8 = 162, B9 = 298, and finally B10 = 548.

Statistics
9
teams received
66.7%
teams solved
00:14:34
average solving time

Problem 56

Solve the following equation for a positive integer a:

(23 + 232 4 2 )5 = (a + a2 4 2 )2.
Solution

Answer:

2525


Throughout the solution, we assume a 2, since for a = 1 the right-hand side is undefined. Note that

23 + 232 4 2 = 23 + 521 2 = (5 + 21 2 )2

Since a + a2 4 > 0, the original equation reduces to

a + a2 4 2 = (5 + 21 2 )5.

This equality can be further expanded as

a + a2 4 = 55 +( 5 2) 53 21 +( 5 4) 51 212 16 + (5 1) 54 21 +( 5 3) 52 (21)3 + (21)5 16 = 3125 + 10 2625 + 25 441 16 + (55 + 21 250 + 212) 21 16 = 2525 + 551 21.

Comparing the rational components gives a candidate a = 2525. To verify that this is really a solution, it suffices to plug a = 2525 into a2 4, which results in 25252 4 = 6375621 = 5512 21 as desired. Finally, the solution is unique: for a 2 the expression a + a2 4 is strictly increasing (both terms increase with a), so the equation can have at most one positive integer solution for a.

Alternative solution. Let α = 1 2(23 + 232 4). Since α is a root of t2 23t + 1 = 0 with the other root being α1, we have α + α1 = 23.

Write β = 1 2(a + a2 4). Then β is a root of t2 at + 1 = 0, so as in the previous case, β + β1 = a. Since we are restricted to positive values of a, it follows that β has to be positive as well.

The given equation is α5 = β2. Let x = β15 (so x > 0). Then x2 = α and hence x2 + x2 = 23. Set y = x + x1; then y > 0 and y2 = x2 + x2 + 2 = 25, so y = 5.

Our goal is to find a = x5 + x5; to this end, we will expand

y5 = (x + x1)5 = (x5 + x5) + 5(x3 + x3) + 10(x + x1),

so

a = y5 5(x3 + x3) 10y.

It remains to express x3 + x3 in terms of y, which can be done in a similar fashion:

y3 = (x + x1)3 = (x3 + x3) + 3(x + x1),

hence

x3 + x3 = y3 3y.

Combining this with the previous equation, we obtain a = y5 5y3 + 5y, which equals 2525 after substituting y = 5.

Statistics
7
teams received
14.3%
teams solved
00:23:08
average solving time

Problem 57

In right triangle ABC with right angle at C, a point D lies on segment BC such that BD = 9 and DC = 5. If further ∠ADC = 3∠BAD, determine the length of AB.

Solution

Answer:

21


Straightforward angle chasing shows that ∠ABD = 2∠DAB. Draw the angle bisector of ∠ABD, meeting AD at E. Since BE bisects ∠ABD, we have ∠ABE = ∠EBD = ∠DAB. Thus AE = EB, and triangles DBE and DAB are similar. From the similarity, DB : DA = DE : DB = BE : AB.

PIC

Let AB = a, AE = EB = b, and AD = c. Then DE = c b, and the proportions give

9 c = b a = c b 9 .

Hence, c2 = bc + 81 and bc = 9a, which imply c2 = 9a + 81.

Since triangles ACD and ABC are right-angled at C, we infer

AC2 = AB2 BC2 = a2 (9 + 5)2 = a2 196,

and also

AC2 = AD2 DC2 = c2 25.

Equating these expressions and using c2 = 9a + 81, we obtain

a2 196 = 9a + 56ora2 9a 252 = 0.

This equation has only one positive root: a = 21.

Statistics
6
teams received
0.0%
teams solved
-
average solving time