26th VTRMC, 2004, Solutions

1. The answer is no. One example is

   A =

   (

   	0	1
   	0	0

   )

   B =

   (

   	0	0
   	1	0

   )

   C =

   (

   	1	0
   	0	0

   ).

   Then det M =/=  0 (expand by the fourth row), whereas det N = 0 (fourth row consists entirely of 0's). Therefore M is invertible and N is not invertible, as required.

2. For n a non-negative integer, as n increases from n to n + 6, we add 3 twice, 1 twice and 2 twice to f (n); in other words f (n + 6) = f (n) + 12. We deduce that f (n) = 2n when n = 0 (mod 6).

3. Let s_n denote the number of strings of length n with no three consecutive A's. Thus s₁ = 3, s₂ = 9 and s₃ = 26. We claim that we have the following recurrence relation:
   s_n = 2s_n-1 +2s_n-2 +2s_n-3    (n>3).
   The first term on the right hand side indicates the number of such strings which begin with B or C; the second term indicates the number of such strings which begin with AB of AC, and the third term indicates the number of such strings which begin with AAB or AAC. Using this recurrence relation, we find that s₄ = 76, s₅ = 222 and s₆ = 648. Since the total number of strings is 3⁶, we conclude that the probability of a string on 6 symbols not containing 3 successive A's is 648/3⁶ = 8/9.

4. The answer is no. Let us color the chess board in the usual way with alternating black and white squares, say the corners are colored with black squares. Then by determining the number of black squares in each row, working from top to bottom, we see that the number of black squares is
   4 + 4 + 5 + 4 + 4 + 4 + 5 + 4 + 4 = 38.
   Since there are 78 squares in all, we see that the number of white squares is 40. Now each domino cover 1 white and 1 black square, so if the board could be covered by dominoes, then there would be an equal number of black and white squares, which is not the case.

5. Expanding the sine, we have
   f (x) = cos x$$\int_{0}^{x}$$sin(t² - t) dt + sin x$$\int_{0}^{x}$$cos(t² - t) dt.
   Therefore

   $$\int_{0}^{x}$$ f'(x)

   $$\int_{0}^{x}$$

   f''(x) = - sin x sin(x² - x) + (2x - 1)cos x cos(x² - x)

   $$\int_{0}^{x}$$ +cos x cos(x² - x) + (1 - 2x)sin x sin(x² - x)

   $$\int_{0}^{x}$$

   
   
   We deduce that

   f (x) + f''(x) = (2x + 1)(cos x cos(x² - x) - sin x sin(x² - x)) = (2x + 1)cos x².

   
   

   Set g(x) = f''(x) + f (x). To find f⁽¹²⁾(0) + f⁽¹⁰⁾(0), we need to compute g⁽¹⁰⁾(0), which we can find by considering the coefficient of x¹⁰ in the Maclaurin series expansion for (2x + 1)cos x². Since cos x² = 1 - x⁴/2! + x⁸/4! - x¹²/6! + ..., we see that this coefficient is 0. Therefore g⁽¹⁰⁾(0) = 0 and the result follows.

6. Suppose first that there is an infinite subset S such that each person only knows a finite number of people in S. Then pick a person A₁ in S. Then there is an infinite subset S₁ of S containing A₁ such that A₁ knows nobody in S₁. Now choose a person A₂ other than A₁ in S₁. Then there is an infinite subset S₂ of S₁ containing {A₁, A₂} such that nobody in S₂ knows A₂. Of course nobody in S₂ will know A₁ either. Now choose a person A₃ in S₂ other than A₁ and A₂. Then nobody from {A₁, A₂, A₃} knows each other. Clearly we can continue this process indefinitely to obtain an arbitrarily large number of people who don't know each other.

   Therefore we may assume in any infinite subset of people there is a person who knows an infinite number of people. So we can pick a person B₁ who knows infinitely many people T₁. Then we can pick a person B₂ in T₁ who knows an infinite number of people T₂ of T₁, because we are assuming in any infinite subset of people, there is somebody who knows infinitely many of them. Of course, B₁ and B₂ know all the people in T₂. Now choose a person B₃ in T₂ who knows an infinite number of people in T₂. Then {B₁, B₂, B₃} know each other. Clearly we can continue this process indefinitely to obtain an arbitrarily large number of people who know each other.

   Remark A simple application of the axiom of choice shows that we can find an infinite number of people in the party such that either they all know each other or they all don't know each other.

7. Set b_n = 1 - a_n+1/a_n. Let us suppose to the contrary that S| b_n| is convergent. Then lim_{n--> $\infty$}b_n = 0, so may assume that | b_n| < 1/2 for all n. Now

   a_n+1 = a₁(1 - b₁)(1 - b₂)...(1 - b_n),
   hence

   ln(a_n+1) = ln a₁ + ln(1 - b₁) + ln(1 - b₂) + ... + ln(1 - b_n).

   
   
   Since lim_{n--> $\infty$}a_n = 0, we see that lim_{n--> $\infty$}ln(a_n) = - $\infty$. Now ln(1 - b)> - 2| b| for | b| < 1/2; one way to see this is to observe that 1/(1 - x) < 2 for 0 < x < 1/2 and then to integrate between 0 and | b|. Therefore lim_{n--> $\infty$}(- 2| b₁| - ... -2| b_n|) = - $\infty$. This proves that S| b_n| is divergent and the result follows.