Problem Set 1 Problem 4. Let n be a postive integer. Prove that log2 n is rational if and only if n is a power of 2. Assume any basic facts about divisibility that you need; just state your assumptions explicitly Solution. Assumption: If n is a power of 2, then n is a power of 2 Proof. We prove that if n is a power of 2, then log2 n is rational and vice-versa Oe first, we prove that if n is a power of 2, then log n is rational. Assume that n is a power of 2. Then n=2 for some integer k>0. Thus, log2 n= log2 2=k, which is a rationa number Next, we prove that if log2 n is rational, then n is a power of 2. Assume that log2n ational. That means there exist integers a and b such that We can rewrite this equation as follows ( Take 2 to power of each side (Take the b-th power of each side. Thus, n is a power of 2. By our assumption n is a power of 2 Problem 5. A triangle is a set of three people such that either every pair has shaken hands or no pair has shaken hands. Prove that among every six people there is a triangle. Su gestion: Initially, break the problem into two cases: 1. There exist at least three people who shook hands with person X 2. There exist at least three people didnt shake hands with X (Why must at least one of these conditions hold?) Solution Proof. We use case analysis. Let X denote one of the six people. There are two possibili- 1. There exist three people who shook hands with person X. Now there are two fur ther possibilities (a) Among these three, some pair shook hands. Then these two and X form a triangle (b) Among these three, no pair shook hands. Then these three form a triangleProblem Set 1 3 Problem 4. Let n be a postive integer. Prove that log2 n is rational if and only if n is a power of 2. Assume any basic facts about divisibility that you need; just state your assumptions explicitly. Solution. Assumption: If nb is a power of 2, then n is a power of 2. Proof. We prove that if n is a power of 2, then log2 n is rational and vice­versa. First, we prove that if n is a power of 2, then log2 n is rational. Assume that n is a power of 2. Then n = 2k for some integer k ≥ 0. Thus, log2 n = log2 2k = k, which is a rational number. Next, we prove that if log2 n is rational, then n is a power of 2. Assume that log2 n is rational. That means there exist integers a and b such that: a log2 n = b We can rewrite this equation as follows: n = 2a/b (Take 2 to power of each side.) n b = 2a (Take the b­th power of each side.) Thus, nb is a power of 2. By our assumption, n is a power of 2. Problem 5. A triangle is a set of three people such that either every pair has shaken hands or no pair has shaken hands. Prove that among every six people there is a triangle. Sug￾gestion: Initially, break the problem into two cases: 1. There exist at least three people who shook hands with person X. 2. There exist at least three people didn’t shake hands with X (Why must at least one of these conditions hold?) Solution. Proof. We use case analysis. Let X denote one of the six people. There are two possibili￾ties: 1. There exist three people who shook hands with person X. Now there are two fur￾ther possibilities: (a) Among these three, some pair shook hands. Then these two and X form a triangle. (b) Among these three, no pair shook hands. Then these three form a triangle