MathDB

3

Part of 2023 Rioplatense Mathematical Olympiad

Problems(2)

Graphs are back!

Source: Rioplatense L3 2023 #3

12/6/2023
The water city of Platense consists of many platforms and bridges between them. Each bridge connects two platforms and there is not two bridges connecting the same two platforms. The mayor wants to switch some bridges by a series of moves in the following way: if there are three platforms A,B,CA,B,C and bridges ABAB and ACAC (no bridge BCBC), he can switch bridge ABAB to a bridge BCBC. A configuration of bridges is good if it is possible to go to any platfom from any platform using only bridges. Starting in a good configuration, prove that the mayor can reach any other good configuration, whose the quantity of bridges is the same, using the allowed moves.
combinatorics
Batman can not meet Joker

Source: Rioplatense L2 2023 #3

12/5/2023
Let n>d>0n>d>0 integers. Batman, Joker, Clark play the following game in an infinite checkered board. Initially, Batman and Joker are in cells with distance nn and a candy is in a cell with distance dd to Batman. Batman is blindfold, and can only see his cell. Clark and Joker can see the whole board. The following two moves go alternately. 1 - Batman goes to an adjacent cell. If he touches Joker, Batman loses. If he touches the candy, Batman wins. If the cell is empty, Clark chooses to say loudly one of the following two words hot or cold. 2 - Joker goes to an adjacent cell. If he touches Batman or candy, Joker wins. Otherwise, the game continues. Determine for each dd, the least nn, such that Batman, and Clark can plan an strategy to ensure the Batman's win, regardless of initial positions of the Joker and of the candy. Note: Two cells are adjacent if its have a common side. The distance between two cells XX and YY is the least pp such that there exist cells X=X0,X1,X2,…,Xp=YX=X_0,X_1,X_2,\dots, X_p=Y with XiX_i adjacent to Xi−1X_{i-1} for all i=1,2,…,pi=1,2,\dots,p.
combinatorics