# Some Interesting Problems to Investigate

Many of the following problems are related to number theory; others connect to different branches of mathematics. The diversity is intentional and seeks to break the habit of reacting mechanically (i.e., without thought) to well-known problem types. Instead, one should ask the good questions of mathematical inquiry, experiment, push ideas to their end and then come up with more ideas. Eventually, something will crack. Be prepared, there is not only a diversity of mathematical disciplines below, but also a diversity of difficulty levels. Some of these problems can be dispatched in a few minutes with a good insight -- others might take days to solve. Good Luck!

1. Let $x = 1^1 + 2^2 + 3^3 + 4^4 + \cdots + 100^{100}$. Find the unit's digit of $x$.

2. Every point of a plane is colored one of 2 colors. Prove that there will always be an equilateral triangle with all its vertices of the same color. Also prove that there exists a rectangle, all of whose vertices are the same color.

3. Show that $7^n - 1$ is divisible by 6 for all positive integers $n$.

4. Let $a, b, c$ be integers satisfying $a^2 + b^2 = c^2$. Prove that $abc$ must be even.

5. Let $N$ denote the natural numbers $\{1, 2, 3, 4, \ldots\}$. Consider a function $f : N \rightarrow N$ which satisfies $f(1) = 1$, $f(2n) = f(n)$, and $f(2n+1) = f(2n) + 1$ for all $n \in N$. Find a simple algorithm for computing $f(n)$. Your algorithm should be a single sentence long, at most.

6. Into how many regions is the plane divided by $n$ lines where no two of the lines are parallel, and no three lines meet at a single point?

7. A platonic solid is defined to be a regular, convex polyhedron whose faces are congruent, regular polygons, with the same number of faces meeting at each vertex. Prove that there are only five such platonic solids (i.e., tetrahedron, cube, octahedron, dodecahedron, and icosohedron) under the assumption that $V - E + F = 2$, where $V$ counts the number of vertices, $E$ counts the number of edges, and $F$ counts the number of faces of the polyhedron.

8. The vertexes of a triangle are labeled A, B, and C. Some number of additional points on segment $\overline{AB}$ are also labeled either A or B. Similarly, some number of additional points on segment $\overline{AC}$ are labeled either A or C, and some additional points on segment $\overline{BC}$ are labled either B or C. Finally, some number of points from the interior of the triangle are chosen and labeled either A, B, or C. Then, segments are drawn, connecting various pairs of these points, so that any area bounded by segments that does not contain any points in its interior is a triangle. Prove that one of these triangles formed has vertices A, B, and C.

9. Lockers in a row are numbered 1, 2, 3, ..., 1000. At first, all the lockers are closed. A person walks by, and opens every other locker, starting with locker #2. Another person walks by and changes the 'state' of every third locker starting with locker #3. Changing the 'state' means closing open lockers and opening closed lockers. Then another person changes the state of every fourth locker starting with locker #4. This process continues until no more lockers can be altered. Which lockers will be closed?

10. A rising music star needs to stay in a hotel for possibly up to 7 days. While he has no money, he does have a gold chain having 7 links. He strikes a deal with the hotel owner. The owner will allow the aspiring musician to stay at the hotel if he pays the owner one gold link each day. Since the musician may not need to stay the entire week and he doesn't completely trust the owner, he refuses to pay for any days in advance. The owner tells him that he can "take change" in the form of links paid previously. Assuming that the musician does indeed stay for the full 7 days, what is the least number of links that need be cut out of the chain? As a generalization, what if the chain has $n$ links? How many cut links are needed for a stay of $n$ days? (Hints: If the muscian needs to stay for 7 days, only one cut link is needed. If he needs to stay for 895 days (and he has a chain of the same length), only 6 cuts are needed. Which links must be cut in each situation? Now, can you generalize this process for n links?

11. Prove that a $14 \times 14$ board can't be tiled with $1 \times 4$ rectangles.

