## PREVIOUS PROBLEMS

991214.
1. Can you find 7 natural numbers such that no two pairs of the 7 you have chosen have sums which are congruent modulo 20? That is, can you find natural numbers x1, x2, ..., x7, so that all the sums x1+x2, x1+x3, ..., x1+x7, ..., x6+x7 give different remainders when divided by 20?
2. Can you find 6 natural numbers such that no two pairs have sums congruent modulo 20?
Hint
Back to Problems Page
991102. Find the sum of the series
 1 2 + 1 3 + 1 4 + 1 6 + 1 8 + 1 9 + 1 12 + . . .
where the denominators consist of all natural numbers that have no prime factors other than 2 and 3.
991026. A sequence of natural numbers is defined by a1 = 1, a2 = 1, and an+2 = 3an+1-an for all natural numbers n. Prove that gcd(an+1, an) = 1 for all n, i.e. an+1 and an are relatively prime.
990921. A game for two players involves two piles of loonies on a table, one pile with 40 loonies and the other with 50 loonies. At any turn, a player must pick up either one or two loonies from one of the piles. If one pile has been emptied, the player must choose from the remaining pile; if a pile has only one loony remaining, the player may either pick up that one loony, or choose from the other pile. It is never permitted to take one coin from each pile. The player who picks up the last loony wins.

In this game, what is your best strategy? Should you choose to move first? At each turn, how should you decide how many coins to pick up?

990914.
Is the rational number
 1999999·2000001999999·1000001
larger or smaller than 4?

 990817. A fair coin is tossed repeatedly until "heads" is obtained. The number of "tails" produced before this happens is noted. If this process is repeated many times, does it tend to produce more "heads" or more "tails" in total?

 990608. Triangle PQR is isosceles, with PQ = PR = 3 and QR = 2 as shown at right. The tangent to the circumcircle at Q meets (the extension of) PR at X as shown. Find the lengths QX and RX.

 990427.Two circles have centres O1 and O2 respectively, and neither circle lies within the other (the circles may intersect, though that possibility is not shown in the diagram at right). Lines O1Q and PO2 are tangent to the circles as shown, and intersect at R. Prove that  PR x RO2 = O1R x RQ.

990420. Seven chess players A, B, C, D, E, F and G are to compete against each other in a "round-robin" tournament. That is, each player will play against each other player exactly once. The sponsors require that, on the first day of the tournament, exactly ten games should be played. (The rest of the games will be played on subsequent days.) Two hours will be allowed for a game, with a one-hour rest between games. The start times available are 9:00 a.m., 12:00 noon, 3:00 p.m., and 6:00 p.m. Several games may be played simultaneously.
1. Arrange a schedule of games for the first day so that no player has to play more than three games.

2. Unforeseen circumstances delay the start of the first day until 12:00 noon. Can you still arrange ten games in the remaining three time slots?

 990330. In the convex quadrangle ABCD, find a point P such that the sum of the distances from P to the vertices is a minimum. That is, AP + BP + CP + DP should be a minimum.

 990323. In the hexagon ABCDEF, sides are equal in pairs: AB = BC, CD = DE, and EF = FA. (a) Perpendiculars (green) are drawn to the chords (purple) as shown: from B to AC, from D to CE, and from F to EA. Show that these perpendiculars are concurrent. (b) Perpendiculars (green) are drawn to the chords (blue) as shown: from A to FB, from C to BD, and from E to DF. Show that these perpendiculars are concurrent.

990316. Evaluate
 n å k = 0 æç è 2n 2k ö÷ ø 4k.
That is, find a simple formula in terms of n for this sum.
990309.  When you buy a new deck of cards, it is arranged in a specific order, for example
 A§, 2§, 3§, ..., Q§, K§, A¨, ..., K¨,A©, ..., K©, Aª, ..., Kª

A perfect shuffle of a deck of 2n cards is carried out by cutting the deck exactly in half (n cards each) and then interleaving the two halves, so that card n+1 becomes the new card 1, card 1 becomes the new card 2, etc. Applying a perfect shuffle to the deck above produces

and a second perfect shuffle produces

How many perfect shuffles must be applied before the deck is back to its original order?

