<p>A cat is chasing a mouse in an infinitely long line. They both hop. The cat c

Question

<p>A cat is chasing a mouse in an infinitely long line. They both hop. The cat can only hop 2,3 or 4 inches to the left or right. The mouse can only hop 1 inch in either direction or remain still. Suppose they take turns to move, although the mouse can give up the right of moving when it is its turn. Now, let P(n) be the statement<br />"if the cat and mouse are n inches apart and if the cat makes the first move, then the cat can catch the mouse for sure"<br /><br />Prove that P(n) is true for all integers n&gt;=0.</p>
<p>Hint: P(0), p(2),p(3),p(4) are easy, P(1) is tricky. once the basic step is complete, then the inductive step should prove P(n) for any n&gt;=5</p>

Explanation / Answer

Base cases:

For P(0), the mouse is already caught.

P(1): the cat should hop 2 in away from the mouse, so that the cat and mouse are separated by 3 in.

Then, no matter in what direction (left or right), the cat can catch the mouse.

P(2): the cat should hop 2 in toward the mouse and catch it.

P(3): same as above, but 3 in.

P(4): same as above, but 4 in.

Inductive step:

Assume P(k) holds for k < n.

Now let's examine P(k + 1).

If we have the cat jump 2 in toward the mouse, and the mouse doesn't move, then we have reduced this problem to P(k - 1). If the mouse moves left, then P(k - 2), if the mouse moves right, then P(k).

All of those are less than or equal to P(k), which we have assumed to be solvable. Therefore, P(n) is solveable for n 0.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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