12. An island is inhabited by five men and a pet monkey. One afternoon the men gathered a large pile of coconuts, which they proposed to divide equally among themselves the next morning. During the night one of the men awoke and decided to help himself to his share of the nuts. In dividing them into five equal parts he found that there was one nut left over, which he promptly gave to the monkey. He then hid his one-fifth share, leaving the rest in a single pile. Later during the night, another man awoke with the same idea in mind. He went to the pile, divided it into five equal parts, and found that there was one coconut left over. This he gave to the monkey, and then hid his one-fifth share, restoring the rest to one pile. During the same night, each of the other three men arose, one at a time, and in ignorance of what had happened previously, went to the pile, and followed the same procedure. Each time, one coconut was left over, and it was given to the monkey. The next morning all five men went to the diminished coconut pile and divided it into five equal parts, finding one coconut left over. What is the least number of coconuts the original pile could have contained?

13. Suppose you have three $16 \times 16$ chessboards, each with a single square missing. The first is missing one of the corner squares. The second is missing a square in its second column, eighth row. The third is missing one of the four center squares. Demonstrate that it is possible to cover the remaining squares of each board with L-shaped pieces, where each L-shaped piece covers three squares. Given a $2^n \times 2^n$ chessboard that is missing one square, is it always possible to cover the remaining squares of the chessboard with L-shaped pieces? Prove this claim, or provide a counter-example.

14. In Roman numerals, the following two equations are correct: $$L I X + L V I = C X V \quad \quad \quad X \cdot X = C$$ Now consider the preceeding as letters of the alphabet as representative of Arabic numerals. If we substitute the proper Arabic numbers, the "equations" are also correct. Each letter denotes the same and unique numeral throughout the problem. What are the two "equations" in Arabic numerals?

15. Let $a$, $b$, and $c$ be integers such that $a^6+2b^6=4c^6$. Show that $a=b=c=0$.

16. Suppose $N$ is a three digit natural number whose (positive integer) powers all end in the same three digits as $N$. Find all possible values for $N$ and prove that the aforementioned property is satisfied for any values you find.

17. Without the aid of technology (e.g., calculators, Mathematica, etc...), find the value of the expression: $$\left( 1 - \frac{1}{4} \right) \left( 1 - \frac{1}{9} \right) \left( 1 - \frac{1}{16} \right) \left( 1 - \frac{1}{n^2} \right) \cdots \left( 1 - \frac{1}{225} \right)$$

18. Alice, Bob, and Carol took the same series of three examinations -- one in Algebra, one in Geometry, and one in Calculus. For each examination, there was one mark of $x$, one mark of $y$, and one mark of $z$, where $x$, $y$, and $z$ are distinct positive integers. The total of the marks obtained by each of the students was: Alice (20), Bob (10), and Carol (9). If Bob placed first in the algebra examination, who placed second in the geometry examination? Prove your result.

19. Given any set of ten natural numbers between 1 and 99 inclusive, prove that there are two disjoint nonempty subsets of the set with equal sums of their elements.

20. I invite 10 couples to a party at my house. I ask everyone present, including my wife, how many different people they shook hands with. It turns out that everyone shook hands with a different number of people. If we assume that no one shook hands with his or her partner, how many people did my wife shake hands with? (I did not ask myself any questions.)

21. Suppose you are given 80 seemingly identical gold coins. Indeed, 79 of the coins are identical in every way -- but one of them is counterfeit and slightly lighter than the others. Using a pan balance, how can you locate the counterfeit coin in only four weighings? As a generalization, suppose you are given $n$ such coins containing a single (lighter) counterfeit. What is the least number of weighings required to find the counterfeit coin? What if it is not known if the counterfeit coin is heavier or lighter than the other coins?

Hints: The interesting case is when we do not know if the counterfeit coin is too heavy or too light. If this is the case, and if we have 13 coins, we can locate in three weighings which coin is counterfeit (although we still will not know whether it is too heavy or too light -- that takes one more weighing). If we have 14 coins, four weighings are necessary. Find a system for finding the counterfeit coin in each of these cases (n = 13, n = 14).