990202. In a triangle with vertices A, B, and C, label the lengths of the sides opposite these vertices a, b, and c as usual. Draw a circle of radius a with centre A, a circle of radius b with centre B, and a circle of radius c with centre C. Then these three circles intersect in six points, giving, together with the original vertices of the triangle, nine points in total (some of these nine points may coincide). Show that there are three lines in the plane which together contain all nine points; and that the intersection points of these three lines are the vertices of a triangle which is similar to the original triangle.
990126.  When a group of  people meet, some of them shake hands.  No one shakes hands with her or himself, and no two people shake hands more than once.  Furthermore, no three people all shake each other's hands; that is, for any three people,  at least one of the three potential handshakes does not occur.

What is the maximum number of handshakes among the  n   people?

990112.  The Fibonacci numbers are defined by the initial conditions F0 = 1,  F1 = 1,  and  Fn = Fn-1 + Fn-2  for  n > 1.
Another sequence {An} is defined by the equation  F2n+1 = AnFn for all n.    Prove  that  Ais an integer for all n, i.e.
prove that  F2n+1  is divisible by  Ffor all n.
981229.  Suppose that a and b are rational numbers such that the equation x3+ax2+bx+2 = 0 has three distinct rational solutions. Find the values of a and b, and find the three rational solutions. Prove that your answer is the only possible answer.
981222. Evaluate
 n å k = 0 æç è n k ö÷ ø 1 k+1 .

981208. A polyhedron is a connected graph on the sphere (or in the plane) with at least three edges meeting at each vertex, and at least three edges forming the boundary of each face.

1. Prove that every polyhedron must have at least six edges.
2. If no faces of a polyhedron are triangles, what is the smallest number of edges that the polyhedron may have?

981124. Find the maximum value of x1x2+x2x3+x3x1 where x1, x2, x3 are real numbers subject to the constraint x1+x2+x3 = 2.
981117. A fair die is rolled n times. In this problem, a ``run'' is a strictly increasing string of values, as long as possible. For example, if the die were rolled only 10 times, with outcomes 3, 2, 3, 5, 1, 6, 6, 1, 3, 5 there would be 5 runs, namely (3), (2, 3, 5), (1, 6), (6), (1, 3, 5). When the die is rolled n times, how many runs are produced, on average?
981103. If integers a ¹ 0, b ¹ 0, and c satisfy a2+b2 = c2 then (a,b,c) is said to be a Pythagorean triple. Is it always the case, for all integers x > 2 , that there is some Pythagorean triple containing x? (x could be either a, b, or c.)
 981027. Find the dimensions and area of the rectangle of largest area that fits within the ellipse 4x2 + 9y2=36, as shown at right. What are the coordinates of the corner point (a, b) for the rectangle of maximum area?

981020. Suppose that x, y and z are integers with   x3 + y3 + z3 divisible by 7. Prove that at least one of x, y and z is divisible by 7.
980929. If a is a real number with 0 < a < 1, prove that for all natural numbers n > 1,
 (1-a)n > 1 - na        and        (1-a)n < 1-a 1+(n-1)a .

980922. Three points are chosen at random on the circumference of a circle, and the inscribed triangle which has these points as vertices is drawn. What is the probability that this triangle contains the centre of the circle?
980915. Two numbers are selected at random, with repetition allowed, from the set {1, 2, 3, ..., 25}. What is the probability that the second number is greater than twice the first?
 980908. A circular pizza is cut into pieces by making straight cuts across it as shown at right. The pieces may be of different shapes and sizes. Is it always possible, for all natural numbers n, to make n straight cuts so that each cut intersects each other cut inside the pizza, and no three cuts pass through the same point? What is the maximum number of pieces that can be produced with n cuts?

980901. Two points are chosen at random (and independently) in the unit interval, cutting the interval into three segments. What is the probability that these three segments can form the sides of a triangle?
 980825. Given a triangle ABC as shown at right, with B1 any point between B and C, construct in turn AiBi parallel to AB, and AiBi+1 parallel to AB1, for all i > 0. Colour the triangle ABB1 red (R), and then the strips AB1B2A1 etcetera alternating green (G) and red (R) as shown. Then part of the original triangle ABC is red and part is green. For various choices of B1, what fraction of the triangle can be coloured green?

980818. Points A, B, and C lie on a circle with centre O. The (extensions of) AO and BO meet BC and AC in X and Y respectively, as shown at right. Prove that
 AXBY = ACAY x BXBC

 980811. Given a circle with centre O and a point P outside the circle, as shown at right, construct a point Q on the circle so that angle PQO is 60 degrees.

980804. Some natural numbers can be written as sums of consecutive odd numbers. For example:
 4 = 1 + 3 15 = 3 + 5 + 7

Which natural numbers can be written as such sums? (Give an answer in terms of the factors of the number.)

