Problem of the Month

March 2014 Problem

Here it is, the last problem of the month for the winter. This should be a good challenge!

You might know these words already, but here they are just in case:

  • Permutation. A permutation of length n is a way of putting the numbers 1 through n in order. For example there are six different permutations of length 3, namely 123, 132, 213, 231, 312, and 321.
  • Derangement. A derangement is a permutation where no number ends up in its original location. So the derangements of length 3 are 231 and 312.

Every permutation is either even or odd. To see which it is, write the numbers 1 through n at the top and bottom. Then, connect the original number up top to the permuted number below. As you see in this diagram, the permutation 231 features lines that connect: the top 1 to the bottom 2, the top 2 to the bottom 3 and the top 3 to the bottom 1.

Then, count the total number of crossings in the drawing. Since the permutation 3142 has three line crossings, it is labeled as odd. The permutation 231 has only two, so it is labeled as even.

Okay, ready?

Problem 1

Compute the difference, (# of even permutations of length 2014) − (# of odd permutations of length 2014).

Problem 2

Compute the difference, (# of even derangements of length 2014) − (# of odd derangements of length 2014).

Due by noon on April 4th to Professor Abrams.

Congratulations to past problem solvers:

  • Onye Ekenta

Rules:

You must work alone, or with a single partner. You may not use any external sources like the internet, mathematical software (e.g. Maple), etc., with the exception of books. You may use physical books that exist on paper.  Submit solutions either in person or electronically to Prof. Aaron Abrams before the deadline. Explain all your reasoning as clearly as possible.

Prizes:

A prize of (your choice!) either a dollar or a donut (mmm . . . Pure Eats) will be awarded to the first person (or pair) who submits a complete and correct solution to each problem.  A prize will also be awarded to the first first-year student(s) who submit(s) a complete and correct solution to each problem. 

Note: At the end of the year, a larger prize will be awarded to the person who has solved the most problems during the course of the year. This prize will probably be a math book of some kind.