Programming Team Independent Study Homework Week #1 ...



Programming Team Independent Study Homework Week #1: Combinatorics

1) Let f(n) denote the number of different perfect covers of a 2-by-n chessboard. Evaluate f(1), f(2), f(3), f(4) and f(5). Try to find and verify a simple relation that the counting function f satisfies. Use this relation to compute f(12).

Solution

f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5, f(5) = 8

At this point it should be fairly obvious that the sequence looks just like the Fibonacci sequence shifted over by one. Hence we can conjecture that f(n) = Fn+1, where Fk denotes the kth Fibonacci number. Now, let's go to prove this relationship.

Consider tiling an nx2 board with n > 2.

| | | | | |

| | | | | |

We could put one tile on our new "column" and get

|Domino #1 | | | | |

|Domino #1 | | | | |

Then, we could tile the remaining squares in f(n-1) ways.

The only other alternative we have to lay that first domino horizontally to yield:

|Domino #1 |Domino #1 | | | |

| | | | | |

At this point we are forced to lay Domino #2 right below domino #1. (Those squares have to be covered by a vertical domino and we can't isolate the corner square.

Once we are done doing this, then we have the remaining (n-2)x2 grid to tile, which can be done in f(n-2) ways. This gives us the recurrence relation:

f(n) = f(n-1) + f(n-2)

Our initial conditions are f(1) = 1, f(2) = 2 which shows that f(n) = Fn+1.

2) Prove that in a group of n people there are two who have the same number of acquaintances in the group. (It is assumed that no one is acquainted with him or herself.)

Solution

Each person in the group must have a number of acquaintances in between 0 and n-1. If anyone has 0 acquaintances then no one has n-1 acquaintances because the rest of the people don't know the hermit. Similarly if anyone has n-1 acquaintances, no one is a hermit because all others are known by that person. (The assumption here is that an acquaintance is a symmetric relationship. If A knows B, B must know A.)

Thus, for any group of n people each of them has a number of acquaintances from the set {0,1,2,...,n-2} or {1,2,3,...,n-1}.

Since there are n people, each of whom have at most, n-1 distinct number of acquaintances, it follows that at least two people have the exact same number of acquaintances.

3) There are 100 people at a party. Each person has an even number (possibly zero) of acquaintances. Prove that there are three people at the party with the same number of acquaintances.

Solution

The possible number of acquaintances for each person comes from the set {0, 2, ..., 98}. This set has 49 values in it. Let these be our pigeonholes and the 100 people be the pigeons. By the pigeonhole principle, at least 3 people belong in one of the pigeonholes. It follows that some group of three people have the exact same number of acquaintances.

4) Prove r(3,3,3) ≤ 17.

Solution

Consider one vertex in the graph with 17 vertices. It has 16 emanating edges. Since each edge is one of three colors. It follows that at least 6 of those edges are the same color, from the pigeonhole principle. Without loss of generality, let this color be green. Now, consider the 6 vertices that those 6 edges are connected to. If any edge between those vertices is green, then we have our clique of size 3 with green edges only. If that is not the case, it follows that ALL the edges between those 6 vertices are colored with the other two colors (red and blue, for example). It was shown previously that if all the edges in a complete graph of 6 vertices is colored red or blue, then there must be a red clique of size 3 or a blue clique of size three, and the result (r(3,3,3) ≤ 17) follows.

5) A collection of subsets of (1,2,3, ...,n} has the property that each pair of subsets has at least one element in common. Prove that there are at most 2n-1 subsets in the collection.

Create a partition of the 2n subsets into 2n-1 groups where each group has two elements. In particular, each group will have a subset S and the subset {1,2,3,...,n} – S. Since there is a one-to-one correspondence between these two subsets for any S, we are guaranteed that the partition will work. For example, for n = 3, we get the following four groups:

{ {} , {1,2,3} }

{ {1}, {2,3} }

{ {2}, {1,3} }

{ {3}, {1,2} }

Clearly, if we attempt to pick 2n-1 + 1 subsets of {1,2,3,...,n} from the 2n-1 groups designated above, by the pigeonhole principle, we are guaranteed that we'll be picking two subsets from one of the groups. But, if this occurs, we can see that these two subsets will NOT share a common element.

To see that we can create a group of 2n-1 subsets that contain a common element, just consider all subsets of {1,2,3,...,n-1}. There are 2n-1 of these. Now, just add the element n to each of them and we'll ahve 2n-1 subsets each which contain the common element n.