980728. Is it possible to find an equilateral triangle whose vertices are lattice points in the plane? That is, are there integers a0, b0, a1, b1, a2, b2, such that the points (a0, b0), (a1, b1), (a2, b2) are the vertices of an equilateral triangle?
980721. Which is larger:     ( 9999991/2 + 10000011/2 ),     or     2000 ?
980714. A sector is cut from a circle of radius 1 as shown at right. The included angle of the sector is a, as shown. The sector is then rolled up and the straight edges are joined to form a cone.
 (i) In terms of a, what is the volume of the cone? (ii) How should a be chosen to maximize the volume of the cone, and what is this maximum volume?

980707.
 A tetrahedron (not necessarily regular) is shown in blue at right. The midpoints of adjacent sides are joined, and the four corners (vertices) of the tetrahedron are cut off. One of the four cuts is shown in red. What 3-dimensional solid is left after the four corners are cut off? What is the ratio of the volume of this solid to the volume of the original tetrahedron?

980630. A fair coin is tossed n times to produce a sequence of H and T. A run is an unbroken string of tosses all the same (i.e. all H or T) with either nothing or the opposite results at the ends. On average, how many runs are produced?
980602. On a certain island, there are two towns, A and B. Everyone lives in one of these two towns. The inhabitants of A always tell the truth; the inhabitants of B never tell the truth. While on a visit to the island, you encounter a large group of the inhabitants. You may ask each of them one question about where they and/or their companions live. What questions could you ask so that after everyone has answered, you could know for each person in the group where that person lives?
980526. Three distinct numbers are chosen at random from 1, 2, 3, ..., 1000. What is the probability that the sum of these 3 numbers is divisible by 3?
980519. Consider the equations
 13 = 412 13 + 18 = 1124 13 + 18 + 115 = 2140 13 + 18 + 115 + 124 = 3460

What is the pattern for the sums on the left? Find a formula for the value of the sum given on the right.

980512.

The figure at right is a regular polygon with 2n vertices and sides, for n > 2. Chords have been drawn inside the polygon from each vertex to the next-vertex-but-one. The intersection points of these chords are the vertices of a smaller regular 2n-gon. Show that the ratio of the side of the large polygon to the side of the small polygon is

where there are n-1 twos in the numerator and n-2 twos in the denominator.

 980505. The figure at right is a regular pentagon, although your browser or printer may not reproduce it exactly. Chords have been drawn inside the pentagon to form a five-pointed star, which in turn contains a smaller regular pentagon in its centre. What is the ratio of the side of the large pentagon to the side of the small pentagon? What is the ratio of the areas?

980428. What are the last two digits of 79999   ?
 980421. Points A, B, C, and D lie on a parabola as shown at right. Let P be the intersection of AC and BD, P' be the intersection of the tangents to the parabola at points B and C, and P'' be the intersection of the tangents at A and B. Show that P, P', and P'' are collinear.

980414. A sports commentator was comparing the performance of two hockey players A and B over the past season, and found interesting results. She found that during the regular season, A had scored in 75% of the games in which A played, and during the semifinals and finals, A had scored in 37.5% of the games in which A played. For B, she found that B had scored in 66.7% (2/3) of the games in which B played in the regular season, and B had scored in 33.3% (1/3) of the games in which B played in the semifinals and finals. Thus A was a better player than B in each of the regular season and the semifinals/finals.

However, when she compared the total performance over the whole season, she found that A scored in just 50% of the games in which A played, and that B scored in 60% of the games in which B played, so overall B was the better player.

Is this possible, or must she have made some mistake in the calculations?

980407. In convex quadrilateral ABCD shown at right, the diagonals intersect at E. Let (AEB) denote the area of triangle AEB, etc. Show that
 (AEB)(DEC) = AEDE . BECE
Hint
Back to Problems Page
980331. Show that for all n > 1 ,
 n1/2 + (n+1)1/2 + . . . + (n2 - 1)1/2 < 23 (n3 - n3/2)

 980324. In triangle ABC, EF and E*F* are parallel to BC. Points P and P* are the intersections of BF, EC and BF*, E*C respectively. Prove that A, P*, and P are collinear. That is, prove that the locus of the point P as EF varies, parallel to BC, is a line through A.

980317. A two-player game is set up as follows: at the beginning, 30 pennies are placed on a table. The players then move alternately. On each move a player may pick up 1, 2, or 3 pennies. The player who picks up the last penny loses.

If you have first move, can you win? What is your strategy?

