Miscellaneous Problems

Problem 83. Let S_n be the set of all pairs (x, y) with integral coordinates such that x ≥ 0, y ≥ 0 and x + y ≤ n. Show that S_n cannot be covered by the union of n straight lines.

Problem 82. Show that the sum of the squares of two consecutive Fibonacci numbers is again a Fibonacci number.

Problem 81. Show that the people at a party can be divided into two groups and sent to two different rooms in such a way that, for every person in either room, at least half that person’s friends at the party are in the other room. (You may assume that friendship is a symmetric relation).

Problem 80. Show that sin(x) ≤ x for x ≥ 0 and sin(x) ≥ x for x ≤ 0 for all x ϵ ℝ.

Problem 79. Suppose that f is a differentiable function on the interval [0, 2]. Prove that there exists an element x ϵ [0; 2] with f″(x) = f(0) – 2f(1) + f(2).

Problem 78. There are n people standing in a field, each carrying a gun. Every person shoots the person nearest to him (all people shoot at the same time, all distances are distinct). Show that at least one person survives if n is odd.

Problem 77. For every integer n, prove that there exists a subset S of {1, 2, . . . , n²} with n elements, so that the difference of any two distinct elements of S is not a square.

Problem 76. Suppose that there are n lines in the Euclidean plane ℝ² such that

(a) Every two lines intersect;

(b) Through any intersection point of two lines there goes at least one other line. Prove that all lines go through one point.

Problem 75. We start with a deck of 52 cards. We put all the cards in one row, face down. In the first round we turn all the cards around. In the second round we turn every second card around. In the third round we turn every third card around. We keep doing this until we complete round 52. Which cards will be faced up in the end?

Problem 74. (Gardner, M) Five sailors survive a shipwreck and swim to a tiny island where there is nothing but a coconut tree and a monkey. The sailors gather all the coconuts and put them in a big pile under the tree. Exhausted, they agree to go to wait until the next morning to divide up the coconuts.

At one o’clock in the morning, the first sailor wakes. He realizes that he can’t trust the others and decides to take his share now. He divides the coconuts into  five equal piles, but there is one left over. He gives that coconut to the monkey, buries his coconuts, and puts the rest of the coconuts back under the tree.

At two o’clock, the second sailor wakes up. Not realizing that the  first sailor has already taken his share, he too divides the coconuts up into  five piles, leaving one over which he gives to the monkey. He then hides his share and piles the remainder back under the tree.

At three, four and five o’clock in the morning, the third, fourth and fifth sailors each wake up and carry out the same actions.

In the morning, all the sailors wake up, and try to look innocent. No one makes a remark about the diminished pile of coconuts, and no one decides to be honest and admit that they’ve already taken their share. Instead, they divide the pile up into five piles, for the sixth time, and find that there is yet again one coconut left over, which they give to the monkey.

Problem 73. How many coconuts were there originally? (Find the smallest number of coconuts that is consistent with this story.)

Problem 72. Find an integer x such that x² + 1 is divisible by 130.

Problem 71. Let S be a subset of {1, 2, . . . , 2n} with n + 1 elements.

Problem 70. Show that one can choose distinct elements a, b ϵ S such that a divides b.