22. We have 11 stones with integer weights. For any stone, we can split the other 10 stones into two groups of 5 with equal total weights. Prove that all of the stones have the same weight. How can this result be generalized?

Hints: Consider the total weight of all of the stones. What can you say about the individual stone weights if the total is odd? ...what if the total is even? Given one collection of stone weights that satisfy this condition, can you find another collection of stone weights that also satisfies this condition? ...can you find one with a smaller total weight?

23. Prove that a $14 \times 14$ board can't be tiled with $1 \times 4$ rectangles. What can you say about tiles of other dimensions?

Hints: Is there a way you can color the board black and white, so that no matter where it is placed, a $1 \times 4$ rectangle covers one and only one black square? What does this tell you about the number of $1 \times 4$ rectangles needed?

24. A $6 \times 6$ board is tiled with $1 \times 2$ dominoes. Prove that there exists a "fault" line which splits the board into two rectangles but does not intersect the interior of any domino. What if the board has different dimensions? When must a fault line exist? Can you say anything about the number of fault lines that must exist?

Hints: What can you say about the number of squares on either side of a potential fault line? What about the number of dominos a given line cuts if it is not a fault line? Try to argue indirectly. Given any domino, how many lines of the board will "cut" the domino? Is there a relationship between the number of dominoes and the number of "cutting" lines?

25. Four different colored chips (red, yellow, green, and blue) are placed on a clock so that they cover four consecutive hours. A chip may be moved in either a clockwise or a counter-clockwise direction over four other hours to a fifth hour, provided that there is no chip already on this fifth hour. After a certain number of moves the same initial hours covered will again be covered by chips. How many rearrangements of the four chips are possible as a result of this process?

Hints: Without loss of generality, suppose the red, yellow, green, and blue chips cover the hours 1, 2, 3, and 4, respectively. Consider the hours (in order) that the red chip might cover if no other chips were in his way. If other chips are in the way, where can they go to get out of the way? Remember, the chips ultimately come back to the same positions -- what must be true if red comes back to hour 1? ...to hour 2?, ...hour 3? ...hour 4?

26. $n$ quarters are stacked so that they are all "heads up". The top coin is removed, flipped over, and then replaced on the top of the stack. Then, the top two coins are removed, flipped over (as a group), and then replaced on the top of the stack. Then, this is done to the top three coins, and then the top four coins, etc..., until finally, the entire stack of $n$ coins is flipped over. Then, this process is repeated, starting again with flipping just the top coin. How many flips does it take to return the stack to "all heads up"? This application might help...

27. Find all integers having the property that, when the third digit is deleted, the resulting number divides the original one.

Hints: Suppose the integer sought is called $N$ and this number with its third digit deleted is called $D$. If the If $D$ divides $N$, then there is some integer $M$ such that $\frac{N}{M} = D$. Consider the values of $N$ and $10\frac{N}{M}$ as determined by the (base $10$) digits of $N$ (like we discussed when we considered alternate bases). What can you say about their difference if $M 10$? ...what if $M = 10$?

28. Take four arbitrary natural numbers, $a$, $b$, $c$, and $d$. Prove that if we use them to find the four numbers $a_1$, $b_1$, $c_1$, and $d_1$, which are equal, respectively to the differences between $a$ and $b$, $b$ and $c$, $c$ and $d$, $d$ and $a$ (taking the positive difference each time), and then we repeat this process with $a_1$, $b_1$, $c_1$, and $d_1$ to obtain four other numbers $a_2$, $b_2$, $c_2$, and $d_2$, and so on, we eventually must obtain four zeros.

29. How many regions are created by $n$ lines on a paper if $k$ of the lines are parallel and the other $n-k$ lines intersect all other lines (no three lines intersect at a point).

Hints: Find the number of regions created when k = 1, 2, 3, 4 and n = k, k+1, k+2, ... 7. If you hold k constant, is there a pattern to the regions created as n varies? What is the pattern to the patterns? (when k is changed, how does the pattern change?). Why does the pattern hold? If you know how many regions are created with m lines, can you determine how many regions are formed with m+1 lines? Can you prove something using induction?

