Change language

Problems and solutions

Náboj Math 2015

Problem 1

Little Peter is a cool guy, so he wears only pairs of socks consisting of two socks of different colours. There are 30 red, 40 green, and 40 blue socks in his wardrobe in an unlighted cellar room. Peter takes one sock after the other out of the wardrobe without being able to recognize its colour. What is the minimum number of socks he has to take out if he needs to get eight two-coloured pairs of socks? Note that one single sock must not be counted in two different pairs.

Solution

Answer:

48


If Peter pulls out all the green socks and seven red socks, he cannot form eight pairs as desired, so 47 is not sufficient. But if he takes out 48 socks, there are at least 48 3 = 16 socks of one colour and at least 48 40 = 8 ones not having this colour among them, which enables him to form eight two-coloured pairs of socks.

Statistics
236
teams received
97.9%
teams solved
00:13:20
average solving time

Problem 2

Assume that x and y are positive integers satisfying x2 + 2y2 = 2468. Find x if you know that there is only one such pair (x,y) and 1234 = 282 + 2 152.

Solution

Answer:

30


Using the given equality 1234 = 282 + 2 152, we get

2468 = 2(282 + 2 152) = (2 15)2 + 2 282.

Since we know that there is only one such pair, we obtain x = 30.

Statistics
236
teams received
69.9%
teams solved
00:38:18
average solving time

Problem 3

A digital watch displays time in hours and minutes using the twenty-four hour time format. How many minutes per day can one see the digit 5 on the display?

Solution

Answer:

450


There are two hours during which the digit five is displayed all the time: 5 and 15. That makes 120 minutes. In the rest of the day, five can be seen during the last ten minutes of each hour (22 10 = 220 minutes) and then five times during the remaining fifty minutes (22 5 = 110 minutes). To sum up, five is shown exactly 450 minutes.

Statistics
236
teams received
99.6%
teams solved
00:14:11
average solving time

Problem 4

A big rectangle with perimeter 136cm is divided into seven congruent rectangles as in the picture.

PIC

What is the area of the big rectangle in cm2?

Solution

Answer:

1120


Since the side lengths of the small rectangles are in ratio 2 : 5, let us denote them by 2x and 5x. The side lengths of the big rectangle are 10x and 7x, hence 2 (10x + 7x) = 34x is the perimeter of the big rectangle. This yields x = 4cm, thus the area is 10 7 42cm2 = 1120cm2.

Statistics
236
teams received
99.6%
teams solved
00:19:20
average solving time

Problem 5

A box of chocolates has the shape of an equilateral triangle of side length scm. There are 2n chocolates in the shape of equilateral triangles, which tightly fill the box: n of side length 1cm and n of side length 2cm. What is the smallest possible value of s?

Solution

Answer:

10


Let a be the area of a small chocolate, i.e. the one with side length 1cm. Then the area of a big chocolate is 4a, the total area of all chocolates is na + 4na = 5na, and the area of the box is s2a as the shape of the box is just the shape of a small chocolate stretched by factor s in all directions. It follows that 5n = s2, so s is a multiple of 5.

It can be proven that it is impossible to fit five big chocolates in a box of side length 5cm, so s5. However, one can easily find a composition of 20 small and 20 big chocolates inside a box of side length 10cm.

PIC

Statistics
236
teams received
83.5%
teams solved
00:45:44
average solving time

Problem 6

Little Peter has grown up, so now he wears pairs of socks consisting of two socks of the same colour. He has also got many new socks, so there are currently 20 brown, 30 red, 40 green, 40 blue, 30 black, and 20 white socks in his wardrobe. However, the wardrobe is still situated in an unlighted cellar room. What is the minimum number of socks Peter has to take in order to get eight pairs of socks, if he cannot recognize their colours during the procedure? Note that one single sock must not be counted in two different pairs.

Solution

Answer:

21


On one hand, every number of socks chosen is the sum of an even number of socks, which are used to build pairs of socks, and a certain number of unpaired socks, which can be at most six due to the number of colours. If Peter takes 21 socks out of his wardrobe, there cannot be six unpaired socks among them because 21 6 = 15 is not even. Thus there are at most five single socks and the remaining socks form at least 215 2 = 8 pairs. On the other hand, it does not suffice to take 20 socks because Peter could have taken seven pairs of white socks and six single socks, one of each colour. It follows that Peter has to take at least 21 socks out of his wardrobe.

Statistics
236
teams received
93.2%
teams solved
00:26:35
average solving time

Problem 7

A square and a regular pentagon are inscribed in the same circle and they share a vertex. What is the largest interior angle of the polygon which is the intersection of the two polygons?

Solution

Answer:

153


Denote the vertices as in the picture. Then the polygon AB1B2C1C2D1D2 is the intersection of the two given polygons.

PIC

Since the figure is symmetric with respect to the line AC, it suffices to check the interior angles at A, B1, B2, and C1. Clearly, the first one is 90 and the last one is 135. As B2D1 is parallel to XY , we have D1B2B1 = ∠Y XW = 108, and since C1B2D1 = ∠CBD = 45 (B2D1 BD), the angle at B2 is 153. Finally, triangle B1BB2 is right-angled, from which we easily obtain that the angle at B1 is 117. Thus the largest angle is 153.

Statistics
236
teams received
63.1%
teams solved
00:43:07
average solving time

Problem 8

The circle 1 has diameter 48mm. What diameter should the circle 2 have to make the whole mechanism work?

PIC

Solution

Answer:

20mm


Having counted the numbers of teeth, one can observe that one full rotation of wheel 1 forces 20 15 = 4 3 of a full circle of the double-wheel. Similarly, when the double-wheel performs one full rotation, wheel 2 covers 18 10 = 9 5 of a full circle. Hence whenever wheel 1 rotates one full circle, wheel 2 rotates 4 3 9 5 = 12 5 of the full circle. The circumference of circle 2 must therefore be 5 12 times the circumference of circle 1. The ratio of circumferences equals the ratio of diameters, which allows us to compute the diameter of circle 2 as 5 12 48mm = 20mm.

Statistics
236
teams received
61.9%
teams solved
00:43:14
average solving time

Problem 9

For his sixty-two-day summer holiday in July and August, Robert had prepared a precise plan on which days he would lie and on which he would tell the truth. On the k-th day of the holiday (for each k from 1 to 62), he reported that he had planned to lie on at least k days. How many of these statements were lies?

Solution

Answer:

31


