Results 1 to 7 of 7

Math Help - Whats wrong in this proof

  1. #1
    asc
    asc is offline
    Newbie
    Joined
    Dec 2007
    Posts
    8

    Smile Whats wrong in this proof

    We will prove the following statement by mathematical induction: Let L1, L2.....Ln. be n>=2 distinct lines in the plane, no two of which are parallel. Then all these lines have a point in common.

    1: For n=2 the statement is true, since any 2 nonparallel lines intersect.
    2: Let the statement hold for n = n0, and let us have n = n0+1 lines L1, L2,....Ln as in the statement. By the inductive hypothesis, all these lines but the last one (i.e. the lines L1, L2 ... Ln-1) have some point in common; let us denote it by x. Similarly the n-1 lines L1,L2.....Ln-2, Ln. have a point in common; let us denote it by y. The line L1 lies in both groups, so it contains both x and y. The same is true for the line Ln-2. Now L1 and Ln-2 intersect at a single point only and so we must have x=y. Therefoer all the lines L1....Ln have a point in common, namely the point x.

    Something must be wrong. Wat is it?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    This is a variant of the Polya's notorious "ALL Horses have the same color" paradox.

    Quote Originally Posted by Wikipedia
    In the middle of the 20th century, a commonplace colloquial locution to express the idea that something is unexpectedly different from the usual was "That's a horse of a different color!". George Pólya posed the following exercise: Find the error in the following argument, which purports to prove by mathematical induction that all horses are of the same color:
    * Basis: If there is only one horse, there is only one color.
    * Induction step: Assume as induction hypothesis that within any set of n
    horses, there is only one color. Now look at any set of n + 1 horses. Number them: 1, 2, 3, ..., n, n + 1. Consider the sets {1, 2, 3, ..., n} and {2, 3, 4, ..., n + 1}. Each is a set of only n horses, therefore within each there is only one color. But the two sets overlap, so there must be only one color among all n + 1 horses.
    And the explanation is here - All horses are the same color (paradox) - Wikipedia, the free encyclopedia

    Personally I think "same" is undefined for 1 element(you need two elements to say that).
    And in your case "meeting at a point" needs 2 or more lines. And the explanation is that, for the statement to be >defined< you need two or more points. Hence the base case=1 is INVALID. Choose 2 and you will be in trouble
    Last edited by Isomorphism; December 26th 2007 at 04:41 AM. Reason: some typos
    Follow Math Help Forum on Facebook and Google+

  3. #3
    asc
    asc is offline
    Newbie
    Joined
    Dec 2007
    Posts
    8
    so you mean this proof is right?? for less than or equal to two.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    GAMMA Mathematics
    colby2152's Avatar
    Joined
    Nov 2007
    From
    Alexandria, VA
    Posts
    1,172
    Awards
    1
    All horses are the same color Paradox?

    Wow, I really do learn something everyday here on MHF!
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by asc View Post
    so you mean this proof is right?? for less than or equal to two.
    NO!!
    I said for values of n greater than or equal to 2, statement does not hold. For the remaining values (how many remaining values are there???), it is not defined!!
    Thus the problem is not true in general
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by asc View Post
    We will prove the following statement by mathematical induction: Let L1, L2.....Ln. be n>=2 distinct lines in the plane, no two of which are parallel. Then all these lines have a point in common.

    1: For n=2 the statement is true, since any 2 nonparallel lines intersect.
    2: Let the statement hold for n = n0, and let us have n = n0+1 lines L1, L2,....Ln as in the statement. By the inductive hypothesis, all these lines but the last one (i.e. the lines L1, L2 ... Ln-1) have some point in common; let us denote it by x. Similarly the n-1 lines L1,L2.....Ln-2, Ln. have a point in common; let us denote it by y. The line L1 lies in both groups, so it contains both x and y. The same is true for the line Ln-2. Now L1 and Ln-2 intersect at a single point only and so we must have x=y. Therefoer all the lines L1....Ln have a point in common, namely the point x.

    Something must be wrong. Wat is it?
    Examine the inductive step. It implicitly assumes that n0>=3, but your base
    case has n=2, but it needs to be redone with n=3 for this to serve as a base
    case. Which cannot be done.

    RonL
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by CaptainBlack View Post
    Examine the inductive step. It implicitly assumes that n0>=3, but your base
    case has n=2, but it needs to be redone with n=3 for this to serve as a base
    case. Which cannot be done.

    RonL
    Ya right
    This holds for n <= 2 ....
    asc, I was referring to polya's paradox when I said n <= 1.
    Anyway I hope you got the idea. The moral of the story is "Be wary of people who say "the base case is trivial" in induction". They could be pulling a polya on ya
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Whats wrong with my maple input?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 21st 2010, 07:10 AM
  2. ok whats wrong/right about this answer?
    Posted in the Math Topics Forum
    Replies: 2
    Last Post: August 12th 2010, 11:03 PM
  3. whats wrong with my solution
    Posted in the Differential Equations Forum
    Replies: 2
    Last Post: April 1st 2010, 06:44 AM
  4. Replies: 0
    Last Post: April 16th 2009, 08:23 AM
  5. Whats wrong with the integration??
    Posted in the Calculus Forum
    Replies: 3
    Last Post: April 15th 2008, 11:20 AM

Search Tags


/mathhelpforum @mathhelpforum