Berkeley Math CircleFeb. 20, 2000

    Problem Solving for ``Beginners": Hints and Solutions
Instructor: Paul Zeitz, University of San Francisco     (zeitz@usfca.edu)

Here are some hints, full solutions, and solution sketches to the problems you got on Feb. 13, 2000. Some of these problems were quite difficult. Remember: you don't have to solve every problem, but you should cultivate a taste for (and stamina for) investigating problems.

1

If there are 1#1 people in the room, after one minute, there will be either 2#2 or 3#3 people. The difference between these two possible outcomes is 3. Continuing for longer times, we see that
4#4

In 5#5 minutes, then, one possible population of the room is just 5#5 people (assuming that one person entered each time). This is a multiple of 3, so all the possible populations for the room have to also be multiples of 3. Therefore 6#6 will not be a valid population.

2

This is yet another application of the Handshake Lemma, which says that if you add the number of handshakes each person in a group shakes, the sum will be even (since you are double-counting). Let 7#7 be the number of doors in room 8#8, where we include ``outside" as room 0 (having as its doors each of the doors in the house that open to the outside). Then by the same reasoning as in 3.4.7, the sum 9#9 must be even. By hypothesis, 10#10 are all even, which forces 11#11 to be even as well.

3

Experiment, and you will guess that only perfect squares stay closed. This is due to the parity: the number of divisors of 1#1 is odd if and only if 1#1 is a perfect square.

4

Consider the sum of the terms. We have

12#12

so the sum is an invariant; it is equal to zero no matter what the arrangement. A sum of an odd number of integers which equals zero (an even number) must contain at least one even number!

5

Let us indicate the population at any time by an ordered triple 13#13. Without loss of generality, consider an X-Z collision. The new population becomes 14#14 and you can easily verify that the difference between the X- and Z-populations is unchanged, while the difference between the X- and Y-populations has changed by 3 (likewise for the difference between the Z- and Y-populations). In general, the ``population gaps" are invariant modulo three. The initial population was 15#15. The X-Y population gap is 1, and hence it must always be congruent to 1 modulo 3. Thus there is no way that the X and Y populations can ever be the same.

6

The answer is no whenever there are an odd number of points. Let us find a rigorous argument for a specific case, say 7 points. Once again, we will argue by contradiction because assuming that we can draw the line gives us lots of specific information that we can work with. So, assume there is a line 16#16 which passes through the interior of each segment. This line cuts the plane into two regions, which we will call the ``left" and ``right" sides of 16#16. Without loss of generality, 17#17 lies on the left side of 16#16. This forces 18#18 to lie on the right side of 16#16, which in turn forces 19#19 to lie in the left, 20#20 in the right, etc. The important thing about this sequence is that 21#21 ends up on the left side, along with 17#17. Therefore 16#16 cannot pass through the interior of segment 22#22, a contradiction.

7

The answer is no. To see why, assume that there is a tiling, and we shall look for a contradiction. Color the squares of 23#23 rectangle with 12 colors in a cyclic ``diagonal" pattern as follows (we are assuming that the height is 66 and the width is 62):

1	12	11	24#24	1	12
2	1	12	24#24	2	1
3	2	1	24#24	3	2
25#25	25#25	25#25	26#26	25#25	25#25
5	4	3	24#24	5	4
6	5	4	24#24	6	5

    and then look at     

27#27	28#28
29#29	30#30

.

8

It is easy to verify that if 31#31 is a legal point, then 32#32 will be a multiple of 11. Since 33#33 is not a multiple of 11, the answer is no.

9

Notice that 34#34, so that 35#35 are replaced with 36#36. Therefore, if the sequence contains the values 37#37, the quantity

38#38

is invariant! Hence the final number will equal 39#39, no matter what the choices are.

10

For example, if 40#40 and the starting sequence was 362154, the cards evolve as follows:

41#41

It would be nice if the number of the card in the 1st place decreased monotonically, but it didn't (the sequence was 42#42). Nevertheless, it is worth thinking about this sequence. We shall make use of a very simple, but important, general principle:

43#43

In our case, either the sequence of 1st-place numbers repeats (since there are only finitely many), or eventually the 1st-place number will be 1 (and then the evolution halts). We would like to prove the latter. How do we exclude the possibility of repeats? After all, in our example, there were plenty of repeats!

