Olimpíada Brasileira de Matemática 2024 — Nível 2 — Fase x

Sequence formed by repeated prime-factorization operation; three sub-parts

Consider a sequence whose first term is a given positive integer $N>1$. Given a term $N$ of the sequence, if $N$ is a power of a single prime, the sequence ends at $N$. Otherwise, the next term is obtained by taking the largest prime factor $p$ of $N$ and replacing $p$ with $p+1$ in the prime factorization; if the resulting number is not a power of a prime, the process is repeated on the new number, giving rise to the next term; and so on. For example, if the first term of the sequence is $N=300=2^2\cdot 3\cdot 5^2$, since its largest prime factor is $p=5$, the second term is $2^2\cdot 3\cdot (5+1{)}^2=2^4\cdot 3^3$. Since $p=3$ and thus the third term is $2^4\cdot (3+1{)}^3=2^{10}$. We have obtained a power of $2$, so the sequence terminates. For example, the sequence $2^2\cdot 3\cdot 5^2,2^4\cdot 3^3,2^{10}$ has $3$ terms.

(a) How many terms does the sequence whose first term is $N=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23$ have?

(b) Show that if a prime $p$ leaves remainder $1$ on division by $3$, then $\frac{p+1}{2}$ is also an integer that leaves remainder $1$ on division by $3$.

(c) Find an initial value $N$ less than $1,000,000$ (one million) such that the sequence starting at $N$ has exactly $11$ terms.

Topic: Teoria dei Numeri, Algebra Metodo: Fattorizzazione, Induzione, Casework Abilita: Manipolazione algebrica, Riconoscimento di pattern, Lettura attenta Area: Aritmetica e Teoria dei Numeri, Algebra e Analisi Fonte: apri PDF

Sequenza costituita da ripetute operazioni di fattorizzazione dei primi; tre sottoparti

Considera una sequenza il cui primo termine è un dato intero positivo $N>1$. Dato un termine $N$ della sequenza, se $N$ è una potenza di un singolo primo, la sequenza termina a $N$. In caso contrario, il termine successivo viene ottenuto prendendo il più grande fattore primo $p$ di $N$ e sostituendo $p$ con $p+1$ nella fattorizzazione primaria; se il numero risultante non è una potenza di un primo, il processo viene ripetuto sul nuovo numero, dando origine al termine successivo; e così via. Ad esempio, se il primo termine della sequenza è $N=300=2^2\cdot 3\cdot 5^2$, poiché il suo fattore primo più grande è $p=5$, il secondo termine è $2^2\cdot 3\cdot (5+1{)}^2=2^4\cdot 3^3$. Dal momento che $p=3$ e quindi il terzo termine è $2^4\cdot (3+1{)}^3=2^{10}$. Abbiamo ottenuto una potenza di $2$, quindi la sequenza termina. Ad esempio, la sequenza $2^2\cdot 3\cdot 5^2,2^4\cdot 3^3,2^{10}$ ha termini $3$.

(a) Quanti termini ha la sequenza il cui primo termine è $N=2\cdot 3\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23$?

b) Mostra che se un primo $p$ lascia il rimanente $1$ sulla divisione di $3$, allora $\frac{p+1}{2}$ è anche un intero che lascia il rimanente $1$ sulla divisione di $3$.

(c) Trovare un valore iniziale $N$ inferiore a $1,000,000$ (un milione) tale che la sequenza a partire da $N$ abbia esattamente $11$ termini.

src_obm_2024_n2_fx__Q01

Cyclic concyclicity result in triangle with circumscribed circles and midpoints

Let $ABC$ be a triangle and let $E$ and $F$ be the midpoints of sides $AC$ and $AB$, respectively. Let $D$ be any point on segment $BC$. The circumscribed circles of triangles $BDF$ and $CDE$ intersect each other at a point $X\ne D$. The point $Y$ lies on line $DX$ such that $AY$ is parallel to $BC$. Prove that the points $K$, $L$, $X$, and $Y$ all lie on the same circle, where $K$ and $L$ are the second intersection points (other than $X$) of the circumcircles of $BDF$ and $CDE$ with the line $EF$.

Topic: Geometria piana Metodo: Coordinate, Trigonometria Abilita: Ragionamento geometrico, Manipolazione algebrica Area: Geometria Fonte: apri PDF

La conciclicità ciclica si traduce in un triangolo con cerchi e punti di mezzo circoscritti

Il $ABC$ sia un triangolo e il $E$ e il $F$ siano rispettivamente i punti medi dei lati $AC$ e $AB$. Il segmento $BC$ deve essere $D$. I cerchi circoscritti dei triangoli $BDF$ e $CDE$ si incrociano a un punto $X\ne D$. Il punto $Y$ si trova sulla linea $DX$ in modo tale che $AY$ sia parallelo a $BC$. Prova che i punti $K$, $L$, $X$ e $Y$ si trovano tutti sullo stesso cerchio, dove $K$ e $L$ sono i secondi punti di intersezione (diversi da $X$) dei circoncircoli di $BDF$ e $CDE$ con la linea $EF$.

src_obm_2024_n2_fx__Q02

Longest guaranteed increasing path in 10×10 grid with 1–100

The numbers $1$ to $100$ are placed without repetition, one in each cell of a $10\times 10$ grid. An increasing path of length $k$ in this grid is a sequence of cells $c_1,c_2,\dots ,c_k$ such that, for each $i=2,3,\dots ,k$, the following properties hold:

