computer sciece(Computation Theory)

posted by .

Find the error in the following proof that all horses are the same color.
CLAIM: In any set of h horses, all horses are the same color.
PROOF: By induction on h.
Basis: For h = 1. In any set containing just one horse, all horses clearly are the same color.
Induction step: For k  1 assume that the claim is true for h = k and prove that it is true for h = k + 1 . Take any set H of k + 1 horses. We show that all the horses in the set are the same color. Remove one horse from this set to obtain the set H1 with just k horses. By the
induction hypothesis, all the horses in H1 are the same color. Now replace the removed horse and remove a di erent one to obtain the set H2. By the same argument, all the horses in H2 are the same color. Therefore all the horses in H must be the same color, and the proof is complete.

  • computer sciece(Computation Theory) -

    "...prove that it is true for h = k + 1 . Take any set H of k + 1 horses. We show that all the horses in the set are the same color. Remove one horse from this set to obtain the set H1 with just k horses...."

    The induction process requires to prove that given the proposition is true for k, then k+1 is true.
    The above prove is proving that given k+1 is true, then k is true. So k decreases, and does not help to prove that k+2 ... is true.

Respond to this Question

First Name
School Subject
Your Answer

Similar Questions

  1. math please help

    One day, a person went to horse racing area, Instead of counting the number of human and horses, he instead counted 74 heads and 196 legs. Yet he knew the number of humans and horses there. How did he do it, and how many humans and …
  2. maths

    A & B together have 132 horses. If 0.25 of the no. of A 's horses = 0.14285714285714.... of no. of B 's horses, how many horses each has?
  3. ps 361

    there are 16 horses. 8 chickens are white. 7 horses run away. how many horses are left?
  4. Math

    joe has a farm with 99 animal, four times as many cows as horses, twice as many horses as pigs. how many cows, horses and pigs are there?
  5. Math

    On joes farm there are 99 animals. There are four times as many cows as horses on the farm. There are twice as many horses as lives. How many horses, cows, and pigs are there?
  6. mason

    seven horses are entered in a race. If two horses are tied for first​ place, and there are no ties among the other five ​horses, in how many ways can the seven horses cross the finish​ line?
  7. math

    horses are entered in a race. If two horses are tied for first​ place, and there are no ties among the other five ​horses, in how many ways can the seven horses cross the finish​ line?
  8. math

    seven horses are entered in a race. If two horses are tied for first​ place, and there are no ties among the other five ​horses, in how many ways can the seven horses cross the finish​ line?
  9. satistical mobeling

    there are 12 horses in a horse show competition. the top three winning horses receive money. how many possible money winning orders are there for a competition with 12 horses ?
  10. math

    john has horses and chickens he has 3 less chickens than horses, if you count the total number of legs for chickens and horses you will get 24 how many chickens does john have?

More Similar Questions