MathDB

1

Part of 2022 OMpD

Problems(2)

Squares with same distance from rooks

Source: 2022 3rd OMpD L2 P1 - Brazil - Olimpíada Matemáticos por Diversão

7/8/2023
Consider a chessboard 6×66 \times 6, made up of 3636 single squares. We want to place 66 chess rooks on this board, one rook on each square, so that there are no two rooks on the same row, nor two rooks on the same column. Note that, once the rooks have been placed in this way, we have that, for every square where a rook has not been placed, there is a rook in the same row as it and a rook in the same column as it. We will say that such rooks are in line with this square.
For each of those 3030 houses without rooks, color it green if the two rooks aligned with that same house are the same distance from it, and color it yellow otherwise. For example, when we place the 66 rooks (TT) as below, we have:
(a) Is it possible to place the rooks so that there are 3030 green squares? (b) Is it possible to place the rooks so that there are 3030 yellow squares? (c) Is it possible to place the rooks so that there are 1515 green and 1515 yellow squares?
combinatoricsChess rookChessboard
Phi function and its conjugate

Source: 2022 3rd OMpD L3 P1 - Brazil - Olimpíada Matemáticos por Diversão

7/8/2023
Given a positive integer n≥2n \geq 2, whose canonical prime factorization is n=p1α1p2α2…pkαkn = p_1^{\alpha_1}p_2^{\alpha_2} \ldots p_k^{\alpha_k}, we define the following functions: φ(n)=n(1−1p1)(1−1p2)…(1−1pk);φ‾(n)=n(1+1p1)(1+1p2)…(1+1pk)\varphi(n) = n\bigg(1 -\frac{1}{p_1}\bigg) \bigg(1 -\frac{1}{p_2}\bigg) \ldots \bigg(1 -\frac {1}{p_k}\bigg) ; \overline{\varphi}(n) = n\bigg(1 +\frac{1}{p_1}\bigg) \bigg(1 +\frac{1}{p_2}\bigg) \ldots \bigg(1 + \frac{1}{p_k}\bigg) Consider all positive integers nn such that φ‾(n)\overline{\varphi}(n) is a multiple of n+φ(n)n + \varphi(n) . (a) Prove that nn is even. (b) Determine all positive integers nn that satisfy this property.
phi functionprime factorizationnumber theoryfunction