Berkeley Math Circle
Problem Solving for ``Beginners"

Paul Zeitz, University of San Francisco, zeitz@usfca.edu

Ferbuary 13 2000

1. At first, a room is empty. Each minute, either one person enters or two people leave. After exactly $a_1,a_2,...,a_n$ minutes, could the room contain people?

2. Show that if every room in a house has an even number of doors, then the number of outside entrance doors must be even as well.

3. Lockers in a row are numbered . At first, all the lockers are closed. A person walks by, and opens every other locker, starting with locker #2. Thus lockers are open. Another person walks by, and changes the ``state" (i.e., closes a locker if it is open, opens a locker if it is closed) of every third locker, starting with locker #3. Then another person changes the state of every 4th locker, starting with #4, etc. This process continues until no more lockers can be altered. Which lockers will be closed?

4. Let $a_1,a_2,...,a_n$ represent an arbitrary arrangement of the numbers . Prove that, if is odd, the product
   
   
   
   is an even number.

5. A bubble-chamber contains three types of sub-atomic particles: 10 particles of type X, 11 of type Y, 111 of type Z. Whenever an X- and Y-particle collide, they both become Z-particles. Likewise, Y- and Z- particles collide and become X-particles and X- and Z-particles become Y-particles upon collision. Can the particles in the bubble chamber evolve so that only one type is present?

6. Let be distinct points in the plane. Connect the points with the line segments . Can one draw a line which passes through the interior of every one of these segments?

7. Is is possible to tile a rectangle with rectangles?

8. Start with a set of lattice points. Each second, we can perform one of the following operations:

   (a)

   The point ``gives birth" to the point .

   (b)

   If and are both even, the point ``gives birth" to the point .

   (c)

   The pair of points and ``gives birth" to .

   For example, if we started with the single point , operation #1 yields the new point , and then operation #2 yields , and then 9 applications of operation #1 gives us and then operation #3 applied to and gives us , etc.

   If we start with the single point , is it possible to eventually get the point ?

9. Initially, we are given the sequence . Every minute, we erase any two numbers and and replace them with the value . Clearly, we will be left with just one number after 99 minutes. Does this number depend on the choices that we made?

10. The cards of a deck (where is an arbitrary positive integer) are labeled . Starting with the deck in any order, repeat the following operation: if the card on top is labeled , reverse the order of the first cards. Prove that eventually the first card will be 1 (so no further changes occur).

11. Twenty-three people, each with integral weight, decide to play football, separating into two teams of eleven people, plus a referee. To keep things fair, the teams chosen must have equal total weight. It turns out that no matter who is chosen to be the referee, this can always be done. Prove that the 23 people must all have the same weight.

12. Several marbles are placed on a circular track of circumference one meter. The width of the track and the radii of the marbles are negligible. Each marble is randomly given an orientation, clockwise or counterclockwise. At time zero, each marble begins to travel with speed one meter per minute, where the direction of travel depends on the orientation. Whenever two marbles collide, they bounce back with no change in speed, obeying the laws of inelastic collision.

    What can you say about the possible locations of the marbles after one minute, with respect to their original positions? There are three factors to consider: the number of marbles, their initial locations, and their initial orientations.

13. A rectangle is tiled with smaller rectangles, each of which has at least one side of integral length. Prove that the tiled rectangle also must have at least one side of integral length.

14. Imagine a long rectangle, where is an integer. Clearly, one can pack this rectangle with circles of diameter 1, and no more. (By ``pack" we mean that touching is OK, but overlapping is not.) On the other hand, it is not immediately obvious that circles is the maximum number possible for packing a rectangle. Investigate this, and generalize to rectangles.

15. (Turkey, 1996) Let
    
    
    
    where are nonzero and . Find .
16. The Josephus Problem. A group of people are standing in a circle, numbered consecutively clockwise from to . Starting with person #2, we remove every other person, proceeding clockwise. For example, if , the people are removed in the order , and the last person remaining is #5. Let denote the last person remaining.

    (a)

    Compute for .

    (b)

    Find a way to compute for any positive integer . You may not get a ``nice" formula, but try to find a convenient algorithm which is easy to compute by hand or machine.

17. We are given planets in space, where is a positive integer. Each planet is a perfect sphere and all planets have the same radius . Call a point on the surface of a planet private if it cannot be seen from any other planet. (Ignore things such as the height of people on the planet, clouds, perspective, etc. Also, assume that the planets are not touching each other.) It is easy to check that if , the total private area is , which is just the total area of one planet. What can you say about ? Other values of ?

18. Let and be integers greater than one which have no common divisors. Prove that
    
    
    
    and find the value of this common sum.
19. Imagine an infinite chessboard that contains a positive integer in each square. If the value in each square is equal to the average of its four neighbors to the north, south, west, and east, prove the values in all the squares are equal.
20. There are 2000 points on a circle, and each point is given a number which is equal to the average of the numbers of its two nearest neighbors. Show that all the numbers must be equal.

21. Given a set of coins in the plane, all with different diameters. Show that one of them is tangent to at most 5 of the others.

22. (Canada, 1987) On a large, flat field, people () are positioned so that for each person the distances to all the other people are different. Each person holds a water pistol and at a given signal fires and hits the person who is closest. When is odd, show that there is at least one person left dry. Is this alwaystrue when is even?
23. Let be the number of odd terms in the row of Pascal's Triangle which starts with . For example, , since the row
    
    
    
    contains 4 odd numbers. Conjecture a formula (or an easy way of computing) .
24. People are seated around a circular table at a restaurant. The food is placed on a circular platform in the center of the table, and this circular platform can rotate (this is commonly found in Chinese restaurants that specialize in banquets). Each person ordered a different entrée, and it turns out that no one has the correct entrée in front of him. Show that it is possible to rotate the platform so that at least two people will have the correct entrée.
25. A bug is crawling on the coordinate plane from to . The bug travels at constant speed one unit per second everywhere but quadrant II (negative - and positive -coordinates), where it travels at units per second. What path should the bug take to complete its journey in minimal time? Generalize!
26. Consider 9 lattice points in three-dimensional space. Show that there must be a lattice point on the interior of one of the line segments joining two of these points.
27. (Korea, 1995) Consider finitely many points in the plane such that, if we choose any three points among them, the area of triangle is always less than 1. Show that all of these points lie within the interior or on the boundary of a triangle with area less than 4.
28. (Russia, 1996) A palindrome is a number or word that is the same when read forward and backward, for example, ``176671" and ``civic." Can the number obtained by writing the numbers from 1 to in order be a palindrome?
29. Place the integers (without duplication) in any order onto an chessboard, with one integer per square. Show that there exist two adjacent entries whose difference is at least . (Adjacent means horizontally or vertically or diagonally adjacent.)

30. (St. Petersberg City Olympiad, 1996) Several positive integers are written on a blackboard. One can erase any two distinct integers and write their greatest common divisor and least common multiple instead. Prove that eventually the numbers will stop changing.
31. (A. Soifer, S. Slobodnik) Forty-one rooks are placed on a chessboard. Prove that there must exist 5 rooks, none of which attack each other. (Recall that rooks attack each piece located on its row or column.)