6) How many sets of 3 numbers each can be formed from the numbers {1, 2, 3, ... , 20} if no consecutive numbers are to be in the same set?

Solution

Consider the numbers 1 through 17 laid out with gaps in between:

_ 1 _ 2 _ 3 _ ... _ 16 _ 17 _

There are 18 gaps. Now, choose 3 of those 18 for our set of three numbers. Here is an example.

_ 1 X 2 _ 3 _ 4 _ 5 X _ ... _ 16 _ 17 X

Now, read the list of numbers from left to right. Each time you encounter an X, put the next number there and add 1 to the remaining numbers. In this example, the set of three numbers formed would be {2, 7, 20}. (Basically the value for X is the number of values before it in the list.) Each placement of X's corresponds to a unique set of 3 numbers that satisfy the requirements. Each set of three numbers that satisfy the requirements correspond to a unique placement of X's. Thus, there is a one-to-one correspondence between the two and we can count the number of possible sets by just counting the number of ways to place the X's which is just [pic].

7) At a party there are 15 men and 20 women.

(a) How many ways are there to form 15 couples consisting of one man and one woman?

(b) How many ways are there to form 10 couples consisting of one man and one woman?

Solution

(a) Each man gets a woman. The first man has 20 choices, the second man 19, etc. Thus the total number is 20P15 = [pic]

(b) There are [pic] ways to choose the men who get to be in a couple. Naturally, each of these choices leads to distinct sets of couples. Now, consider one of these [pic] sets of men. Within the set, the first man has 20 choices for his woman, the second man has 19 choices, etc. Using the reasoning above, given the 10 men, there are 20P10 = [pic] possible groups of couples. Putting it all together we get [pic] ways to form 10 couples from the group.

8) How many integral solutions of

x1 + x2 + x3 + x4 = 30 satisfy x1 ≥ 2, x2 ≥ 0, x3 ≥ -5, x4 ≥ 8?

Solution

Pick new integers a,b, c and d with a = x1 – 2, b = x2, c= x3 + 5 and d = x4 – 8. Then the restrictions on these integers is a ≥ 0, b ≥ 0, c ≥ 0 and d ≥ 0. Substituting, we are now looking for the number of integral solutions in

(a + 2) + b + (c – 5) + (d + 8) = 30

with the restrictions above. This simplifies to

a + b + c + d = 25

Using the formula for combinations with repetition we get [pic] number of solutions.

9) There are 20 sticks lined up in a row and 6 of them are to be chosen.

(a) How many choices are there?

(b) How many choices are there if no two of the chosen sticks can be consecutive?

(c) How many choices are there it there must be at least two sticks between each pair of chosen sticks?

Solution

(a) This is a straight combination problem, so the answer is [pic].

(b) Using the same exact reasoning as question 6, place 14 sticks with 15 gaps between then:

_ | _ | ... | _

Now, just choose 6 of the 15 gaps. Each choice corresponds to a unique selection of 6 sticks from the 20 with no two adjacent. As before this correspondence is a one-to-one correspondence. So, the answer to our original question is the same has how to choose 6 locations out of 15 for the 6 sticks, which is [pic].

(c) We can layer this question on top of the previous one. When we are choosing the 6 spots out of 15, we are now no longer allowed to choose 2 consecutive spots again. Using the same logic we previously used, we find that we can pick 6 sticks out of 15 in a row with no two consecutive in [pic] ways, so this is the answer to our original question.

10) Answer question number nine when there are n sticks lined up and k are to be chosen.

(a) [pic], the explanation should be obvious.

(b) Using the same reasoning as in question 9, we provide n – k sticks with n – k + 1 gaps between them. Of those n – k +1 gaps, we much choose k to place our k sticks. This can be done in [pic] ways.

(c) Finally, now we are forced to choose k sticks from a line of n – k + 1 sticks, with no two consecutive. Using the same reasoning, we get [pic] ways to complete the task. Hopefully you can draw the generalization that if we require there to be at least s sticks in between each chosen, then the this can be done in [pic] ways.

11) For how many pairs of consecutive integers in the set {1000, 1001, ..., 2000} is no carrying required when the two integers are added?

Solution