Once again, the extreme principle saves the day. Since there are only finitely many possibilities as a sequence evolves, there exists a largest 1st-place value that ever occurs, which we will call 44#44 (in the example above, 45#45). So, at some point in the evolution of the sequence, the 1st-place number is 44#44, and thereafter, no 1st-place number is ever larger than 44#44. What happens immediately after 44#44 occurs in the 1st place? We reverse the first 44#44 cards, so 44#44 appears in the 44#44th place. We know that the 1st-place card can never be larger than 44#44, but can it ever again equal 44#44? The answer is no; as long as the 1st place value is less than 44#44, the reversals will never touch the card in the 44#44th place. We will never reverse more than the first 44#44 cards (by the maximality of 44#44), so the only way to get the card numbered 44#44 to move at all would be if we reversed exactly 44#44 places. But that would mean that the 1st-place and 44#44th-place cards both had the value 44#44, which is impossible.

That was the crux move. We now look at all the 1st-place values that occur after 44#44 appeared in the 1st place. These must be strictly less than 44#44. Call the maximum of these values 46#46. After 46#46 appears in 1st place, all subsequent 1st-place values will be strictly less than 46#46 by exactly the same argument as before.

Thus we can define a strictly decreasing sequence of maximum 1st-place values. Eventually, this sequence must hit 1, and we are done!

11

Let us call any set 47#47 of integers ``balanced" if it has the property that no matter which of the 48#48 is chosen for the referee, then one can decompose the remaining 22 numbers into two sets of 11 which have equal sums. Clearly if a set is balanced and we multiply or divide each element by the same number, it will still be balanced. Likewise, if a set is balanced and we add or subtract the same number to each element, it will still be balanced.

Now, let us suppose we have a balanced set 47#47 of positive integers. Let 49#49 be the sum of the 23 elements. If we pick 50#50 as referee, then we know that 51#51 must be even, since the remaining 22 elements can be partitioned into two sets with equal integer sums. By the same reasoning, 52#52 are all even. Therefore, if the set of integers is balanced, then all the elements 53#53 are the same parity (i.e., all are even, or all are odd).

Now consider our balanced set 47#47 of positive integers. We wish to show that all elements are equal. Let 54#54 be the minimum value of the elements. If we define 55#55 for 56#56, then the new set 57#57 will also be a balanced set of nonnegative integers. Some of the elements will be zero, and perhaps some are not. We would like to prove that they are all zero. Since some of the elements are zero, and zero is even, then all of the elements must be even. Consequently we can form a new set 58#58, where 59#59 for 56#56. But this set also has some zero elements, hence all of its elements are even, hence we can divide them all by 2 and get yet another balanced set of nonnegative integers. We can do this forever! The only integer which one can divide by 2 endlessly and still get an even integer as a result is zero. We conclude that the elements of 57#57 are all zero, i.e., the elements of 47#47 are all equal.

12

Consider the general problem of 1#1 marbles 60#60 with arbitrary starting locations. Each marble has a ``ghost path," the path it would travel if it did not bounce off its neighbors but instead passed through them. Whenever the marbles bounce, the actual path of a marble coincides with another marble's ghost path. After one minute has passed, each ghost path has returned to the original positions of each marble. Hence after one minute, the actual locations of the marbles are a permutation of the original positions. Moreover, this permutation must be a cyclic permutation, since the marbles cannot pass through one one another.

We claim that the permutation takes 61#61 to 62#62, where 63#63 is the ``counterclockwise excess," i.e. the difference modulo 1#1 between the number of counterclockwise marbles and the number of clockwise marbles.

To see this, let 64#64 be the velocity function for marble 65#65, where the velocities of 66#66 denote counterclockwise and clockwise motion, respectively. Notice that for any time 67#67,

68#68

since the number of clockwise and the number of counterclockwise marbles never changes (even when marbles collide). There will be finitely many bounces, and in any time interval between bounces, each velocity function is a constant. Let 69#69 be time values inside each interval, and let each each interval have length 70#70. For each marble 65#65, denote the net counterclockwise distance traveled from 71#71 to 72#72 by

73#73

Summing this over all marbles, we get

74#74

The only cyclic permutation associated with this sum of net distance traveled is the one which takes 61#61 to 62#62.

13

A very sketchy hint: orient the large rectangle so that one corner is a lattice point, and then consider the parity of the number of corner lattice points.

14

