Math Help Forum - View Single Post

ThePerfectHacker · #10 September 23rd, 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.

The Following 2 Users Say Thank You to ThePerfectHacker For This Useful Post:
janvdl, qspeechc
$Donate to MHF$