Observe that if Robert was telling the truth on one day, then he must have been doing so on all the previous days. If he was telling the truth only for k < 31 days, it would contradict the fact that he was lying for 62 k > 31 days. Similarly, telling the truth for more than 31 days would result in lying too little. We infer that Robert lied on exactly 31 days.

Statistics
236
teams received
76.3%
teams solved
00:42:34
average solving time

Problem 10

In a game of battleship, our opponent has hidden an aircraft carrier, represented by a 5 × 1 or 1 × 5 block, somewhere inside a 9 × 9 cell grid. What is the smallest number of shots, i.e. choices of a cell in the grid, that is needed to ensure that we have hit the carrier at least once?

Solution

Answer:

16


The decomposition of the 9 × 9 cell grid in figure 1 shows that 16 shots are necessary since every 5 × 1 rectangle must be hit by at least one shot.

PIC

But 16 shots are sufficient as well, as we see from figure 2.

PIC

Therefore 16 is the correct answer.

Statistics
234
teams received
96.2%
teams solved
00:17:24
average solving time

Problem 11

What is the maximum possible value of a common divisor of distinct positive integers a, b, c satisfying a + b + c = 2015?

Solution

Answer:

155


Since 5 13 31 = 2015 = a + b + c = gcd(a,b,c) (a0 + b0 + c0) for some distinct positive integers a0, b0, c0, we obtain a0 + b0 + c0 6. Hence gcd(a,b,c) can be at most 5 31 = 155. We can reach the maximum by taking any distinct positive integers that sum up to 13. For instance, a0 = 1, b0 = 5, c0 = 7 yield a = 1 155, b = 5 155, c = 7 155.

Statistics
449
teams received
54.6%
teams solved
00:35:18
average solving time

Problem 12

A train supplying an ironworks consists of a locomotive (which is always in the front) and six carriages, each carrying either coal or iron ore. Adam wanted to take a picture of the train, but he failed to capture the whole train, so only an iron ore carriage directly followed by two coal carriages was visible in the photo. The carriages were not completely symmetric, so it was clear that the ore carriage was the first one of these three. How many different trains can be photographed so that one obtains the same picture as Adam did?

Solution

Answer:

31


There are four possibilities where the photographed I-C-C carriage sequence can be, and for each of them there are 23 ways to complete the train. However, this results in counting the train I-C-C-I-C-C twice. Thus the number of different trains is 4 8 1 = 31.

Statistics
440
teams received
78.2%
teams solved
00:36:06
average solving time

Problem 13

An object built from several identical cubes looks like ‘1’ from behind, and like ‘3’ from above (see the picture). How many cubes can be seen from the right if we know that the object contains maximum possible number of cubes?

PIC

The figure below shows a cube, its back view and its top view, respectively.

PIC

Solution

Answer:

17


The structure can obviously fit in a box that is two cubes wide, five cubes high and five cubes long. Let us divide it in half and analyse its two 1 × 5 × 5 parts separately. If we look at the structure from the front, we can see mirror ‘1’. Hence in the right part, there is one square visible from the front and five squares visible from above. The only way to achieve that is to put five cubes in one row. Similarly for the left part, there are five squares visible from the front and three squares visible from above, so we get the maximum number of cubes if we place five cubes in each of the three columns.

The resulting structure looks like the one in the following picture. If we look at it from the right, we can see 17 cubes.

PIC

Statistics
429
teams received
85.1%
teams solved
00:32:13
average solving time

Problem 14

We say that a positive integer n is delicious if the sum of its digits is divisible by 17 and the same holds for n + 10. What is the smallest delicious number?

Solution

Answer:

7999


Denote by Q(r) the sum of digits of r. If the tens digit of n differs from 9, then we have Q(n + 10) = Q(n) + 1. Hence the tens digit of n has to be 9. If the hundreds digit differs from 9, we have Q(n + 10) = Q(n) 8, but if the hundreds digit is 9 and the thousands digit is not, we get Q(n + 10) = Q(n) 17, so we can make both Q(n) and Q(n + 10) divisible by 17. To keep n as small as possible, suppose that this is the case and Q(n) = 2 17 = 34. The sum of all digits but the hundreds and tens one is therefore 34 2 9 = 16 < 2 9, which means that two more digits are enough. Now it is easy to see that n = 7999 is the desired result.

Statistics
421
teams received
78.6%
teams solved
00:33:37
average solving time

Problem 15

A bus company runs a line between towns A and D with stops in towns B and C (in this order). The ticket price is directly proportional to the distance travelled by the bus. For example, the ticket from A to C costs the same as the tickets from A to B and from B to C together. Moreover, the company does not offer return tickets, only one way ones. Lisa, a keen bus ticket collector, wants to gather tickets with all possible prices regardless of the direction of the journey. So far she has got the tickets costing 10, 40, 50, 60, and 70. What are the possible prices of the missing ticket?

Solution

Answer:

20, 110


Assume first that Lisa has the most expensive ticket (i.e. the one from A to D) in her collection; thus its price is 70. As this price is the sum of the tickets for the sections AB, BC, and CD, at least two of which are already in Lisa’s possession, we see that the only possibility for the prices of these three tickets is 10, 20, and 40, so the missing price has to be 20. It is easy to see that these prices can be assigned to the sections so that they agree with the rest of the tickets.

If the most expensive ticket is missing, then the ticket costing 70 has to be for a journey with one stop; the only way to decompose this price to a sum of two which Lisa already has is 10 + 60. We infer that the ticket for the remaining section costs 40 and the longest journey costs 10 + 40 + 60 = 110. It is again easy to check that these values are satisfactory.

Statistics
410
teams received
82.2%
teams solved
00:35:34
average solving time

Problem 16

In a clock and watch store, Helen admires a watch which is packed in a transparent rectangular box such that the center of the box and the center of the watch (the point where the hands meet) coincide. The shorter side of the box is 3cm long. She notices that at noon, the hour hand points to the middle of the shorter side of the box, and at one o’clock, it points to the corner of the box. How far apart are the two points on the boundary of the box where the hour hand points to one o’clock and to two o’clock, respectively?

Solution

Answer:

3cm


Denote by Px the point on the boundary of the box where the hour hand points at x o’clock, and let C be the center of the box. Since P2CP1 = P3CP2 = 30, we see that the point P2 is the incenter and centroid of the equilateral triangle CCP1, where C is C reflected through P3. Now, the distance P1P2, which we are looking for, is 23 of the height of an equilateral triangle of side length 3cm, i.e. P1P2 = 2 3 1 2 3 3cm = 3cm.

