Ecs20: homework 5 help

Homework 5 HelpGetting Started: Induction and Word Problems There is a lot of information provided in this exercise. You should first figure out exactly what youneed to provide. In this case you must: Use mathematical induction to show that if there are n people at the party, then you canfind the celebrity, if there is one, with 3(n − 1) questions.
Also, a key definition in this exercise is that of a celebrity. A person is a celebrity if: (1) This person is known by every other guest at the party.
(2) This person does not know any other guests at the party.
You could write this using quantifiers, but it is not necessary.
Before we get started with mathematical induction, we should state our conjecture P (n). Withproblems like this, P (n) might not be a nice, precise, and compact mathematical statement.
In this case, P (n) is given by the exercise. Restated, it is: Let P (n) be the statement that for n people at a party, then you can find the celebrity(if there is one) with 3(n − 1) questions.
What does it mean to say P (4) = 9? It means that for 4 people at a party, we can find the celebrityin 3(4 − 1) = 9 questions.
We know that with mathematical induction, we must provide a basis step. Usually, P (1) is givenas the basis step. Again, with problems like this there will be more text than math: Notice that for n = 1, there is a single person at the party. Lets call this person Xander.
There are no other people at the party. Therefore, Xander knows nobody else at theparty (condition 2). Likewise, every other guest knows Xander since there are no otherguests (condition 1).
This means that, without asking any questions, we know Xander is a celebrity. ThereforeP (1) = 3(1 − 1) = 3(0) = 0 is true.
This works for our proof, but does not give us much insight on what is going on. In situations likethis, I suggest looking at a specific example for a slightly larger number of people. For example,look at P (3). To make discussion easier, suppose the 3 people at the party are Xander, Yasmin,Zane. Ask if Xander knows Yasmin. If Xander knows Yasmin, then Xander is not a celebrity (dueto condition 2). If Xander does not know Yasmin, then Yasmin is not a celebrity (due to condition1). Notice that we eliminate one person from being a celebrity.
I don’t have the time to typeset the full examples here. However, you should be able to work outthe rest on your own.
If you have the time and are still lost, also work out P (4) and see how you can reuse the questionsfrom P (3), and how many extra questions you must ask about the extra person.
Step 4: What is the inductive hypothesis? Our inductive hypothesis is that we assume P (k) is true. Therefore, we assume: Assume P (k) is true, meaning that for k people at a party, you can find the celebrity (ifthere is one) with 3(k − 1) questions.
You will use this hypothesis in the next step.
Step 5: Show P (k + 1) is true given P (k)? This is often the most time consuming and difficult part of the mathematical induction. Show showthat if P (k) is true, then P (k + 1) must also be true. It helps to know what we want to prove. Inthis case, we want to prove that: P (k + 1) is true, meaning that for k + 1 people at a party, you can find the celebrity (ifthere is one) with 3((k + 1) − 1) = 3k questions.
This is where you are on your own! I do have one hint, which is also given in your book. Whendealing with k + 1 people, ask a question to the extra person. Then break up your argument towhether there is a celebrity, or if there is not a celebrity. Once you get the problem down to kpeople, you can use the inductive hypothesis.
If you just don’t know where to start, work out specific examples. Like I mentioned earlier, workout P (3) and P (4) and look at the difference and similarities between the two.
Examples will help you figure out how to proceed with the inductive step for this exercise. Workout what phone calls must be made for G(4), and then for G(5).
For G(4), you need to find how many phone calls must be made for 4 people.
For example, suppose we have four people labeled A, B, C, and D. Person A knows about scandal1, B knows about scandal 2, C knows about scandal 3, and D knows about scandal 4.
If A calls B, then they both know scandal 1 and 2. Then if C calls D, then they both know scandal3 and 4. Now, have A call C. At this state, A and C will know all four scandals. Finally, have Bcall D. Then B and D will know all four scandals. Our total number of phone calls is 4. If k = 4,then P (k) involves ≤ 2 ∗ 4 − 4 = 4 phone calls.
Now, consider what happens for 5 people. Say we add to our bunch person E which knows scandal5. This time, let our first call be between D and E. Now D and E know both scandal 4 and 5.
Then, make all the same phone calls as above in G(4). At the end, A through D will know all thescandals. (Make sure you understand this.) However, E still does not know scandals 1 through 3. (Since all of the phone calls from G(4) arenever made to E.) One more phone call, between A and E will update E on all the juicy gossip.
Therefore, we updated everyone with two extra phone calls.
Generalize this, and then you are good to go! (Easier said than done, right?) Notice that this is basically the representation of a number in binary form. For example, let ourconjecture be: Let P (n) be the statement that n may be written as a sum of distinct powers of two.
First, look at odd numbers. We know that P (3) is true since 20 + 21 = 1 + 2 = 3. Similarly, P (5)is true since 20 + 22 = 1 + 4 = 5. Similarly, P (7) is true since 20 + 21 + 22 = 1 + 2 + 4 = 7.
Now, look at even numbers. For P (2) we get 21 = 2. For P (4) we get 22 = 4. For P (6) we get21 + 22 = 2 + 4 = 6.
There is a pattern. Odd numbers always include 20, and even numbers never include 20. (Remem-ber, we are dealing with distinct powers of 2.) Now, look at what happens when we go from an even number to an odd number. For example: Then, look at what happens when we go from an odd number to an even number. For example: This doesn’t look quite as nice. However, if we look at: You can see that each exponent increased by one from P (3) to P (6). It just so happens that3 × 2 = 6. We can use P (3) since we are using strong induction.
Confused about the difference between strong induction and normal induction? In normal induc-tion, we assume P (k) is true. In strong induction, we assume P (k) is true, and P (k − 1) is true,and P (k − 2) is true, . . . , and P (1) is true.
Therefore if k = 6, we assume that P (5), P (4), P (3), P (2), and P (1) are all true. Therefore we canuse P (3) and assume 3 can be written as a sum of distinct powers of two when we are trying toshow P (6).
You can work out more examples on your own. (For example, look at n = 8 and n = 4.) Youshould be able to find a pattern, and use it for your mathematical induction.

Source: http://www.phien.org/ucdavis/ta/ecs20-s07/notes/homework5notes.pdf