Problem 37

ThePerfectHacker · #1 $Old$ 09-16-2007, 08:41 PM

1)Let $A,B\in \mathbb{R}^+$ . Define $a_0=A$ , $a_1=B$ and $a_n = a_{n-1}+a_{n-2} \mbox{ for }n\geq 2$ . Find the radius of convergence of $\sum_{n=0}^{\infty}a_nx^n$ .

The next two problems are for the younger kids, so give them a chance.

2)Let $S$ be a set (non-empty) of finite terms. A "partition" is breaking the set into two sets (non-empty) so that together they have the all the elements of $S$ but none of eachother. For example, let $S=\{1,2,3,4,5\}$ then $\{1,2,3\} \mbox{ and }\{4,5\}$ are partitions. But $\{1,2,3,4\} \mbox{ and }\{4,5\}$ are not. Say that $S$ has $n$ elements. How many different paritions are there in terms of $n$ ?

3)Given an $8\times 8$ checkerboard what is the maximum number of checkers which can be placed so that no two are adjacent. Prove your answer. "Adjacent" means either horizontally or veritcally next to eachother not diagnolly.

putnam120 · #2 $Old$ 09-17-2007, 08:40 PM

#1) the initial values of $a_0$ and $a_1$ do not matter. you just need to notice that $\lim_{n\to\infty}\frac{a_n}{a_{n-1}}=\phi=\frac{1+\sqrt{5}}{2}$
so to find the radius we just use the ratio test and get

$\lim_{n\to\infty}\left|\frac{x^na_n}{x^{n-1}a_{n-1}}\right|=\lim_{n\to\infty}\left|x\left(1+\frac{a_{n-2}}{a_{n-1}}\right)\right|=|x|\left(1+\frac{1}{\phi}\right)<1$

so $|x|<\frac{1}{1+\frac{1}{\phi}}$ which makes the radius of convergence $\frac{1}{1+\frac{1}{\phi}}=\frac{\phi}{1+\phi}$

putnam120 · #3 $Old$ 09-17-2007, 08:43 PM

about number 2.
are the partitions $\{1,2,3\}\cup\{4,5\}$ and $\{4,5\}\cup\{1,2,3\}$ considered to be different? this will affect the solution. i however assume that they are not.

ThePerfectHacker · #4 $Old$ 09-17-2007, 08:47 PM

Quote:

Originally Posted by putnam120 $View Post$

about number 2.
are the partitions $\{1,2,3\}\cup\{4,5\}$ and $\{4,5\}\cup\{1,2,3\}$ considered to be different? this will affect the solution. i however assume that they are not.

No they are not considered different maokid7, give the younger kids a chance.

For #1 it would be nice if you can give a full proof.

putnam120 · #5 $Old$ 09-17-2007, 09:46 PM

well ill start by proving my first assertion $\lim_{n\to\infty}\frac{a_n}{a_{n-1}}=\phi$

Let $L=\lim_{n\to\infty}\frac{a_n}{a_{n-1}}$ . Then after expanding $a_n$ by the recursion we have

$L=\lim_{n\to\infty}\frac{a_{n-1}+a_{n-2}}{a_{n-1}}=\lim_{n\to\infty}1+\frac{a_{n-2}}{a_{n-1}}$ . Notice that the second term is just the reciprocal of the original limit so we solve

$L=1+\frac1L\Longrightarrow L^2-L-1=0\Longrightarrow L=\frac{1\pm\sqrt{5}}{2}$ . We choose the positive solution because all the terms in the sequence are obviously positive and thus a negative ratio is not possible.

ThePerfectHacker · #6 $Old$ 09-17-2007, 10:18 PM

Quote:

Originally Posted by putnam120 $View Post$

well ill start by proving my first assertion $\lim_{n\to\infty}\frac{a_n}{a_{n-1}}=\phi$

Let $L=\lim_{n\to\infty}\frac{a_n}{a_{n-1}}$ . Then after expanding $a_n$ by the recursion we have

$L=\lim_{n\to\infty}\frac{a_{n-1}+a_{n-2}}{a_{n-1}}=\lim_{n\to\infty}1+\frac{a_{n-2}}{a_{n-1}}$ . Notice that the second term is just the reciprocal of the original limit so we solve

$L=1+\frac1L\Longrightarrow L^2-L-1=0\Longrightarrow L=\frac{1\pm\sqrt{5}}{2}$ . We choose the positive solution because all the terms in the sequence are obviously positive and thus a negative ratio is not possible.

But you are assuming the limit exists. First show that it exists.

putnam120 · #7 $Old$ 09-18-2007, 06:54 AM

First we show that the sequence is bounded.

$\left|\frac{a_n}{a_{n-1}}\right|\Longrightarrow 1<\left|1+\frac{a_{n-2}}{a_{n-1}}\right|<2$ since each term in the sequence is obviously larger than the previous term.

now define $R_n=\frac{a_n}{a_{n-1}}$ and look at the ratio $\frac{R_{n+1}}{R_n}=\frac{a_{n+1}a_{n-1}}{a_n^2}$ which is just $\frac{a_n^2-1}{a_n^2}<1$ . (easy induction proof ill leave the verification to the reader, but if this were for some competition i would include the proof

) so the sequence is monotonically decreasing.