There are 1000 pairs to consider. Let abcd represent the smaller of the two numbers in a pair. We know that a = 1. We also know that b, c and d can NOT be 5, 6, 7 or 8. (The reason for this is that if any of them were, the successive number is guaranteed to have 5, 6, 7, 8 or 9 in the corresponding digit.) Furthermore, we also know that if all three are confined to the set {0, 1, 2, 3, 4} that there is definitely no carrying involved since the subsequent number will have all digits from {0,1,2,3,4,5}. There are 5x5x5 = 125 pairs. Now, we must count all of the pairs where at least one of the digits b, c, d is 9. If d is not 9, but one of the others is, then a carry is involved with that digit. Thus, we are only looking for situations where d=9 OR both c and d are equal to 9 OR b,c and d are equal to 9. When just d=9, there are 25 combinations that work for b and c (using the previous logic). When c and d are equal to 9 there are 5 combinations that work for b. Finally there is one combination with b, c and d equal to 9. The final answer is 125 + 25 + 5 + 1 = 156.

12) Prove that among any 16 distinct positive integers not exceeding 100 there are four different ones a, b, c and d such that a + b = c + d.

Solution

Let the 16 distinct integers be x1, x2, ... , x16 with xi < xi+1 , for 0 < i < 16. Consider pairs of the form (xi , xj) with i > j. There are 120 such pairs. Note that in all these pairs 0 < xi – xj < 100. Thus, by the pigeonhole principle, there will be at least two pairs with the same difference. If these two pairs have 4 distinct values, we are done. To see this consider the pairs (xi , xj) and (xm , xn). If these are four distinct values then xi – xj = xm – xn and by adding terms to both sides we get xi + xn = xm + xj, the desired property.

The problem here is that the four aren't guaranteed to be distinct. It's possible that one of the four values is repeated: (xi , xj) and (xj , xn). In this case, we don't have four separate numbers for our construction. Imagine that a single term, such as xj was involved in another two pairs that had this property, say (xa , xj) and (xj , xb). It's clear that the difference between the two terms in each of these pairs is different than the ones in the previous two pairs. So we get the following equations:

xi – xj = xj – xn → 2xj = xi + xn

xa – xj = xj – xb → 2xj = xa + xb

Thus, if one number is involved with 2 sets of pairs like this, we see that there do exist 4 numbers with the desired property.

Thus, let's assume that each number in the set is involved in at most one arrangement where it's the number in the middle. That still leaves us with 120 – 16 = 104 pairs of values, which still exceeds the 99 possible differences that those 104 pairs could have. Using the pigeonhole principle, it follows that two of these differences are the same and that they correspond to a distinct set of four values with the desired property.

13) Let n = 231319. How many positive integer divisors of n2 are less than n but do not divide n?

Solution

n2 = 262338. A divisor of n2 must be of the form 2a3b with a ≤ 62 and b ≤ 38. There are 63x39 of these divisors. Of these divisors, one is n, so there are 63x39 – 1 of them that are not n. Exactly half of these are less than n and the other half are more than n. (This is because for each divisor D, there is a corresponding divisor n2/D. If the first is greater than n the second is less than n and vice versa.) Thus, we have [pic] divisors of n2 that are less than n. Of these divisors, exactly 32x20 – 1 are divisors of n that are less than n. (The 1 subtracted out is for n itself.) Thus, when we list the [pic] divisors of n2 that are less than n, we simply don't want to count the 32x20 – 1 are divisors of n that are less than n. This makes our final answer [pic].

14) Let T = {9k | k is an integer, 0 ≤ k ≤ 4000}. Given that 94000 has 3817 digits and that its first (leftmost) digit is 9, how many elements of T have 9 as their leftmost digit?

Solution

Consider the first three powers of 9: 9, 81, 729. Generally speaking, it looks as if one power of 9 has n digits, the following power of 9 has n+1 digits. Of course, this won't always be true. It is possible for a power of 9 to be greater than 10k and less than 10k+1/9. In this case, multiplying by 9 won't add a new digit to the result. (For example, when we multiply 104 by 9, we get 936, which also has three digits.) Notice that in each of these cases, the leading digit of the previous power of 9 must be a 1 and that the following leading digit is a 9. In fact, we ONLY get a leading digit of 9 RIGHT at one of these transitions. So the key then is to count how many transitions there are.

Let f(k) denote the number of digits in 9k. (Thus, f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 3, etc.) For each value of k where f(k-1) = f(k), the corresponding value of 9k starts with a 9. Thus, our goal becomes counting the number of values of k for which f(k-1) = f(k).

Consider the sequence f(0), f(1), f(2), ..., f(4000). There are 4001 numbers in this sequence, of which, 3817 are distinct. Each repeated value occurs only twice (multiplying by 81 guarantees a greater number of digits..) so to determine the number of repeated values, just take 4001 – 3817 = 184 values in T start with 9.