PIC

Statistics
398
teams received
71.4%
teams solved
00:35:12
average solving time

Problem 17

Find an arrangement of 1,2,,9 as a nine-digit number such that any two consecutive digits form a number which is a product k l of digits k,l {1,2,,9}.

Solution

Answer:

728163549


Let x,y {1,2,,9} be distinct digits. A pair xy will be called valid whenever there exist k,l {1,2,,9} such that 10x + y = kl holds. Since the only valid pair involving 9 is 49, the block 49 must appear at the end of the desired nine-digit number z. There are two valid pairs involving 7, namely 27 and 72. They cannot occur simultaneously, and the end of z is already occupied. Therefore 72 must be put at the beginning of z. Since valid pairs involving 8 are 18, 28, 48 and 81, and 4 has been already used to form 49, the only option is to form a block 281. Hence z = 728149. Now we have to handle the remaining digits 3, 5 and 6. Since neither 13 nor 34 is a valid pair, and the only valid pair xy such that x {5,6} and y = 3 is 63, we find z = 728163549. Clearly, z satisfies all imposed conditions.

Statistics
378
teams received
87.0%
teams solved
00:30:22
average solving time

Problem 18

Find the largest prime p less than 210 such that the number 210 p is composite.

Recall that number 1 is neither prime nor composite.

Solution

Answer:

89


Instead of looking for the largest prime p, let us look for the smallest composite number n such that 210 n is a prime. We have 210 = 2 3 5 7. Consequently, if n was divisible by 2, 3, 5, or 7, so would be 210 n, i.e. 210 n would not be prime. The next smallest composite candidate for n is 112 which gives p = 210 121 = 89, which is a prime.

Statistics
363
teams received
61.2%
teams solved
00:36:25
average solving time

Problem 19

The management of an elementary school decided to buy a certain number of pencils and to distribute them among the first grade pupils, who were divided into classes A, B, and C. If they gave the same number of pencils to every pupil, each of them would get nine pencils. If they handed them only to class A, each pupil in this class would get 30 pencils, and if they chose class B instead, each would get 36 pencils. How many pencils would a single pupil from class C receive if only this class was given pencils?

Solution

Answer:

20


Denote by T the total number of pencils and by a, b, c the numbers of pupils in the corresponding classes. From the statement we know that T = 9(a + b + c), T = 30a, and T = 36b. We are looking for Tc. Substituting a = T30 and b = T36 in the first equation yields

T = 3 10T + 1 4T + 9c, 9 20T = 9c, T c = 20.
Statistics
351
teams received
87.5%
teams solved
00:16:43
average solving time

Problem 20

Find all four-digit square numbers which have the property that both the first two digits and the last two digits are non-zero squares, the latter one possibly starting with zero.

Solution

Answer:

1681


Since for k 50 the inequality (k + 1)2 k2 > 100 holds, 502 = 2500 is the only square starting with 25 (similarly for 3600, 4900, 6400, and 8100). Hence the first two digits have to be 16. The only square greater than 1600 and less than 1700 is 412 = 1681, which clearly satisfies the problem conditions.

Statistics
334
teams received
72.2%
teams solved
00:27:07
average solving time

Problem 21

A driver was driving on a highway between two cities at a constant speed. Unfortunately, some parts of the highway were under repair, so he had to reduce his speed by one fourth while he was driving through these sections. Consequently, by the time he would normally have reached his destination, he had travelled only six sevenths of the entire distance. At that point, what fraction of the total time he had been driving did he spend in the sections under repair?

Solution

Answer:

4/7


Let x be the fraction of time spent in the sections under repair. Then 1 x is the fraction of time spent on the rest of the highway. Thus we have

6 7 = 3 4x + 1 x,

which yields x = 47.

Statistics
315
teams received
71.1%
teams solved
00:25:43
average solving time

Problem 22

A rectangle with integral side lengths is decomposed into twelve squares with the following side lengths: 2, 2, 3, 3, 5, 5, 7, 7, 8, 8, 9, 9. What is the perimeter of the rectangle?

Solution

Answer:

90


By summing the areas of the squares, the area of the rectangle is 464 = 24 29. The lengths of both sides of the rectangle have to be at least 9 because of the square with side length 9. Hence the only possible factorization is 16 29, which yields the perimeter 90.

Such a decomposition exists, as one can see in the figure:

PIC

Statistics
303
teams received
75.9%
teams solved
00:21:34
average solving time

Problem 23

A square sheet of paper is folded so that one of its vertices is precisely on one of the sides. As in the picture, there is a small triangle, which overlaps the original square. The length of its outer side that is adjacent to the line of the folding is 8cm, and the length of the other outer side is 6cm.

PIC

What is the side length of the paper?

Solution

Answer:

36cm


By checking angles, we see that all triangles in the statement picture are right-angled and similar to each other. If we denote the side lengths of the triangle in the lower right corner by 6x, 8x, and due to the Pythagorean theorem 10x, then by “unfolding” we see that the side length of the square is 18x. This implies that the lower left triangle has one side of length 18x 6x = 12x, as can be seen in the following picture. The other sides of this triangle are of length 9x and 15x due to the scaling factor 32 of similarity. Now we can see that the side length of the given square is also 15x + 6cm, which yields x = 2cm. Therefore the side length of the paper is 36cm.

PIC

Statistics
283
teams received
70.0%
teams solved
00:22:43
average solving time

Problem 24

An old steamship is moving along a canal at a constant speed. Simon wants to find out the length of the ship. While the ship is slowly advancing, he walks at the waterside at a constant speed from the rear of the ship to its nose counting 240 steps. Then he immediately turns around and walks backwards up to the rear of the steamship counting 60 steps. What is the length of the steamship in steps?

Solution

Answer:

96


When Simon returns to the back of the ship, he has made 300 steps and the ship has moved on 240 60 = 180 steps. Hence during the time in which Simon makes 60 steps, the ship moves 180 : 5 = 36 steps forward. However, Simon reaches the back of the ship after 60 steps, so the length of the ship must be 60 + 36 = 96 steps.

Statistics
269
teams received
55.8%
teams solved
00:28:45
average solving time

Problem 25

The number 137641 = 3712 is the smallest six-digit number such that it is possible to cross out three pairwise different digits to obtain its square root: 137641. Find the largest six-digit number having this property.

Solution

Answer:

992016 = 9962


