MathDB

4

Part of 2022 Middle European Mathematical Olympiad

Problems(2)

gcd+lcm operation on a blackboard

Source: MEMO 2022 I4

9/2/2022
Initially, two distinct positive integers aa and bb are written on a blackboard. At each step, Andrea picks two distinct numbers xx and yy on the blackboard and writes the number gcd(x,y)+lcm(x,y)gcd(x, y) + lcm(x, y) on the blackboard as well. Let nn be a positive integer. Prove that, regardless of the values of aa and bb, Andrea can perform a finite number of steps such that a multiple of nn appears on the blackboard.
number theory
Weird sequence of moves in a grid

Source: MEMO 2022 T4

9/2/2022
Let nn be a positive integer. We are given a 2n×2n2n \times 2n table. Each cell is coloured with one of 2n22n^2 colours such that each colour is used exactly twice. Jana stands in one of the cells. There is a chocolate bar lying in one of the other cells. Jana wishes to reach the cell with the chocolate bar. At each step, she can only move in one of the following two ways. Either she walks to an adjacent cell or she teleports to the other cell with the same colour as her current cell. (Jana can move to an adjacent cell of the same colour by either walking or teleporting.) Determine whether Jana can fulfill her wish, regardless of the initial configuration, if she has to alternate between the two ways of moving and has to start with a teleportation.
combinatorics