The idea is that triangular packing (so the centers of three circles are vertices of an equilateral triangle) is a more efficient use of space, however, to do this, you waste some space at the beginning of the rectangle. So you need a long rectangle to catch up.

15

Let us work out the first few terms of the product. We get

75#75

76#76

What are the (positive) exponents 77#77? All integers of the form 78#78, where the integers 79#79 satisfy 80#80. In other words, they will be numbers which, when written in base-3, only contain ones and zeros and end with a zero. In order, the first few exponents are (written in base-3) are

81#81

Of course, these numbers are just the base-2 representations of the sequence 82#82. In particular, to figure out 83#83, we just write 84#84 in base-2:

85#85

so the base-2 representation of 3994 is 111110011000, and 83#83 is equal to 111110011000 (base-3).

In other words,

86#86

16

See Concrete Mathematics by Graham, Knuth and Patashnik for a very nice discussion of this and related problems.

17

A bit of experimentation convinces us that if 87#87, the total private area is also equal to the total area of one planet. Playing around with larger 1#1 suggests the same result. We conjecture that the total private area is always equal exactly to the area of one planet, no matter how the planets are situated. It appears to be a nasty problem in solid geometry, but must it be? The notions of ``private" and ``public" seem to be linked with a sort of duality; perhaps the problem is really not geometric, but logical. We need some ``notation." Let us assume that there is a universal coordinate system, such as longitude and latitude, so that we can refer to the ``same" location on any planet. For example, if the planets were little balls floating in a room, the location ``north pole" would mean the point on a planet which was closest to the ceiling.

Given such a universal coordinate system, what can we say about a planet 88#88 which has a private point at location 89#89? Without loss of generality, let 89#89 be at the ``north pole." Clearly, the centers of all the other planets must lie on the south side of the 88#88's ``equatorial" plane. But that renders the north poles of these planets public, for their north poles are visible from a point in the southern hemisphere of 88#88 (or from the southern hemisphere of an planet that lies between). In other words, we have shown pretty easily that
90#90
After this nice discovery, the penultimate step is clear: to prove that
91#91
We leave this as an exercise (problem?) for you!

18

Let 92#92 be the interior of the rectangle with vertices 93#93. The line 94#94 intersects no lattice points in 92#92 (it passes through 95#95 and 96#96, but these points are not included in 92#92, and there are no other lattice points on the line, since 54#54 and 97#97 have no common divisors). Observe that 98#98 is just the number of lattice points that lie below this line in 92#92 for 99#99. Thus the left-hand sum is just the number of lattice points lying below the line in 92#92 . By similar reasoning, the right-hand sum is equal to the number of lattice points lying above the line. The common value must equal one-half of the total number of lattice points, which is of course 100#100. Observe that at least one of 54#54 and 97#97 must be odd, for otherwise the two numbers would share a common divisor (namely, 2). Consequently 100#100 is even and can be divided by 2.

19

Assume that the values are not all equal. Let 101#101 be the smallest value on the board. There must be a square containing 54#54 which is adjacent (WLOG) on the east by a square containing the value 97#97 which is strictly greater than 54#54. But then 54#54 is equal to the average of 4 numbers, none less than 54#54, one of which is strictly greater than 54#54. This is a contradiction.

20

This is very similar to the problem above.

21

The coin with smallest diameter cannot be tangent to more than 5 others.

22

Certainly when 1#1 is even, it is not true: Just imagine a set of pairs of people standing a few inches apart, with each pair quite far from every other pair. Now, if 1#1 is odd, first eliminate all pairs as in the above case, where two people end up shooting each other. Since 1#1 is odd, some dry people remain. Now consider the person whose nearest neighbor is maximal (there may be ties). This person will stay dry, since the only way that he could get shot is if someone else is as close to him as he is to his nearest neighbor. But that contradicts the fact that for each person, the distances to the others are different.

23

102#102, where 103#103 is the number of 1's in the base-2 representation of 1#1. This can be proven with induction, as well as many other methods.

24

Let there be 1#1 people. Each person is seated a distance 63#63 from his or her correct place, where 104#104 is measured counterclockwise. There are 1#1 people, but 105#105 different values of 63#63. Hence at least two people share the same distance 63#63.

25

The bug should travel along two line segments: first from 106#106 to 107#107, and then from 108#108 to 109#109. This is a consequence of the following principle: the bug must avoid quandrant II completely, even though a straight line path from 106#106 to 109#109 goes through quadrant II.