Let (1000 n)2 be the desired number (n 1). We can calculate the squares for n = 1,2,3,4, by using the formula (1000 n)2 = 1000 (1000 2n) + n2 to get 9992 = 998001, 9982 = 996004, 9972 = 994009, 9962 = 992016, It remains to see that the digits 2, 0, 1 are pairwise different and that 992016 = 996 is the square root of 992016. Therefore 992016 is the desired number.

Statistics
248
teams received
47.6%
teams solved
00:24:45
average solving time

Problem 26

Linda typed something on her calculator, and so a three-digit number appeared on the display. Patrick, who was sitting opposite to her, noticed that from his point of view (upside-down) it looked exactly as a three-digit number that is greater by 369 than the one typed. What was the number that Linda typed?

The calculator has a seven-segment display, therefore the digits look like this:

PIC

Solution

Answer:

596


Notice that if we turn a digit upside-down, then either it does not change (0, 2, 5, 8), or it changes (6 9), or we do not get a digit at all (1, 3, 4, 7). Let us denote by x the Linda’s number and by x the same number upside-down. Since the number 369 ends with 9, there are three candidates for the units digit of x: 0, 6, and 9 (all other admissible numbers lead to a non-admissible units digit of x).

If x ended with 0, then x would begin with 0, which is impossible. Furthermore, x ending with 9 would result in x ending with 8, i.e. x beginning with 8 and x beginning with 6, which is a contradiction since x > x. Finally, if 6 is the units digit of x, we have x = 5a6¯ and x = 9a5¯ for some admissible digit a and its upside-down version a. However, a = a is not possible in the light of x x = 369, so a has to be either 6 or 9. Direct computation shows that x = 596 is the sought value.

Statistics
234
teams received
70.1%
teams solved
00:21:09
average solving time

Problem 27

There are three families living on the island of Na-boi, each having two sons and two daughters. In how many ways can these twelve people form six married couples if the marriages of siblings are forbidden?

Solution

Answer:

80


Denote the families A, B, and C. If the sons from A marry two sisters from some other family (w.l.o.g. B), then the daughters from A have to marry the sons from C (otherwise at least one son from C would marry his sister). It follows that the sons from B marry the daughters from C. This yields 2 23 = 16 ways—there are two ways to match the families, and then each pair of daughters has two options of marrying the sons from the matched family.

If, on the other hand, the sons from A decide to have wives from different families, their sisters must do the same in order to prevent inter-family marriages. The two sons together have eight choices of wives and the same holds for the daughters. After this matching is done, in each family B and C there is exactly one son and one daughter left unmarried, which gives the one and only way to complete the marriage scheme. Therefore this scenario gives 8 8 = 64 ways.

We conclude that there are 16 + 64 = 80 ways to marry the people.

Statistics
212
teams received
39.2%
teams solved
00:27:37
average solving time

Problem 28

Hansel and Gretel have baked a very big pizza consisting of 50 slices of equal circular sector shape. They have distributed olives on the slices in such a way that there are consecutively 1,2,3,,50 olives placed clockwise on the slices. Now they want to divide the pizza into two equal halves by making a straight cut between the slices so that Hansel gets twice as many olives as Gretel. Determine the total number of olives on the four slices adjacent to the cutting line.

Solution

Answer:

68, 136


Let us number the slices by the number of olives put on them. Note that the cutting line cannot separate the slices 1 and 50 (or the slices 25 and 26) because clearly

2 (1 + 2 + + 25) < 26 + 27 + + 50.

Hence we can assume that n, n + 1, n + 25, n + 26 are the numbers of the slices adjacent to the cutting line, where 1 n 24. The sum of these numbers is 4n + 52. Now we compute (n + 1) + (n + 2) + + (n + 25) = 25n + 1 2 25 26 = 25(n + 13) and 1 + 2 + + 50 = 1 2 50 51 = 25 51. Then we have two possibilities:

25(n + 13) = 1 3 25 51 = 25 17or25(n + 13) = 2 3 25 51 = 25 34.

The first possibility yields n = 4 and the desired sum is 4n + 52 = 68. From the second possibility we obtain n = 21 and 4n + 52 = 136. In total, there are two solutions, namely 68 and 136.

Statistics
185
teams received
42.2%
teams solved
00:26:22
average solving time

Problem 29

Find all primes p with the property that 19p + 1 is the cube of an integer.

Solution

Answer:

421


If p is a prime fulfilling the given condition, then there exists an integer k > 2 with k3 = 19p + 1. Therefore we get the equation

19p = k3 1 = (k 1)(k2 + k + 1).

Due to k > 2, both factors on the right-hand side are proper divisors of 19p. Since 19p is a product of two primes, we have either k 1 = 19 or k2 + k + 1 = 19. The first case leads to k = 20 and p = 400 + 20 + 1 = 421, which is a prime. In the second case, the quadratic equation k2 + k 18 = 0 has no integer solution. Therefore p = 421 is the only solution.

Statistics
163
teams received
53.4%
teams solved
00:15:48
average solving time

Problem 30

In a parallelogram ABCD, the point E lies on side AD with 2 AE = ED and the point F lies on side AB with 2 AF = FB. Lines CF and CE intersect the diagonal BD in G and H, respectively. Which fraction of the area of parallelogram ABCD is covered by the area of the pentagon AFGHE?

Solution

Answer:

7 30


In the following, we shall denote the area by square brackets. Since the triangles EHD and CHB are similar, the equation

BH HD = BC ED = AD 2 3 AD = 3 2

follows. Due to the similarity of the triangles FBG and CDG, we get DG GB = 3 2. Therefore DH = BG = 2 5 DB and HG = 1 5 DB. Since

[ECD] = 2 3[ACD] = 2 3 1 2[ABCD] = [FBC],

we get

[AFGHE] = [AFCE] [GCH] = (1 3 1 5 1 2 )[ABCD] = 7 30[ABCD].

Statistics
147
teams received
31.3%
teams solved
00:26:20
average solving time

Problem 31

Find the largest five-digit number with non-zero digits and the following properties:

Solution

Answer:

85595


Let abcde¯ be a five-digit number such that abc¯ = 9 de¯ and cde¯ = 7 ab¯. Then we have

63 de¯ = 7 abc¯ = 70 ab¯ + 7c = 10 cde¯ + 7c = 1007c + 10 de¯,

so de¯ = 1007c 53 = 19c. Analogously we get ab¯ = 17c. If c 6, then the numbers 17c and 19c are greater than 100. It follows that the maximum possible value of c is 5, i.e. the maximum possible value of 17119c is 85595.

