Problem #3 is the one I need help with. However, someone said they wanted the fu

Question

Problem #3 is the one I need help with.

However, someone said they wanted the full worksheet.

Especially for problem 3.

Please explain and show steps and as the question says please use Ramsey.

Birds of a feather... wenty six birds landed on 5 electric wires, as shown below (don't worry, they are safe), Each wire long. now that regardless of how they land, two bir don't know anything about the spacing between same wire. Name the technique are goingt wires). Hint: first show that enough birds will be on the que that you are going to use for solving this problem. pigeon hole prirciple, one uire xill 26-1 ea ch (2 points) Among the 26 birds, we have 15 singing birds, and 21 red birds. How many singing red birds are there. In addition to your answer, write down a formula that explains the principle behind this question, and name that principle. 2. 3. (1 poin) Some birds flew away, and only the singing red birds remained on the wires. Can we find either 4 birds that are friends, or 3 birds that are strangers? Hint: use what you know about Ramsey numbers

Explanation / Answer

The remaining number of singing red birds = 10.

Now, the Ramsey number, R(m,n) gives us the solution to the general party problem as to the minimum number of guests that must be invited so that at least 'm' will know each other or at least 'n' will not know each other. Seeing the value of Ramsey number for R(3,4), we get R(3,4) = 9. So, in this case we can find either 4 birds that are friends, or 3 birds that are strangers.

The formal proof for R(3,4) < 10 is given below.

Lets select one fellow - say, X. The rest are split into 2 groups: those that know X (group P) and those that don't (group Q). There are just two possibilities: either |P| ? 6 or |Q| ? 4. (Otherwise |P?Q| < 10.)

If |P| ? 6, then there are 3 members of P that know each other; together with X they form a group of four mutual acquaintances. (Note: There can't be no 3 members that don't know each other as by further dividing these 6 in the same way, we can show so as otherwise there will be 4 strangers in which case we will be done).

If |Q| ? 4, then either they all know each other (in which case we will be done), some two are strangers. In the latter case, together with X these two form a group of 3 people who are mutual strangers.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.