To see why this is true, let 54#54 and 97#97 be arbitrary positive numbers, and consider a path starting at 110#110 and ending at 111#111. Certainly the quickest route within quadrant II is the line segment 112#112, and the length of this path is 113#113. Now consider the alternate route 114#114 followed by 115#115. This path lies outside quadrant II (since quadrant II does not include the 89#89- or 116#116-axes) and has total length 117#117. Compare these two lengths. By the arithmetic-geometric mean inequality, we have 118#118, which implies that 119#119. Hence

120#120

We conclude that as long as the speed in quadrant II is less than 121#121, then any path from 122#122 to 123#123 that passes through quadrant II will take more time than the shortest non-quadrant-II path (along the 116#116- and 89#89-axes). Since 124#124, our bug will save time by avoiding quadrant II.

26

This problem is rather tricky unless we start by considering the 2-dimensional case. A bit of playing around convinces us that 5 is the magic number: If 5 lattices points are chosen in the plane (all distinct, of course), then one of the line segments joining two of these points will have a lattice point in the interior. The key ideas are parity and pigeonhole. There are only four distinct parity types for lattice points: (odd, odd), (odd, even), (even, odd), and (even, even). Hence among any 5 distinct lattice points, two must be of the same parity type, which means that the midpoint of the line segment joining them is a lattice point! The argument adapts easily to 3-dimensions.

27

Let triangle 125#125 have the largest area among all triangles whose vertices are taken from the given set of points. Let 126#126 denote the area of triangle 125#125. Then 127#127. Let triangle 128#128 be the triangle whose medial triangle is 125#125. (In other words, 129#129 are the midpoints of the sides of triangle 128#128. See figure.)

medial_triangle.eps scaled 500

Then 130#130. We claim that the set of points must lie on the boundary or in the interior of 128#128. Suppose a point 88#88 lies outside 128#128. Then we can connect 88#88 with two of the vertices of 125#125 forming a triangle with larger area than 125#125, contradicting the maximality of 126#126.

28

We will show that no palindrome can exist by contradiction. Assume that the concatenation of the numbers from 1 to 1#1 was the palindrome

131#131

Consider the longest run of consecutive zeros in 88#88; note that this exists, since 1#1 is surely greater than 10. There may be several runs of consecutive zeros that are all equally long; pick the last (rightmost) one. Observe that immediately to the left of this string is a single digit, and this digit plus the zeros forms one of the numbers from 1 to 1#1. For concreteness, suppose that the longest string of zeros was 0000. Then the rightmost such string obviously consists of the last digits of one of the numbers from 1 to 1#1, not the middle of one, and doesn't straddle two (for example, if the number was, say, 400005, then the number 400000 would have appeared to the left of it, contradicting the fact that 0000 is longest string of zeros. Likewise, the number that ends with 0000 had to start with a single digit, for if, say, the number was 7310000 then there would have been the number 7000000 to the left of it.

So, let us suppose that the rightmost string of 0000 is the last digits of the number 70000. Then, writing the predecessor and successor numbers, these four zeros are embedded in the string 699997000070001 Assume also, that there is at least one other string of 0000 in 88#88. Since 88#88 is a palindrome, the first 0000 must be embedded in the string 100070000799996. But that makes no sense, since the first time 0000 appears is as the last digits of the number 10000.

So the only remaining possibility is that there is only one 0000 string, which by necessity is at the exact center of 88#88 and is the last four digits of the number 10000. Writing the predecessor and successor, and letting ``132#132" mark the exact midpoint of 88#88, we must have the following string at the center:

133#133

But this isn't symmetrical (134#134), achieving our contradiction.

29

Consider the shortest path joining 135#135 with 136#136, where path means a walk along adjacent squares. The worst case scenario is that the path has length 1#1 (if 1 and 136#136 are at opposite diagonal corners). In any event, the members of the path will be at most 1#1 distinct numbers between 1 and 136#136, inclusive. If their successive differences were all less than or equal to 1#1, that means there are 105#105 successive differences which bridge the gap from 135#135 to 136#136. Since 137#137, the largest difference must be at least 2#2.

30

A very brief hint: show that eventually, the sequence will form a chain where each element will divide the next (when arranged in order). Moreover, the least element and the greatest element of this chain are respectively the greatest common divisor and least common multiple of all the original numbers.

31

Hint: look at diagonals.