Results 1 to 2 of 2

Math Help - Pigeon hole principle for odd or even product

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241

    Pigeon hole principle for odd or even product

    Let n be odd and suppose (x_{1},x_{2},\ldots,x_{n}) is any permutation of [n]. Prove that the product (x_{1}-1)(x_{2}-2)\cdots(x_{n}-n) is even. Is the result necessarily true if n is even? Give a proof or counterexample.

    If the x_{i}'s are written in ascending order, then each is paired with its additive inverse and each factor is zero, so the product is zero and we are done.

    Since the product of any two even numbers is even and the product of an even number and an odd number is even, we need all the terms to be odd if the product is to be odd. Since n is odd, the first term x_{1} and the last term x_{n} will be odd. The sum (or difference) of any two numbers is even if they are both even or both odd and it is odd if one is even and one is odd. Starting with the x_{i}'s in ascending order, we notice that each term has the two numbers paired so that each even x_{i} is paired with an even number and each odd x_{i} is paired with an odd number. We also notice that we can rearrange n-1 x_{i}'s so that each even x_{i} is paired with an odd number and each odd x_{i} is paired with an even number. But by the pigeon hole principle, there is one x_{i} left that is paired so that its term is even. Therefore with n being an odd number, the product of the terms must be even.

    By a similar argument, if n is even, there is a way to rearrange the terms so that the product can be odd. Example: (2-1)(1-2)(4-3)(3-4).

    Is this correct?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by oldguynewstudent View Post
    Let n be odd and suppose (x_{1},x_{2},\ldots,x_{n}) is any permutation of [n]. Prove that the product (x_{1}-1)(x_{2}-2)\cdots(x_{n}-n) is even. Is the result necessarily true if n is even? Give a proof or counterexample.

    If the x_{i}'s are written in ascending order, then each is paired with its additive inverse and each factor is zero, so the product is zero and we are done.

    Since the product of any two even numbers is even and the product of an even number and an odd number is even, we need all the terms to be odd if the product is to be odd. Since n is odd, the first term x_{1} and the last term x_{n} will be odd. The sum (or difference) of any two numbers is even if they are both even or both odd and it is odd if one is even and one is odd. Starting with the x_{i}'s in ascending order, we notice that each term has the two numbers paired so that each even x_{i} is paired with an even number and each odd x_{i} is paired with an odd number. We also notice that we can rearrange n-1 x_{i}'s so that each even x_{i} is paired with an odd number and each odd x_{i} is paired with an even number. But by the pigeon hole principle, there is one x_{i} left that is paired so that its term is even. Therefore with n being an odd number, the product of the terms must be even.

    By a similar argument, if n is even, there is a way to rearrange the terms so that the product can be odd. Example: (2-1)(1-2)(4-3)(3-4).

    Is this correct?
    Looks right. A somewhat abbreviated paraphrase: In the set [n]={1,2,...,n} with n odd, There are \displaystyle \left\lfloor \frac{n}{2} \right\rfloor even numbers and \displaystyle \left\lfloor \frac{n}{2} \right\rfloor+1 odd numbers. In order for the product (x_{1}-1)(x_{2}-2)\cdots(x_{n}-n) to be odd, each multiplicand (x_{i}-i) must be odd. That means that for even i, x_{i} must be odd, and vice versa. But the number of odd x_i is greater than the number of even i, therefore by the pidgeonhole principle there is at least one odd i for which x_i is odd. Thus for n odd, the product (x_{1}-1)(x_{2}-2)\cdots(x_{n}-n) is even.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 17th 2011, 07:44 PM
  2. Pigeon-hole Principle
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: August 5th 2011, 06:20 AM
  3. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 2nd 2011, 02:44 PM
  4. Pigeon Hole Principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 31st 2009, 07:59 AM
  5. Pigeon hole principle
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 30th 2007, 08:37 AM

Search Tags


/mathhelpforum @mathhelpforum