Subcontests
(6)Italian Mathematical Olympiad 2022 - Problem 5
Robot "Mag-o-matic" manipulates 101 glasses, displaced in a row whose positions are numbered from 1 to 101. In each glass you can find a ball or not. Mag-o-matic only accepts elementary instructions of the form (a;b,c), which it interprets as
"consider the glass in position a: if it contains a ball, then switch the glasses in positions b and c (together with their own content), otherwise move on to the following instruction"
(it means that a,b,c are integers between 1 and 101, with b and c different from each other but not necessarily different from a). A \emph{programme} is a finite sequence of elementary instructions, assigned at the beginning, that Mag-o-matic does one by one.
A subset S⊆{0,1,2,…,101} is said to be \emph{identifiable} if there exists a programme which, starting from any initial configuration, produces a final configuration in which the glass in position 1 contains a ball if and only if the number of glasses containing a ball is an element of S.
(a) Prove that the subset S of the odd numbers is identifiable.
(b) Determine all subsets S that are identifiable. Italian Mathematical Olympiad 2022 - Problem 4
Alberto chooses 2022 integers a1,a2,…,a2022 (not necessarily positive and not necessarily distinct) and places them on a 2022×2022 table such that in the (i,j) cell is the number ak, with k=max{i,j}, as shown in figure (in which, for a better readability, we have denoted a2022 with an).
Barbara does not know the numbers Alberto has chosen, but knows how they are displaced in the table. Given a positive integer k, with 1≤k≤2022, Barbara wants to determine the value of ak (and she is not interested in determining the values of the other ai's with i=k). To do so, Barbara is allowed to ask Alberto one or more questions, in each of which she demands the value of the sum of the numbers contained in the cells of a "path", where with the term "path" we indicate a sorted list of cells with the following characteristics:
• the path starts from the top left cell and finishes with the bottom right cell,
• the cells of the path are all distinct,
• two consecutive cells of the path share a common side.
Determine, as k varies, the minimum number of questions Barbara needs to find ak.