MathDB

11.7

Part of VII Soros Olympiad 2000 - 01

Problems(1)

sets of sequences, M<= 2n-4 (VII Soros Olympiad 2000-01 R1 11.7)

Source:

7/29/2021
Consider all possible functions defined for x=1,2,...,Mx = 1, 2, ..., M and taking values ​​y=1,2,...,n​​y = 1, 2, ..., n. We denote the set of such functions by T.T. By T0T_0 we denote the subset of TT consisting of functions whose value changes exactly by 1 1 (in one direction or another) when the argument changes by 11. Prove that if M≥2n−4M\ge 2n-4, then among the functions from of the set TT, there is a function that coincides at least at one point with any function from T0T_0. Specify at least one such function. Prove that if M<2n−4M <2n-4, then there is no such function.
algebraSequenceSequences