980310. An urn contains r red balls and b blue balls where r > b. All the balls are drawn from the urn one-by-one at random. What is the probability that at some point, an equal number of red and blue balls have been drawn?
980303. Three natural numbers a, b, and c are said to form a linear triple or arithmetic progression if a < b < c and b-a = c-b. How many linear triples are there with a, b, c in the set {1, 2, ... , n} ?
 980224. m ones and n zeros, where m > n , are placed around a circle in any order. An example with 7 ones and 5 zeros is shown. A particular 1 is called good if every sequence which starts from that position and proceeds counter-clockwise always contains more ones than zeros. In the example, the green 1 is good, while the red 1 is not. In general, in terms of m and n, how many ones are good? Explain your answer, remembering that the digits may occur in any order around the circle.

980217. A help centre for a math class is open from 1:00 pm. to 2:00 pm. every day. One day, thirty-one students show up at various times, and each stays for at least 10 minutes. Prove that at some time between 1:00 pm. and 2:00 pm. there must be at least 7 students present.
980210.
 In the figure shown at right, ABCD is a square, and APB is an isosceles triangle with base angles 15°. Prove that triangle DPC is equilateral.

980203. Coins 0, 1, 2, . . . , r are given, with coin 0 known to be genuine and at most one of the other coins either heavy or light. A standard balance is also provided, which can give one of three answers (left side heavier, sides equal, right side heavier) on any weighing. How many weighings are necessary to identify the false coin (if there is one) and state whether it is heavy or light?

Give a complete description of the process to be used for r = 4 .

980127. Simplify
( n
0
) 2-n + ( n+1
1
) 2-n-1 + ( n+2
2
) 2-n-2 + ... + ( 2n
n
) 2-2n

980120. Let Fn denote the nth Fibonacci number. That is, F0= 1, F1= 1, F2= 2, F3= 3, F4= 5, and in general
Fn+2 = Fn+1 + Fn.

Find a simple formula for

 F02 + F12 + . . . + Fn2

980113. Let Fn denote the nth Fibonacci number. That is, F0= 1, F1= 1, F2= 2, F3= 3, F4= 5, and in general
Fn+2 = Fn+1 + Fn.

Find a simple formula for

 F0 + ( n1 ) F1 + ( n2 ) F2 + . . . + ( nk ) Fk + . . . + Fn

980106. Given two positive integers m and n, we form four columns of numbers as follows: at the top we put m, n, m, n. To form the next row, compare the two numbers in columns 1 and 2. If they are not equal, subtract the smaller from the larger. Write this difference below the larger, and copy the smaller. In columns three and four, do the operation that was used in columns 1 and 2, except add instead of subtract. That is, if column 1 was subtracted from column 2, then add column 3 to column 4. Stop when the numbers in the first two columns are equal. Then take the average of the numbers in columns 3 and 4, last row.

For example, given 33 and 12, the work is:

 33 12 33 12 21 12 45 12 9 12 57 12 9 3 57 69 6 3 126 69 3 3 195 69
The average that is found is (195+69)/2 = 132.

Try a few more examples. What is the relationship of the number produced to the original numbers m and n ? Explain.

971230. The decimal expansion of 1/7 is 0.142857142857 . . . , with "period" 142857. When this period is split into two equal pieces, 142 and 857, and these two three-digit numbers are added, the result is 999. Try this for some other repeating decimals such as 1/11, 1/13, and 1/17. What is the general pattern? What is the explanation?
971223. Let Fn denote the nth Fibonacci number. That is, F0= 1, F1= 1, F2= 2, F3= 3, F4= 5, and in general
Fn+2 = Fn+1 + Fn.

Find a simple formula for Fn+1 Fn-1   -   Fn2 .

971216. Prove that no matter how 5 integers are chosen, not necessarily non-negative or even distinct, there must be some 3 numbers x1, x2, x3 among the 5 such that x1 + x2 + x3 is divisible by 3.
971209. Prove that for any real number x,
(x2 + ( x-1 )2 )1/2   +   (x2 + ( x+1 )2 )1/2   >=   2

971202. Prove that in any quadrilateral (not necessarily planar), with sides of lengths a, b, c, d
a2 <= 3( b2 + c2 + d2 )

971125. Prove that in any tetrahedron (not necessarily regular), there must be at least one vertex at which the edges have lengths that could form a triangle.
971118. For n a natural number, what is the last digit of 1n - 3n - 6n + 8n ?
971111. Prove that for n a natural number, 4n3 - 6n2 + 4n - 1 is never prime.
971104. Prove that for all n > 2,
n(n+1)(n+2) . . . (n+10) < n(11 + 55/n)

