Math 300 HW 7 1. Let S be the set of positive integer divisors of 1,000,000 (as shown in the diagram on one of the problems in the \"more practice\" folder). a) Prove that among any eight elements of S, there is some pair, one of which is a divisor of the other. b) Show that the above statement is not true if the number eight is replaced by 7. 2. 13 numbers are chosen out of the first 100 positive integers. Prove that three of them form a triangle. Not a triangular number, an actual triangle. Like if you had sticks of lengths 1,2, and 3, they would not form a triangle; the shorter two sticks would lie flat against the third. But sticks of lengths 2,3, and 4 would form a triangle. 3. Suppose you begin with a pile of n beans and split this pile into two smaller piles. Each time you split a pile, you multiply the number of beans in each of the two smaller piles you form. For example, if these piles have r and s beans in them, respectively, you compute rs. You keep doing this until all the piles have only one bean each, and thus can no longer be split. Show that no matter how you split the piles, the sum of the products computed n(n 1) . at each step equals 2 4. The ancient Egyptians had a system for writing fractions, but only with numerator 1. 8 , the Egyptians Such a fraction is called a 'unit fraction\".1 So for example, instead of 11 1 1 1 1 would have written the sum 2 + 5 + 37 + 4070 . This sum comes from the so-called greedy algorithm: the largest unit fraction that we can 8 8 5 5 take away from 11 is 12 . So we do so: 11 12 = 22 . From 22 , we can subtract 15 (but not 41 ): 5 3 3 1 3 1 1 15 = 110 . From 110 , subtract 37 : 110 37 = 4070 , which is a unit fraction. This gives 22 8 the sum written above, which is called an Egyptian fraction representation for 11 . Note that such a representation must consist of distinct unit fractions, so it is not allowed to 1 1 1 1 1 1 1 1 8 as 11 + 11 + 11 + 11 + 11 + 11 + 11 + 11 . write 11 Notice that after each subtraction, we end up with a fraction with a smaller numerator (8,5,3,1). So eventually, this process must end, no matter how horrible of a fraction we start out with. Thus, you are going to prove that every positive rational number has an Egyptian fraction representation. Hints. Let P (n) denote the statement that every positive rational number with numerator n in lowest terms has an Egyptian fraction representation. You will need to use strong induction. The assertion that each iteration of the greedy algorithm produces a fraction with a smaller numerator is key to making the induction go through. Prove this assertion n ? using the Division Algorithm: what is the smallest k such that k1 m 1 so, they also had a symbol for 32 , but you should ignore that for the sake of this