MathDB

P2

Part of Russian TST 2019

Problems(2)

Permutations problem

Source: Russian TST 2019, Day 4 P2

3/22/2023
For each permutation σ\sigma of the set {1,2,…,N}\{1, 2, \ldots , N\} we define its correctness as the number of triples 1⩽i<j<k⩽N1 \leqslant i < j < k \leqslant N such that the number σ(j)\sigma(j) lies between the numbers σ(i)\sigma(i) and σ(k)\sigma(k). Find the difference between the number of permutations with even correctness and the number of permutations with odd correctness if a) N=2018N = 2018 and b) N=2019N = 2019.
combinatoricspermutations
Congruence modulo p^2

Source: Russian TST 2019, Day 6 P2

3/22/2023
Prove that for every odd prime number pp{}, the following congruence holds ∑n=1p−1np−1≡(p−1)!+p(modp2).\sum_{n=1}^{p-1}n^{p-1}\equiv (p-1)!+p\pmod{p^2}.
number theorycongruence