MathDB

4

Part of 2024 OMpD

Problems(3)

"Given A and B, how many roads are part of the route connecting A to B?"

Source: 2024 5th OMpD L3 P4 - Brazil - Olimpíada Matemáticos por Diversão

10/16/2024
Lavidópolis is a city with 2024 neighborhoods. Lavi Dopes was elected mayor, and since he saw that there were no roads in the city, he asked Gil Bento, the monster engineer, to design the city's roads according to the following rules: 1. Any two neighborhoods are connected by at most one two-way road; 2. For any two neighborhoods, there is exactly one route from one neighborhood to another, which may pass through some intermediate neighborhoods, but never passes through the same neighborhood more than once.
Mayor Lavi Dopes wants to try for re-election, but since he knows nothing about the city and only shows up during campaign times (he spent all this time stealing... I mean, thinking about math problems), he wants to find a pair of neighborhoods such that the number of roads that are part of the route connecting them is maximized among all pairs of neighborhoods. To do this, he starts asking Gil Bento various questions, all in the following manner: he chooses two of the 2024 neighborhoods, say A and B, and asks: "Given neighborhoods A and B, how many roads are part of the route connecting A to B?"
Knowing that Gil Bento always answers correctly to each question, determine the minimum number of questions that Lavi Dopes needs to ask to achieve his goal, regardless of how Gil Bento has designed the roads of Lavidópolis.
combinatoricsgraph
a_n+a_{n-1} is a perfect square for all n

Source: 2024 5th OMpD L2 P4 - Brazil - Olimpíada Matemáticos por Diversão

10/16/2024
Let a0,a1,a2,…a_0, a_1, a_2, \dots be an infinite sequence of positive integers with the following properties: - a0a_0 is a given positive integer; - For each integer n≥1n \geq 1, ana_n is the smallest integer greater than an−1a_{n-1} such that an+an−1a_n + a_{n-1} is a perfect square. For example, if a0=3a_0 = 3, then a1=6a_1 = 6, a2=10a_2 = 10, a3=15a_3 = 15, and so on.
(a) Let TT be the set of numbers of the form ak−ala_k - a_l, with k≥l≥0k \geq l \geq 0 integers. Prove that, regardless of the value of a0a_0, the number of positive integers not in TT is finite.
(b) Calculate, as a function of a0a_0, the number of positive integers that are not in TT.
algebraSequencePerfect Squares
euclidean norm in functions

Source: 2024 5th OMpD LU P4 - Brazil - Olimpíada Matemáticos por Diversão

10/16/2024
Let n n be a positive integer. Determine the largest possible value of k k with the following property: there exists a bijective function ϕ:[0,1]→[0,1]k \phi: [0, 1] \to [0, 1]^k and a constant C>0 C > 0 such that, for all x,y∈[0,1] x, y \in [0, 1] ,
∥ϕ(x)−ϕ(y)∥≤C∥x−y∥k. \| \phi(x) - \phi(y) \| \leq C \| x - y \|^k.
Note: ∥⋅∥ \| \cdot \| denotes the Euclidean norm, that is, ∥(a1,…,an)∥=a12+⋯+an2 \| (a_1, \ldots, a_n) \| = \sqrt{a_1^2 + \cdots + a_n^2} .
functionreal analysis