Statistics
125
teams received
54.4%
teams solved
00:20:16
average solving time

Problem 32

Twelve smart men, each of whom was randomly dealt one of twelve cards—nine blank cards and three special cards labelled J, Q, and K—were sitting in a circle. Everybody looked at his card, and then passed it to his right-hand neighbour. Continuing in this way, after every look at a card, they were asked to raise their hands simultaneously if they knew who was holding which special card at that very moment. Nobody raised his hand after having seen four cards. Exactly one man raised his hand after having seen his fifth card. Next, x men raised their hand after having seen six cards and y men after seven cards. Determine xy.

Solution

Answer:

42


The first man to raise his hand was the first one to see all three special cards. This man must have received one special card as his fifth card because otherwise he could have raised his hand earlier. Moreover, he must have received one special card at the very beginning because otherwise his left-hand neighbour would have seen all special cards after the previous round. Denote C1 the first card, C3 the fifth card, and C2 the remaining special card that the man got in the meantime. After the subsequent looks at their cards, exactly the persons who encountered C2 and at least one other card know or can deduce the positions of all three special cards—the positions of C1 and C3 are known to everyone, but their labels are not. It is easy to see that there are six such men after having seen six cards and seven after having seen seven cards, so the answer is 42.

Statistics
107
teams received
25.2%
teams solved
00:23:50
average solving time

Problem 33

Within an isosceles right-angled triangle with the length of the base 1, seven circles are constructed as in the picture:

PIC

What is the total area of the circles?

Solution

Answer:

π322 4 = π(12)2 4 = π 1 4(1+2)2 = π 1 4(3+22)


If an isosceles right-angled triangle is cut into two equal triangles, then they are similar to the original one with the ratio 1 : 2, and so are the radii of the incircles. Thus each new incircle has half the area of the original one. In other words, the total area of the incircles is not changed when cutting the big triangle. Hence it is sufficient to determine the area of the incircle of the big triangle, radius of which we compute using equal tangents. Since the length of the legs of the big triangle equals 2 2 by Pythagorean theorem and the perpendiculars from the incenter to the legs form a square, we get that the radius is 2 2 1 2, so the area equals

π3 22 4 .

Statistics
92
teams received
37.0%
teams solved
00:22:48
average solving time

Problem 34

Find all primes p such that p + 11 divides p(p + 1)(p + 2).

Solution

Answer:

7, 11, 19, 79


As p is a prime, it is either equal to 11 (which clearly satisfies the given condition) or coprime to p + 11. In the latter case, the product in question is divisible by p + 11 if and only if (p + 1)(p + 2) is. This reduced product modulo p + 11 equals (10) (9), thus p + 1190. This is satisfied for p {7,19,79}.

Statistics
70
teams received
44.3%
teams solved
00:19:42
average solving time

Problem 35

Wood lice (Porcellio scaber) have fourteen legs. Mother wood louse has large supplies of identical socks and shoes and prepares her children for the upcoming cold season. She explains to little wood louse Jim that he may put on his socks and shoes in arbitrary order, but he has to bear in mind that on each individual leg he has to put a sock prior to a shoe. In how many ways can little Jim proceed to dress his feet?

Solution

Answer:

28! 214


A way to dress Jim’s legs can be represented by a 28-tuple consisting of 14 socks and 14 shoes in which the sock belonging to a specific leg is in a position previous to that of the shoe belonging to the same leg. For the first pair of a sock and a shoe, there are (28 2) possibilities. For the second pair, there are 28 2 = 26 places, hence (26 2) possibilities. Continuing this way, there remains only (2 2) = 1 possibility for the last pair. Therefore the result is

( 28 2) ( 26 2) ( 24 2) (2 2) = 28! 214.

Statistics
56
teams received
35.7%
teams solved
00:16:27
average solving time

Problem 36

Let x be a real number such that x3 + 4x = 8. Determine the value of x7 + 64x2.

Solution

Answer:

128


It suffices to plug in x3 = 8 4x into the given expression as follows:

x7+64x2 = x(x3)2+64x2 = x(84x)2+64x2 = 64x+16x3 = 16(x3+4x) = 128.

Statistics
41
teams received
34.1%
teams solved
00:27:31
average solving time

Problem 37

In an isosceles triangle ABC with base AB, let D be the intersection of angle bisector of ∠ACB with AB and E the intersection of angle bisector of ∠BAC with BC. Given that AE = 2 CD, find ∠BAC.

Solution

Answer:

36


Let F be the point on BC such that AE DF. Now DF = 1 2AE = CD, so the triangle FCD is isosceles with base FC. Denote φ = ∠BAC. Then

∠AEC = ∠DFC = ∠FCD = ∠DCA = 90 φ.

Finally, since ∠CAE = 1 2φ, we have (using AEC)

1 2φ + 3(90 φ) = 180,

so φ = 36.

PIC

Statistics
35
teams received
31.4%
teams solved
00:13:13
average solving time

Problem 38

Given a sequence of real numbers (an) such that a1 = 2015 and a1 + a2 + + an = n2 an for each n 1, find a2015.

Solution

Answer:

1 1008


By subtracting the recursive formulas for n and n 1, we get an = n2 an (n 1)2 an1, which can be simplified to an = n1 n+1an1. Thus

an = n 1 n + 1 n 2 n n 3 n 12 4 1 3 a1 = 2a1 n(n + 1),

and therefore a2015 = 22015 20152016 = 1 1008.

Statistics
27
teams received
59.3%
teams solved
00:13:40
average solving time

Problem 39

Kate and Harriet invented the following game: They colour the faces of two twelve-sided fair dice with cyan, magenta, and yellow so that each colour is present on at least one face of each die, and there are exactly four yellow faces on the first die. If they throw the dice and both of these show the same colour, Kate wins, otherwise Harriet wins. Suppose that the colours are distributed so that the girls have equal chances of winning. How many magenta faces must be there on the second die?

Solution

Answer:

1, 9


Denote by c1, m1, y1, c2, m2, y2 the numbers of faces of respective colours on the dice. We know that c1 + m1 + y1 = 12, c2 + m2 + y2 = 12, and y1 = 4. Moreover, from the total of 122 = 144 possible outcomes of throwing the dice, exactly one half results in same colours, so

c1c2 + m1m2 + y1y2 = 72.

Expressing the left-hand side in terms of c1, c2, and m2 using the relations above, we obtain

c1c2 c1m2 4c2 + 4m2 + 48 = 72,

