MathDB

2017 | a_ib_i- a_jb_j i for permutations a_i, a_j of 1-2016

Source: 2017 Latvia BW TST P16

December 18, 2022

combinatoricsnumber theorydividesdivisible

Problem Statement

Strings

a_1, a_2, ... , a_{2016}

and

b_1, b_2, ... , b_{2016}

each contain all natural numbers from

1

2016

exactly once each (in other words, they are both permutations of the numbers

1, 2, ..., 2016

). Prove that different indices

i

and

j

can be found such that

a_ib_i- a_jb_j

is divisible by

2017