15) Determine, with proof, if it is possible to arrange 1, 2, ..., 1000 in a row such that the average of any pair of distinct numbers is not located in between the two numbers.

Solution

It is possible and we can prove this through induction. First, we will prove through induction on n that it's possible to arrange the values 1, 2, 3, ..., 2n an ordering the has the desired quality, for all positive integers n.

Base case: n = 1, the ordering 1, 2 works trivially since there are no intermediate values.

Inductive hypothesis: For an arbitrary positive integer n=k there exists a valid ordering of 1, 2, 3, ..., 2k.

Inductive step: For n = k+1, prove that there exists a valid ordering of 1, 2, 3, ..., 2k+1.

To prove the inductive step, break up the group of numbers into two sets:

{1,3,5,...,2k+1-1} and {2, 4, 6, ..., 2k+1}. Our arrangement will have all the numbers in the first set, followed by all the numbers in the second set. Using our inductive hypothesis, we know that we can arrange {1, 2, 3, ..., 2k} in a desired manner. Take this arrangement and multiply each number by 2 to get an arrangement of {2, 4, 6, ..., 2k+1}. Clearly, this arrangement still has the desired property since each number and average have been multiplied by 2. Now, take this same arrangement and subtract 1 from each value to create an arrangement of 1,3,5,...,2k+1-1. This arrangement ALSO has the desired property. By subtracting one from each term, we have decreased the average of each pair of numbers by 1 as well. But, since each middle term has also been decreased by 1, since the old ordering had this property, the new one will also. (To be more explicit, if we have an old ordering where c is in between a and b, we are guaranteed that c does NOT equal the average of a and b. If we subtract 1 from a, b and c, then c will STILL note equal the average of a and b, since both c AND the average of a and b have been decreased by 1.)

Thus, we know that if there does exist a pair of numbers with the average in between, the first number in the pair would have to be in the first half of the set and the second number would have to be in the second set (since we have already proved that no pair exists within the first half or second half of the list.) But, all the numbers in the first half are odd and all the numbers in the second half are even. All possible averages created by these pairs are non-integral. Thus, the property holds for our newly created ordering of 1, 2, 3, ..., 2k+1.

As an example, consider the ordering 1, 3, 2, 4. We will build an ordering of size 8 from it. First we create 2, 6, 4, 8 by doubling each number. This will be the second half of our list. Next subtract one from each term to get 1, 5, 3, 7. Our total list is 1, 5, 3, 7, 2, 6, 4, 8.

But, this doesn't prove our claim for the original question. To do so, just take our listing of 1, 2, 3, ..., 1024 that is guaranteed by the proof above, and yank out the numbers 1001 through 1024 in the list. Yanking numbers out does NOT create any new "averages", thus if the old list had no averages in between pairs of numbers, the new one doesn't either.

16) In the first lecture we showed that in the game of NIM, our goal was to force the opponent into a position where each "column" has even parity. It was shown that whenever this is NOT true, we could construct a positive binary number based on subtracting either 0 or 1 from each column. What we failed to prove is that the corresponding binary number was less than or equal to the maximum number of marbles in a pile. Prove that this is the case.

Solution

That corresponding number does NOT correspond to how many pebbles to take and that was the flaw in my explanation. It just corresponds to which bits to toggle. In the example given in class, we had:

bit: 3 2 1 0

7: 0 1 1 1

9: 1 0 0 1

12: 1 1 0 0

15: 1 1 1 1

Bits 3, 2 and 0 must be toggled. Since we are subtracting, we CAN'T toggle the most significant bit from 0 to 1, this must be toggled from 1 to 0. So we have three courses of action:

1) Make the 9 row look like 0 1 0 0

2) Make the 12 row look like 0 0 0 1

3) Make the 15 row look like 0 0 1 0

In order to do #1, we take 5 marbles from pile 2.

In order to do #2, we take 11 marbles from pile 3.

In order to do #3, we take 13 marbles from pile 4.

Since the starting number is greater than the ending number (toggliing the most significant bit from 1 to 0 guarantees this), we are guaranteed to be taking a positive number of marbles. Finally, we can always choose any pile, so long as it has enough marbles in the most significant bit that has to be toggled. (Obviously, such a pile will always exist because in order to achieve odd parity, at least one of the values must have a 1 in the column.)

17) (Optional) Stephen showed by writing a computer program that there are 588 ways to arrange three oak, four birch and five elm trees in a row without any two trees of the same type adjacent to one another. Show this fact mathematically, without the aid of a computer program.

I haven't made any progress on this one...

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download