or

(c1 4)(c2 m2) = 24.

Using 3 c1 4 3 and 9 c2 m2 9, we deduce that c2 m2 is either 8 or 8, which together with 0 < y2 = 12 c2 m2 yields that m2 is either 1 or 9. A straightforward check shows that both these values are possible.

Statistics
22
teams received
54.5%
teams solved
00:13:52
average solving time

Problem 40

There are n > 24 women sitting around a great round table, each of whom either always lies or always tells the truth. Each woman claims the following:

Find the smallest n for which this is possible.

Solution

Answer:

32


Let us pick a woman, then the one 24 seats to her right, then the next one 24 seats to the right etc. After a certain number of such steps, say s, we get back to the original woman. This s is readily seen to be the smallest positive integer such that 24s is a multiple of n. Hence s = nd, where d is the greatest common divisor of n and 24.

Observe that the truthfulness of the women has to alternate, i.e. every woman is truthful if and only if the one 24 seats to her right is a liar. If s were odd, this would lead to a contradiction. Therefore n has to be divisible by a higher power of 2 than 24 is. The smallest candidate for n is 32, and it is easy to check that this number satisfies the given conditions.

Statistics
19
teams received
73.7%
teams solved
00:08:05
average solving time

Problem 41

Two squares have a common center and the vertices of the smaller one lie on the sides of the bigger one. If the small square is removed from the big one, it decomposes into four congruent triangles, the area of each being one twelfth of the area of the big square. What is the size in degrees of the smallest internal angle of the triangles?

PIC

Solution

Answer:

15


Denote by a, b the legs and by c the hypotenuse of the remaining triangles, and assume a b. A straightforward computation shows that the area of the small square equals two thirds of the area of the big square. Hence the area of one of the triangles is one eighth of the area of the small square, that is

1 2ab = 1 8c2.

Let α be the smallest internal angle in the triangle. Then a = csinα and b = ccosα, so

c2 = 4ab = 4c2 sinαcosα = 2c2 sin2α,

or

sin2α = 1 2.

Since α 45, it follows that 2α = 30, and finally, α = 15.

Statistics
17
teams received
58.8%
teams solved
00:10:38
average solving time

Problem 42

A circle ω3 of radius 3 is internally tangent to circles ω1, ω2 of radii 1 and 2, respectively. Moreover, ω1 and ω2 are externally tangent. Points A, B on ω3 are chosen so that the segment AB is a common external tangent of ω1 and ω2. Find the length of AB.

Solution

Answer:

4 3 14


Denote O1, O2, O3 the centers of ω1, ω2, ω3, respectively, and let T1, T2, T3 be the feet of perpendiculars from O1, O2, O3 to the segment AB (hence T1 and T2 are the points of tangency of AB to ω1, ω2). Since O1T1 O2T2 O3T3, O1T1 = 1, O2T2 = 2, and O1O3 = 2O2O3, where O1, O2, O3 are collinear, we easily get O3T3 = 5 3 (consider similar triangles). Applying the Pythagorean theorem to the triangle AO3T3, we conclude that

AB = 2AT3 = 232 (5 3 )2 = 4 314.

PIC

Statistics
14
teams received
42.9%
teams solved
00:17:56
average solving time

Problem 43

One day, Oedipus, an intrepid hero, met the Sphinx, who gave him the following riddle: She chose a positive two-digit integer S. Oedipus could choose three one-digit integers a < b < c and ask if S was divisible by them. For each of these numbers, he got an answer (either ‘yes’ or ‘no’). Oedipus fell into despair as there were exactly two numbers satisfying the divisibility conditions. But then the Sphinx told him that she had been wrong about the divisibility by b, which fortunately allowed Oedipus to find S with certainty. What was the value of S?

Solution

Answer:

84


There are clearly three two-digit numbers satisfying both given answers about divisibility by a and c (two corresponding to the Sphinx’ first answer and one after the correction). Moreover, both these answers have to be positive since a negative answer would result in more than three eligible two-digit numbers. Hence these numbers are multiples of lcm(a,c) = m. It follows that 25 m 33, but only two numbers within this range are the least common multiples of two digits, namely 28 = lcm(4,7) and 30 = lcm(5,6). The latter is impossible because of c a 2, so we have a = 4 and c = 7. Now if b were 5, then there would be no two-digit number being divisible by a, b, and c simultaneously. In the case b = 6, the negative answer about b corresponds to the numbers 28 and 56, while the positive answer yields S = 84.

Statistics
13
teams received
69.2%
teams solved
00:11:14
average solving time

Problem 44

Four people were moving along a road, each of them at some constant speed. The first one was driving a car, the second one was riding a motorcycle, the third one was riding a Vespa scooter, and the fourth one a bicycle. The car driver met the Vespa at 12 noon, the bicyclist at 2 p.m., and the motorcyclist at 4 p.m. The motorcyclist met the Vespa at 5 p.m., and the bicyclist at 6 p.m. At what time did the bicyclist meet the Vespa scooter?

Solution

Answer:

3:20 p.m.


Since the time in question does not depend on the chosen reference frame, we may assume that the car is not moving at all. Under this assumption, the motorcycle needed one hour from where it met the car to its meeting point with the Vespa, whereas the Vespa needed five hours for the same distance, thus the motorcycle was five times faster. Similarly, one may deduce that the motorcyclist was twice as fast as the bicyclist, hence the ratio of the speeds of the Vespa and the bicycle was 2 : 5.

If the Vespa needed t hours to get from the car to its meeting point with the bicyclist, then the bicyclist needed t 2 hours. The ratio of these required times equals the inverse of the ratio of the speeds, so

t 2 t = 2 5,

or t = 103. Finally, using the fact that the Vespa met the car at 12 noon, we infer that it met the bicyclist at 3:20 p.m.

Statistics
12
teams received
25.0%
teams solved
00:09:02
average solving time

Problem 45

The floor of a hall is covered with a square carpet of side length twenty-two meters. A robotic vacuum cleaner (robovac) is given the task to clean the carpet. For its convenience, the carpet is divided into 484 unit squares. The robovac cleans one square after another in accordance with the following rules:

At the beginning, the robovac is placed on one square and it may choose any admissible direction. For how many starting squares is the robovac able to clean the whole carpet if it does not need to finish its work on the edge?

Solution

Answer:

20