30. Josephus, an American spy posing as a member of Al-Qaida, was trapped in a large cave with 2011 Al-Qaida terrorists. The Americans, who were just outside the cave, were readying their final assault. There was no question that Al-Qaida was outmatched. Choosing suicide over capture, the terrorists decided they would form a circle and start killing themselves. They agreed they should start with their leader and then from his position, counting by twos, each man would take his own life, working their way around the circle several times until all had died. What position in the circle should Josephus take to ensure he is the last man standing?

31. Several positive numbers are written on a blackboard. Erase any two distinct integers and replace them with their greatest common divisor and and their least common multiple. Prove that eventually the numbers will stop changing.

32. Calissons are a French candy that looks like two equilateral triangles meeting along an edge. They come in a box shaped like a regular hexagon. Suppose a hexagonal box with side length n is completely filled with calissons of sides 1, where each calisson is placed in one of three different directions. Prove that a filled box contains as many calissons in one direction as in any other.

To make things clearer, the picture below shows 3 calissons in each direction in an hexagonal box with side length 3 that is not yet filled. Regardless of how we finish filling the box (i.e., covering up all of the dots) with additional colored calissons/rhombuses, we are trying to prove that the final number of green rhombuses will equal the final number of red rhombuses, which in turn will equal the final number of brown rhombuses.

33. Find the number of ways to pair off and join by chords $2n$ points on the circumference of a circle so that no chords intersect.

Hints: Suppose you know the number of ways for every n where $1 \le n \le k$. Can express the number of ways for n = k+1. Think about the choice for the first chord -- can you express your next number of moves in terms of problems where n is smaller? Can you prove something with strong induction?

34. Find the number of incongruent triangles with perimeter $n$ whose sides are all of integer length.

Hints: you may wish to consider even and odd values of $n$ seperately. The geometry is not really relevant. All that is important is how many ways can you write n as a sum of three integers greater than zero. Equivalently, how many ways can you write n-3 as a sum of three non-negative zeros. Make lists of how many ways you can do this for n = 3, 4, 5, 6, 7, 8, 9, 10, 11, 12. Is there a pattern?

35. Which perfect squares are also the sum of the first $n$ integers for some $n$ (which, by the way, are called "triangular numbers")? Find a way to generate them.

Hints: What do you know about $1+2+3+\cdots+n$? Try to find the next such number in terms of the previous two numbers. This pattern is actually much easier to find than an explicit formula for the $n^{th}$ term, once you have enough examples of square-triangular numbers.

36. A certain whole number contains 300 one's and the rest of the digits are zero. Can any number of this type be a perfect square?

37. Find and prove a formula for the product of all the positive integral divisors of any number?

38. Let $a$, $b$, $c$, $d$ be integers. Show that the product
$$(a-b)(a-c)(a-d)(b-c)(b-d)(c-d)$$ is divisible by 12

39. Determine the least possible value of the natural number $n$ such that $n!$ ends in exactly 1987 zeros.

40. Let $n$ be an integer. Can both $n+3$ and $n^2 +3$ be perfect cubes?

41. An integer $x \ge 2$ with $n$ digits is called an automorph if the last $n$ digits of $x^2$ are the same as those of $x$. Find all automorphs with four digits (with initial zeros allowed).

42. It is possible to list the ordered pairs whose coordinates are taken from $\{0,1\}$ so that any two consecutive ordered pairs in this list differ in exactly one coordinate:

$$(0,0), (0,1), (1,1), (1,0)$$

Note, in this problem, we consider the first and last elements in our list to also be "consecutive", at least in a modular sense.

Can this be done with the list of ordered triples whose coordinates are taken from $\{0,1\}$? ...ordered quadruples of the same sort? Describe a way to list ordered $n$-tuples of the same variety in a consistent manner, or find the first $n$ where the corresponding ordered $n$-tuples can't be listed in this way.

◆ ◆ ◆