• cells $c_i$ and $c_{i-1}$ share a side or a vertex;
• the number in $c_i$ is greater than the number in $c_{i-1}$.

What is the largest positive integer $k$ such that we can always find an increasing path of length $k$, regardless of how the numbers $1$ to $100$ are arranged in the grid?

Topic: Combinatoria Metodo: Estremalità, Casework, Invarianti Abilita: Conteggio sistematico, Ragionamento geometrico, Stima Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

*Il percorso di crescita più lungo garantito nella griglia 10 ×10 con 1100 *

I numeri $1$ a $100$ vengono inseriti senza ripetizione, uno in ogni cella di una griglia $10\times 10$. Un percorso aumentante di lunghezza $k$ in questa griglia è una sequenza di celle $c_1,c_2,\dots ,c_k$ tale che, per ciascuna $i=2,3,\dots ,k$, possano le seguenti proprietà:

• le celle $c_i$ e $c_{i-1}$ condividono un lato o un vertice; - il numero di $c_i$ è maggiore del numero di $c_{i-1}$.

Qual è il più grande intero positivo $k$ in modo che possiamo sempre trovare un percorso crescente di lunghezza $k$, indipendentemente dal modo in cui i numeri $1$ a $100$ sono disposti nella griglia?

src_obm_2024_n2_fx__Q03

Count 10-digit numbers with digits in {1,2,3} divisible by 99

A number is called trilegal if all its digits belong to the set $\{1,2,3\}$ and it is divisible by $99$. How many trilegal numbers have exactly $10$ digits?

Topic: Teoria dei Numeri, Combinatoria Metodo: Congruenze, Conteggio, Casework Abilita: Conteggio sistematico, Manipolazione algebrica, Riconoscimento di pattern Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

Contare i numeri a 10 cifre con cifre di {1,2,3} divisibili per 99

Un numero è chiamato trilegal se tutti i suoi numeri appartengono all’insieme $\{1,2,3\}$ ed è divisibile da $99$. Quanti numeri trilegali hanno esattamente $10$ cifre?

src_obm_2024_n2_fx__Q04

Esmeralda’s iterated quadratic equations with distinct positive integer roots

Esmeralda chooses two distinct positive integers $a$ and $b$, with $a>b$, and writes the equation $x^2-ax+b=0$ on the board. If the equation has distinct positive integer roots $c$ and $d$, with $c>d$, she then writes the equation $x^2-cx+d=0$ on the board. She repeats this procedure as long as she keeps obtaining distinct positive integer roots. If she writes an equation for which this does not happen, she stops.

(a) Show that Esmeralda can choose $a$ and $b$ such that she writes exactly $2024$ equations on the board.

(b) What is the greatest number of equations she can write knowing that one of the numbers she initially chose is $2024$?

Topic: Algebra, Teoria dei Numeri Metodo: Fattorizzazione, Ricorsione, Backward Abilita: Manipolazione algebrica, Riconoscimento di pattern, Ragionamento geometrico Area: Algebra e Analisi, Aritmetica e Teoria dei Numeri Fonte: apri PDF

Equazioni quadratiche iterate di Esmeralda con radici di numeri interi positivi distinti

Esmeralda sceglie due numeri interi positivi distinti $a$ e $b$, con $a>b$, e scrive l’equazione $x^2-ax+b=0$ sulla lavagna. Se l’equazione ha radici di numeri interi positivi distinte $c$ e $d$, con $c>d$, scrive poi l’equazione $x^2-cx+d=0$ sulla lavagna. Essa ripete questa procedura finché continua a ottenere radici di numeri interi positivi distinte. Se scrive un’equazione per la quale questo non accade, si ferma.

(a) Mostrare che Esmeralda può scegliere $a$ e $b$ in modo tale da scrivere esattamente $2024$ equazioni sulla lavagna.

b) Qual è il maggior numero di equazioni che può scrivere sapendo che uno dei numeri che ha inizialmente scelto è $2024$?

src_obm_2024_n2_fx__Q05

Perpendicularity result in isosceles triangle with special cevian configuration

Let $ABC$ be an isosceles triangle with $AB=BC$. Let $D$ be a point on segment $AB$, $E$ a point on segment $BC$, and $P$ a point on segment $DE$ such that $AD=DP$ and $CE=PE$. Let $M$ be the midpoint of $DE$. The line parallel to $AB$ through $M$ intersects $AC$ at $X$, and the line parallel to $BC$ through $M$ intersects $AC$ at $Y$. The lines $DX$ and $EY$ intersect at $F$. Prove that $FP$ is perpendicular to $DE$.

Topic: Geometria piana Metodo: Coordinate, Simmetria Abilita: Ragionamento geometrico, Manipolazione algebrica, Modellizzazione Area: Geometria Fonte: apri PDF

Perpendicolarità che si traduce in triangolo di isosceles con configurazione ceviana speciale

Che $ABC$ sia un triangolo di uguali dimensioni con $AB=BC$. Il $D$ deve essere un punto del segmento $AB$, $E$ un punto del segmento $BC$ e $P$ un punto del segmento $DE$ in modo tale che $AD=DP$ e $CE=PE$. $M$ deve essere il punto medio di $DE$. La linea parallela a $AB$ attraverso $M$ si interseca a $AC$ a $X$, e la linea parallela a $BC$ attraverso $M$ si interseca a $Y$. Le linee $DX$ e $EY$ si incrociano a $F$. Prove che $FP$ è perpendicolare a $DE$.

src_obm_2024_n2_fx__Q06