MathDB

2

Part of 2020 Francophone Mathematical Olympiad

Problems(2)

new colony, n cities, 2020 languages, 2,020 galactic credits cheapest ticket

Source: The Francophone MO Juniors P2

8/10/2020
Emperor Zorg wishes to found a colony on a new planet. Each of the nn cities that he will establish there will have to speak exactly one of the Empire's 20202020 official languages. Some towns in the colony will be connected by a direct air link, each link can be taken in both directions. The emperor fixed the cost of the ticket for each connection to 11 galactic credit. He wishes that, given any two cities speaking the same language, it is always possible to travel from one to the other via these air links, and that the cheapest trip between these two cities costs exactly 20202020 galactic credits. For what values of nn can Emperor Zorg fulfill his dream?
combinatoricsFrancophone
A combinatorics problem with palindromic sequences

Source: The francophone mathematical olympiads P2

6/29/2020
Let a1,a2,…,ana_1,a_2,\ldots,a_n be a finite sequence of non negative integers, its subsequences are the sequences of the form ai,ai+1,…,aja_i,a_{i+1},\ldots,a_j with 1≤i≤j≤n1\le i\le j \le n. Two subsequences are said to be equal if they have the same length and have the same terms, that is, two subsequences ai,ai+1,…,aja_i,a_{i+1},\ldots,a_j and au,au+1,…ava_u,a_{u+1},\ldots a_v are equal iff j−i=u−vj-i=u-v and ai+k=au+ka_{i+k}=a_{u+k} forall integers kk such that 0≤k≤j−10\le k\le j-1. Finally, we say that a subsequence ai,ai+1,…,aja_i,a_{i+1},\ldots,a_j is palindromic if ai+k=aj−ka_{i+k}=a_{j-k} forall integers kk such that 0≤k≤j−i0\le k \le j-i What is the greatest number of different palindromic subsequences that can a palindromic sequence of length nn contain?
combinatoricsinductionSequenceFrancophone