MathDB

5

Part of 2016 IMC

Problems(2)

IMC 2016, Problem 5

Source: IMC 2016

7/27/2016
Let SnS_n denote the set of permutations of the sequence (1,2,…,n)(1,2,\dots, n). For every permutation π=(π1,…,πn)∈Sn\pi=(\pi_1, \dots, \pi_n)\in S_n, let inv(π)\mathrm{inv}(\pi) be the number of pairs 1≤i<j≤n1\le i < j \le n with πi>πj\pi_i>\pi_j; i. e. the number of inversions in π\pi. Denote by f(n)f(n) the number of permutations π∈Sn\pi\in S_n for which inv(π)\mathrm{inv}(\pi) is divisible by n+1n+1. Prove that there exist infinitely many primes pp such that f(p−1)>(p−1)!pf(p-1)>\frac{(p-1)!}{p}, and infinitely many primes pp such that f(p−1)<(p−1)!pf(p-1)<\frac{(p-1)!}{p}.
(Proposed by Fedor Petrov, St. Petersburg State University)
IMCIMC 2016prime numberspermutationscollege contests
IMC 2016, Problem 10

Source: IMC 2016

7/28/2016
Let AA be a n×nn\times n complex matrix whose eigenvalues have absolute value at most 11. Prove that ∥An∥≤nln⁡2∥A∥n−1. \|A^n\|\le \dfrac{n}{\ln 2} \|A\|^{n-1}. (Here ∥B∥=sup⁡∥x∥≤1∥Bx∥\|B\|=\sup\limits_{\|x\|\leq 1} \|Bx\| for every n×nn\times n matrix BB and ∥x∥=∑i=1n∣xi∣2\|x\|=\sqrt{\sum\limits_{i=1}^n |x_i|^2} for every complex vector x∈Cnx\in\mathbb{C}^n.)
(Proposed by Ian Morris and Fedor Petrov, St. Petersburg State University)
IMCIMC 2016college contestsmatrix