MathDB

B6

Part of 2008 Putnam

Problems(1)

Putnam 2008 B6

Source:

12/8/2008
Let n n and k k be positive integers. Say that a permutation σ \sigma of {1,2,…n} \{1,2,\dots n\} is k k-limited if |\sigma(i)\minus{}i|\le k for all i. i. Prove that the number of k k-limited permutations of {1,2,…n} \{1,2,\dots n\} is odd if and only if n≡0 n\equiv 0 or 1\pmod{2k\plus{}1}.
Putnammodular arithmeticlinear algebramatrixinductionfloor functionfunction