and every bounded monotonic sequence converges.

ThePerfectHacker · #8 $Old$ 09-18-2007, 10:52 AM

Maybe you like this more.

janvdl · #9 $Old$ 09-20-2007, 04:34 AM

Quote:

Originally Posted by ThePerfectHacker $View Post$

3)Given an $8\times 8$ checkerboard what is the maximum number of checkers which can be placed so that no two are adjacent. Prove your answer. "Adjacent" means either horizontally or veritcally next to eachother not diagnolly.

That simply means that all the pieces should either be on the white squares or black squares only. Seeing as the amount of black squares is equal to the amount of white squares, then that means the maximum amount of pieces which can be placed is: $\frac{1}{2} (8 \times 8) = 32 \ pieces$

ThePerfectHacker · #10 $Old$ 09-23-2007, 10:28 PM

All these three problems are my own I hope you liked them.
-----
Maokid7 solved the first problem the trick here is to use the ratio test for evaluating radius of convergence for infinite series. The link I gave show that no matter what two possitive numbers are chosen thier ratio is the divine proportion. So the radius is $1/\phi$ .
-----
The second problem requires the knowledge combinations formula. Rieview them!

Now for a set $S$ we can constrct a partion in the following way. For simplicity let us say $S=\{ a,b,c \}$ and show how we can construct partitions. Let $P_1$ and $P_2$ be two partitions. So we cannot have $P_1 = \{ a,b,c\}$ then that would mean $P_2 = \{ \}$ (empty set) which is against the rules of the problem. Similarly $P_2 \not = \{a,b,c\}$ . However, let us focus on $P_1$ only. Because once we know $P_1$ then $P_2$ is completely determined. For example, if $P_1 = \{ a \}$ then $P_2 = \{ b,c\}$ , this is what I mean by being completely determined. So let us count the number of different ways of choosing elements for $P_1$ , because again once I know that we know what $P_2$ is. We cannot chose all the elements at once as explained above. But we can chose $2$ elements for $P_1$ the number of ways this can be done is ${3\choose 2} = 3$ . And these are:
$P_1 = \{ a , b\} \mbox{ and }P_2=\{c\}$
$P_1=\{ b, c\} \mbox{ and }P_2 = \{a \}$
$P_1=\{ a, c\}\mbox{ and }P_3 = \{b \}$ .
Now let us count the number of ways choosing $1$ element for $P_1$ there are ${3\choose 1}=3$ ways. And these are:
$P_1 = \{a\} \mbox{ and }P_2=\{b,c\}$
$P_2 = \{b\} \mbox{ and }P_2 =\{a,c\}$
$P_3 = \{c\} \mbox{ and }P_3 = \{a,b\}$
So in total there are ${3\choose 1}+{3\choose 2} = 6$ ways of creating ordered partitions. What do I mean by "ordered" I mean we make a distinction between which partition is first, $P_1$ , and which partition is second, $P_2$ . The important realization is that I overcounted the unordered partitions twice. Because these play symettric roles in this problem. Thus, the answer should be divided by two to give us $3$ .

Okay, since we understand this easy example let us generalize it for large values $n$ where $n$ is the number of elements in $S$ . If you follow everything what I did you will agree that the number of ordered partitions is:
${n\choose 1}+{n\choose 2}+...+{n\choose {n-1}}$ .
And the reason why I start with $1$ and go up to $n-1$ is because as I explained otherwise if we use all the elements in one partition then the remaining partition must be the empty set which we do not want. Do you realize that sum? Do you know the fabulous identity that,
${n\choose 0}+{n\choose 1}+...+{n\choose n} = 2^n$ .
But, ${n\choose 0} = {n\choose n} = 1$ .
Thus, the total number of ordered partitions is,
${n\choose 1}+...+{n\choose {n-1}} = 2^n - 2$ .
Divide this number by two to get unordered partitions which is,
$\boxed{ 2^{n-1} - 1 }$ .
-----
The last problem is easy but I posted it to come up with an elegant proof. Hopefully you will learn from this solution. We will use the "pigeonhole principle". It says given $n$ pigeonholes and $m$ holes, if we place these pigeons into the holes there there exists at least one hole containing $2$ pigeons. Think about it, a very trivial observation, but an important one. So this is what we will do (you will see why). Give each tile in the $8\times 8$ board a number. Let the upper left one be $1$ to its right $2$ to its right $3$ and go on up to $8$ . Then $9$ is directly below $1$ and go until to the right until $18$ . So cover up the entire board with these $64$ numbers. Now define "blocks". Block $\#1$ is the pair of $1,2$ tiles. Block $\#2$ is the pair of $3,4$ tiles. And so on. So there are $32$ different blocks. Okay, I argue that if I place $33$ peices on the checkerboard then two of them must be adjancet. To see this note that we have $32$ blocks. So two of the peices end up in the same block since $33>32$ . This means those two pieces must be adjacent to each other. This shows $33$ is too much. Now show it is possible to have $32$ non-adjacent peices which will show $32$ is the maximum number.