If the robovac does not start in one of the corner 3 × 3 ‘multisquares’, there always remains a non-cleaned part of the carpet—when the robovac leaves the edge of the carpet (i.e. no later than in its seventh move), it divides the remaining non-cleaned squares into two separate regions. We can routinely verify that the squares with coordinates (1,2), (2,1), (2,3), (3,2) and their symmetric counterparts in the other corners do not satisfy the given conditions for similar reasons. However, those with coordinates (1,1), (2,2), (3,3), (3,1), (1,3) do. Thus there are 4 5 = 20 possible starting squares in total.

PIC

Statistics
10
teams received
30.0%
teams solved
00:13:57
average solving time

Problem 46

Let the points A, B, C, D, E, F lie clockwise in this order on a circle ω. Assume further that AD is a diameter of ω, BF intersects AD and CE in G and H, respectively, ∠FEH = 56, ∠DGB = 124, and ∠DEC = 34. Find ∠CEB.

Solution

Answer:

22


The inscribed angle theorem implies that ∠CEB = ∠CDB, so let us compute ∠CDB. Since the quadrilateral BCEF is cyclic, we have

∠FBC = 180∠FEC = 180 (180∠FEH) = 56.

Moreover, ∠DGF = 180∠DGB = 56, so AD and BC are parallel. This implies ∠ADB = ∠DBC and using inscribed angles we further infer ∠DBC = ∠DEC = 34. Since ∠ABD = 90 (Thales’ theorem) and trapezoid ABCD is cyclic, we obtain

∠ADC = 180∠ABC = 180 (∠ABD + ∠DBC) = 56,

and finally

∠CEB = ∠CDB = ∠ADC ∠ADB = 56 34 = 22.

PIC

Statistics
6
teams received
33.3%
teams solved
00:17:46
average solving time

Problem 47

Ten people—five women and their husbands—took part in E events. We know that no married couple took part in the same event, every pair of non-married people (including same-sex pairs) took part in exactly one event together, and one person attended only two events. What is the smallest E for which this is possible?

Solution

Answer:

14


Denote the couples (a1,a2), (b1,b2), (c1,c2), (d1,d2), (e1,e2). We may w.l.o.g. assume that a1 is the person who attended only two events and that the first of these events was also attended by b1, c1, d1, and e1, whereas the second one by their counterparts. Every other event could have been attended by at most two people from b1,b2,,e1,e2 simultaneously, so there had to be at least 12 other events. If further a2 takes part in any disjoint four of these events, we obtain the situation described in the statement, thus the smallest value of E is 14.

Statistics
3
teams received
66.7%
teams solved
00:40:51
average solving time

Problem 48

Students were given a three-digit number abc¯ with 0 < a < b < c. The task was to multiply it by 6 and then swap the tens digit with the hundreds digit. Alex made a mistake and performed the swap before the multiplication, but the result turned out to be correct! Find abc¯.

Solution

Answer:

678


Since 0 < a < b, we have b 2 and 6 bac¯ > 1200, so the result obtained by Alex must be a four-digit number, say 6 bac¯ = defg¯. On the other hand, we know that 6 abc¯ = dfeg¯. Subtracting these two equalities, we get

6(bac¯ abc¯) = defg¯ dfeg¯.

Thus 540(b a) = 90(e f), or 6(b a) = e f. As e, f are digits, we have e f 9. It follows that e f = 6 and b a = 1 (b a > 0 because b > a). Substituting b = a + 1 in 6 bac¯ = defg¯ gives

defg¯ = 6(100(a + 1) + 10a + c) = 660(a + 1) 6(10 c).

This means that defg¯ must differ from some multiple of 660 by a non-zero multiple of 6 not exceeding 42 (c 3). Remembering that e f = 6, and considering successively a = 1,2,,7, we determine all candidates for the number defg¯: 1938, 2604, 3930, 3936, 4602, 4608. Only for defg¯ = 4608 the number bac¯ = defg¯6 = 768 turns out to have distinct non-zero digits. Now we can directly check that indeed 6 abc¯ = 6 678 = 4068 = dfeg¯.

Statistics
3
teams received
33.3%
teams solved
00:53:51
average solving time

Problem 49

Consider a 5 × 3 grid. A mouse sitting in the upper left corner wants to reach a piece of cheese in the lower right corner, whereas a crab sitting in the lower left corner wants to reach algae in the upper right corner. They move simultaneously. Every second, the mouse moves one square right or down, and the crab moves one square right or up. In how many ways can the animals reach their food so that they do not meet at all?

PIC

Solution

Answer:

70


Observe that the animals may meet only in the middle row. Furthermore, the path of each animal is completely determined by the visited squares in the middle row. It is easy to see that the animals do not meet if these middle parts of their paths do not intersect, so we are looking for the number of pairs of disjoint segments of the middle row.

Let us first handle the case when there is at least one unused square between the segments. Then the number of pairs may be computed as 2 ( 6 4), since one chooses four out of six edges of squares in the middle row and then chooses the animal which uses the segment between the first two of the chosen edges (the second animal uses the segment between the second two edges). If there is no gap between the segments, we obtain 2 ( 6 3) pairs since the segments are described by three edges.

In total, there are 2 ( 6 4) + 2 ( 6 3) = 70 possible ways.

Statistics
3
teams received
33.3%
teams solved
00:36:35
average solving time

Problem 50

Find the number of positive integers n not exceeding 1000 such that the number n3 is a divisor of n.

The symbol x denotes the integral part of x, i.e. the greatest integer not exceeding x.

Solution

Answer:

172


Observe that n3 = k if and only if k3 n (k + 1)3 1. Out of the 3k2 + 3k + 1 numbers in this range, every k-th is divisible by k starting with k3, thus there are 3k + 4 such numbers. It remains to sum this expression for all numbers k such that (k + 1)3 1 1000 (i.e. k 9) and add one for the number 1000, which satisfies the given condition as well. Hence the desired result is

1 + k=19(3k + 4) = 1 + 9 4 + 3 9 10 2 = 172.
Statistics
2
teams received
100.0%
teams solved
00:09:51
average solving time

Problem 51

Find all real m such that the roots of the equation

x3 152x2 + mx 1952 = 0

are side lengths of a right-angled triangle.

Solution

Answer:

281/2


Let a, b, c be the roots of the given equation, which are also side lengths of a right-angled triangle. Assume w.l.o.g. that 0 < a,b < c, hence by Pythagoras’ theorem, the equation a2 + b2 = c2 holds. By Vieta’s formulas (or working out (x a)(x b)(x c) and then comparing coefficients), we get