971028. Prove that for all n greater than or equal to 2,
 (5)(7)(9) . . . (2n+1) (4)(6)(8) . . . (2n) < n 1/2.

971021. A fair die is rolled 6 times to produce numbers a, b, c, d, e, f. What is the probability that these numbers are produced in non-decreasing order, i.e. a <= b <= c <= d <= e <= f ?

Note that <= is used here to denote "less than or equal to".

971014. It is possible to write 81 as a sum of consecutive odd natural numbers in two different ways:
1. 81 = 25 + 27 + 29;
2. 81 = 1 + 3 + 5 + 7 + 9 + 11 + 13 + 15 + 17.
Find all possible ways to express 1485 as a sum of consecutive odd natural numbers.
971007. A fair coin is tossed n times. What is the probability that at each step in the sequence of "heads" and "tails" that is produced, the number of "heads" obtained so far is at least as big as the number of "tails" obtained so far?
970930. Two players, A and B, take turns tossing a fair coin. A starts, then B has a turn, and so on. This continues until each player has tossed the coin n times; then A has one more toss. What is the probability that A has more "heads" than B, after A's last toss?
970923. A regular tetrahedron is inscribed in a cube of side 1, as shown in the figure below, by drawing diagonals in the faces of the cube (heavy lines).

Find

1. the volume of the tetrahedron;
2. the edge length of the tetrahedron;
3. the surface area of the tetrahedron;
4. the altitude of the tetrahedron.

970916. A regular tetrahedron is inscribed in a sphere of radius 1. Find
1. the altitude of the tetrahedron;
2. the edge length of the tetrahedron;
3. the surface area of the tetrahedron;
4. the volume of the tetrahedron.

970909. Is the binomial coefficient
(
 500 212
)
even or odd?

In general, how can you discover this without explicitly calulating the value?

970902. This problem concerns properties of the binomial coefficients
(
 n k
)
For what values of n are all of these odd? To rephrase, which rows in Pascal's triangle contain only odd numbers?
970826. A mathematics class has 13 students. As part of the course work, each student participates in some projects. Each project has exactly three students assigned to it. Furthermore any two students must work together exactly once.
• How many projects does each student do?
• How many projects are there in total?

970819. Show that for all constants a and b, and all real values of x,
| a sin(x) + b cos(x) |   <=   ( a2 + b2 ) 1/2

(Note that <= means "less than or equal to".)

Is it possible to have equality? If so, for what value of  x is the bound achieved?

970812. Find the minimum value of
 (x + y + z) . ( 1x+y + 1x+z + 1y+z )
where x, y, and z are positive real numbers.
970805. Some positive integers may be written as sums using all the digits from 0 to 9 exactly once. For example:
• 180 = 0 + 16 + 32 + 45 + 78 + 9;
• 54 = 10 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9.
Can you write the number 100 as such a sum?
970729. A triangle of area A is given. What is the area of the largest rectangle that can be inscribed in the triangle? How is this area achieved?

You may find it helpful to assume that one side of the rectangle lies on a side of the triangle. In this case, you should explain why this assumption is reasonable.

970722. A fair die is rolled three times. What is the probability that the three numbers obtained can be used as the lengths of the sides of a non-degenerate triangle?
970715. A fair coin is tossed n times. What is the probability that no consecutive "heads" occur in these n tosses?

You should aim for an answer in terms of familiar or known numbers, or an answer for n tosses in terms of previous values.

970708. n great circles are drawn on a sphere so that no three have a point in common. Into how many regions is the sphere divided?
970701. Arrange the three numbers
• 1000000 1000000 ,
• 999999 1000001 , and
• 1000001 999999
in increasing order.
970624. This week's problem is another puzzle or game. This particular one is a two-player board game.
970617. Professor Parity and her husband invite N-1 other couples to a party at their house (for a total of N couples). As people arrive, some shake hands with some of the others. No one shakes hands with her or his partner. After everyone has arrived, Professor Parity asks each person how many hands they shook, and finds that all 2N-1 people other than herself shook a different number of hands.
• How many hands did Professor Parity's husband shake?
• How many hands did Professor Parity shake?

