MathDB

Putnam 2008 B6

Source:

December 8, 2008

Putnammodular arithmeticlinear algebramatrixinductionfloor functionfunction

Problem Statement

Let

n

and

k

be positive integers. Say that a permutation

\sigma

of

\{1,2,\dots n\}

is

k

-limited if |\sigma(i)\minus{}i|\le k for all

i.

Prove that the number of

k

-limited permutations of

\{1,2,\dots n\}

is odd if and only if

n\equiv 0

or 1\pmod{2k\plus{}1}.

Back to Problems View on AoPS