152 = a + b + c,m = ab + ac + bc,1952 = abc.

Squaring 152 c = a + b leads to 450 302c = 2ab. After multiplying by c and substituting abc = 1952, we get the quadratic equation

2c2 15c + 132 = 0,

having roots c1 = 2 and c2 = 1322. Since the constraints 0 < a,b < c and abc = 1952 allow only c = 1322, the desired number m can be calculated via

m = ab + ac + bc = 1 2 ((a + b + c)2 2c2) = 1 2 450 c2 = 2812.

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

Problem 52

There are green and red apples in a basket, at least one red and two green ones. The probability that a randomly chosen apple is red is 42 times higher than the probability that two randomly chosen apples (without replacement) are both green. How many green apples and how many red apples are there in the basket?

Solution

Answer:

4 green and 21 red


Let g be the number of green apples and r the number of red apples. The statement may be rewritten as

r g + r = 42 g (g 1) (g + r) (g + r 1),

equivalently

r2 + (g 1)r 42g (g 1) = 0.

The latter can be viewed as a quadratic equation with variable r and parameter g . The discriminant

(g 1)2 + 168g (g 1) = 169g2 170g + 1

must be a square of an integer, otherwise the roots would be irrational. Due to g 2, we obtain the inequalities

(13g6)2 = 169g2156g+36 > 169g2170g+1 > 169g2208g+64 = (13g8)2.

Therefore 169g2 170g + 1 has to be equal to (13g 7)2, which implies 12g = 48, or g = 4. Then the roots of the quadratic equation are 24 and 21, but since r > 0, we get r = 21 as the only solution. Hence there are 21 red and 4 green apples in the basket.

Statistics
2
teams received
50.0%
teams solved
00:32:14
average solving time

Problem 53

Gilbert Bates, a very rich man, wants to have a new swimming pool in his garden. Since he likes symmetry, he tells the gardener to build an elliptical-shaped pool within a 10m × 10m square ABCD. This elliptical pool should touch all four sides of the square, particularly the side AB at point P which is 2.5m away from A. The gardener, who knows very well how to construct an ellipse if the foci and a point on the ellipse are given, reflects that due to symmetry he only needs the distance of the foci in this case. Can you help him by computing the distance of the foci in meters?

PIC

Solution

Answer:

10


We solve the problem in a more general way. Let ABCD be a square of side length 1 with corner A in the origin of a coordinate system. Point P is on AB and has coordinates (b,0) with 0 < b < 1 2. If focus F1 has coordinates (f,f), then focus F2 has coordinates (1 f,1 f) (both foci have to lie on the diagonal AC symmetrically with respect to the other diagonal).

PIC

Now line g1 through P and F1 is given by

y = (x b) f f b,

and line g2 through P and F2 by

y = (x b) f 1 b + f 1.

Since the line through P perpendicular to the tangent AB bisects F2PF1, the gradient of g2 has to be the negative of the gradient of g1. Therefore we get

f f b = (1) f 1 b + f 1,

which can be simplified to

f2 f + b 2 = 0.

This quadratic equation has two solutions f1,2 = 1 2 (1 ±1 2b), each one corresponding to one focus of the ellipse. The distance of the foci can now be computed by Pythagoras’ theorem, yielding 2 4b. Setting b = 1 4 and scaling up by 10 gives the desired result F1F2 = 10.

Alternative solution. Let us shrink both the square and the ellipse along AC so that the ellipse becomes a circle and denote the new points with a prime. Further, let S be the midpoint of AC and T the midpoint of AB.

PIC

Since AP = 1 4AB, we have AP = PT, so SA = ST. It follows that AC = BC and that the triangle ABC is equilateral. Hence the factor of shrinking is

AC AC = 3 3 .

It is easy to compute that the radius of the circle (which coincides with the length b of the minor semi-axis of the ellipse) equals 1 4AC. The length a of the major semi-axis is obtained by dividing the minor semi-axis by the factor of shrinking. Knowing the lengths a and b, it remains to compute the eccentricity using the formula e = a2 b2 and multiply it by two to get the distance of the foci.

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

Problem 54

A sequence (an) is given by a1 = 1, and an = a1 + a2 + + an1 for n > 1. Determine a1000.

The symbol x denotes the integral part of x, i.e. the greatest integer not exceeding x.

Solution

Answer:

495


By writing down the first few members (1,1,1,1,2,2,2,3,3,4,4,4,5,5,6,6,7,7,8,8,8,9,9,), we discover that number 1 repeats four times, while numbers greater than 1 seem to appear only twice or thrice. Let us prove by induction that those appearing three times are exactly natural powers of 2.

Suppose we have written down the beginning of the sequence up to the first occurrence of n (n > 1) and assume it behaves as described above. Let k be the largest integer such that 2k < n. Then the sum of all written members equals

s1 = (1+2++n)+(1+2++n1)+(1+2+22 ++2k)+1 = n2 +2k+1.

Since 2k+1 = 2 2k < 2n < 2n + 1 = (n + 1)2 n2, we have s1 < (n + 1)2, and hence the following member is s1 = n.

Let us determine the next number. Now the sum is s2 = s1 + n = n2 + n + 2k+1. If 2k+1 < n + 1, then again s2 < (n + 1)2 and the following member is n. However, k is the largest integer satisfying 2k < n, so it holds 2k+1 n. Therefore this case occurs exactly when 2k+1 = n. If n is not a natural power of 2, then the next member is n + 1 because n + 1 2k+1 < 2n < 3n + 4, which is equivalent to (n + 1)2 n2 + n + 2k+1 < (n + 2)2.

It remains to show that if n = 2k+1, then there comes n + 1 after three occurrences of n. This is easy because if we compute the next sum s3 = s2 + n = n2 + 2n + 2k+1 = n2 + 3n, we immediately get (n + 1)2 < s3 < (n + 2)2. Thus the induction step is complete and we get a1000 = 495 (since 500 = a1010 = a1009).

Statistics
1
team received
100.0%
teams solved
00:09:51
average solving time

Problem 55

Determine the number of 4 × 4 tables with non-negative integer entries such that

Solution

Answer:

576


Observe that every such table uniquely decomposes into an entrywise sum of two tables, the first one having exactly one 1 in every row and every column, and the second one exactly one 2 in every row and every column. Conversely, having such a pair of tables, adding them entrywise results in a table satisfying the given criteria. Therefore (4!)2 = 576 is the desired result.

Statistics
1
team received
0.0%
teams solved
-
average solving time