970610. A lattice point in 3-dimensional space is one with all integer coordinates. If A and B are two lattice points, then the midpoint of the line segment in 3-space joining A and B may or may not be a lattice point. For example the midpoint of the line joining (0,0,0) to (1,2,3) is (1/2,1,3/2), not a lattice point, but the midpoint of the line joining (-1,0,1) to (1,2,3) is (0,1,2), a lattice point. Consider 9 lattice points in 3-space. There are 36 line segments, using all possible pairs as end-points. Can you find 9 lattice points so that none of the 36 midpoints is a lattice point?
970603.

Six cubes (each of side 1 cm.) are arranged as shown. A line segment is drawn from the centre of each cube to the four corners of the touching cubes. These line segments form a 3-dimensional geometric figure, each face of which is a rhombus.

• What is the length of each of these line segments?
• What are the lengths of the major and minor diagonals of these rhombuses?
• Find the area of each rhombus.
• How many faces does the geometric figure have? What is its total surface area?
• What is the volume of the solid which has these line segments as edges?

970527.

Six cubes (each of side 1 cm.) are arranged as shown. If a line segment is drawn from the centre of each cube to the centre of the four touching cubes,

• what is the length of each of these line segments?
• what geometric figure is formed?
• what is the volume of the solid which has these line segments as edges?

970520. A PROBABILITY PUZZLE: The equipment for a probability demonstration consists of a box containing five coins: two are double-headed, two are fair, and one is double-tailed. A coin is selected at random from the box and is tossed. It happens to land with heads showing. At this point the demonstrator states: "We now know that the coin cannot be double-tailed, so it must be either double-headed or fair. Two of the remaining four coins are double-headed, so there are 2 chances in four that the bottom face of the coin is heads. So we now know that there is a 50% chance that the bottom face is heads."

Some members of the audience disagree, with different calculations:

1. "No, the bottom face is heads if we have a double-headed coin. There were 2 such coins out of 5 coins total, so there is a 2/5 or 40% chance that the bottom face is heads."
2. "Yes, there were 4 chances in 5 of getting one of the double-headed or fair coins, and then 2 chances in 4 of getting a double-headed coin. So the chance that the bottom face is heads should be (4/5)x(2/4) = 2/5."
3. "No, both the answers so far are wrong. There were 4 chances in 5 of missing the double-tailed coin, but then there are 6 heads and 2 tails on the coins that are left. So 6 out of 8 faces are heads, and the overall chance that the bottom face is heads should be (4/5)x(6/8) = 3/5 or 60%."
4. "Yes, that's right, among the 10 faces of the original five coins there were exactly 6 heads, so the chance of any one of these being on the bottom is 6/10 = 3/5."
5. "No, it's simple. There are 8 faces remaining, OK, of which 6 are heads, but one of the heads is showing. So there are 5 heads of 7 possible faces left, and the chance of heads on the bottom is therefore 5/7 or a bit more than 71%."
6. "No, the coin was tossed, and so any one of the 6 heads out of 8 sides could have been on the bottom. So the chance of this happening is 6/8 = 75%."
Which (if any) of these answers is correct?
Hint

970513. This week's problem is a scaled-down version of the old "fifteen-puzzle". It has been tested on version 3 of Netscape, but may not work on all Net browsers.

970506. Bob has 44 loonies and 10 pockets. Is it possible for Bob to put the loonies into his pockets so that each pocket has a different number of loonies? No more than one pocket may be empty (0 loonies).
Hint

970430. A locker room has 100 lockers numbered 1, 2, ..., 100, which are all closed to begin with. 100 students go through the locker room one by one, opening and closing locker doors as follows:

• the first student opens all the doors;
• the second student closes every second door, starting with door 2;
• the third student changes the state of every third door, starting with door 3 (that is, if the door is found open, it is closed and vice versa);
• ...
• the nth student changes every nth door, starting with door n.
When all the students have been through the locker room, how many doors are open and how many are closed? Which doors are open?

Suppose in general there are N doors and N students. What is the general solution for the problem?
Hint

970423. Show that there is a positive integer with digits only 0s and 1s which is divisible by 1997. [Here, "divisible" means exactly divisible, i.e. no remainder.]
Hint

970416. A mouse encounters a 3cm x 3cm cube of cheese, and being of a geometric frame of mind, decides to eat the cheese as a sequence of sub-cubes, each 1cm x 1cm. The mouse will start with a corner sub-cube, and will move from one sub-cube only to an adjacent one (i.e. one that shares a face, not just a corner). Ignoring gravity, can the mouse eat all the sub-cubes and finish by eating the central sub-cube of the block of cheese?
Hint

To send a solution by e-mail, click this link.
Best student solution may be published.
Back to WOMA index page