Olimpíada Brasileira de Matemática 2022 — Nível 3 — Fase x

Stone-pile game: prove final pile count is invariant

A game for one person has the following rules: initially there are ten piles of stones, with $1,2,3,\dots ,10$ stones respectively. A move consists of performing one of the following two operations:

(i) Choose two piles, each with at least two stones, merge them and then add two more stones to the new pile.

(ii) Choose a pile with at least 4 stones, take two stones from it and split it into two piles, with the numbers of stones in the two new piles chosen by the player.

The game ends when no move can be made. Show that the number of piles with exactly one stone at the end of the game is always the same, regardless of how the moves are made.

Topic: Combinatoria Metodo: Invarianti Abilita: Astrazione, Ragionamento geometrico, Lettura attenta Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Gioco di pile di pietra: dimostra che il numero finale di pile è invariante

Un gioco per una persona ha le seguenti regole: inizialmente ci sono dieci pile di pietre, rispettivamente $1,2,3,\dots ,10$ pietre. Una mossa consiste nell’esecuzione di una delle due operazioni seguenti:

(i) Scegliere due pile, ciascuna con almeno due pietre, fonderele e poi aggiungere altre due pietre alla nuova pila.

(ii) Scegliere una pila con almeno 4 pietre, prenderne due e dividerla in due pile, con il numero di pietre nelle due nuove pile scelte dal giocatore.

La partita finisce quando non si può fare nessuna mossa. Mostrare che il numero di pile con esattamente una pietra alla fine del gioco è sempre lo stesso, indipendentemente dal modo in cui le mosse sono fatte.

src_obm_2022_n3_fx__Q01

Reflection of circumcenter midpoint lies on circumcircle ABC

Let $ABC$ be an acute triangle with $AB<AC$. Let $K$ be the midpoint of arc $BC$ of the circumscribed circle of $ABC$ that does not contain $A$, and let $P$ be the midpoint of side $BC$. The points $I_B$ and $I_C$ are the excenters relative to vertices $B$ and $C$, respectively. Let $Q$ be the reflection of $K$ across point $A$. Show that $P$, $Q$, $I_B$, and $I_C$ lie on the same circle.

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

Il riflesso del centro del circolo si trova sul circolo ABC

$ABC$ sia un triangolo acuto con $AB<AC$. Il punto $K$ deve essere il punto medio dell’arco $BC$ del cerchio circoscritto di $ABC$ che non contiene $A$ e il punto medio del lato $BC$ deve essere $P$. I punti $I_B$ e $I_C$ sono gli eccentri relativi ai vertici $B$ e $C$, rispettivamente. Il $Q$ deve essere il riflesso di $K$ attraverso il punto $A$. Indicare che $P$, $Q$, $I_B$ e $I_C$ si trovano sullo stesso cerchio.

src_obm_2022_n3_fx__Q02

Self-referential sequence: find smallest M making it M-self-referential in 2022

Let $(a_n{)}_{n\ge 0}$ be a sequence of integers. Define ${\Delta }^1{a}_n=a_{n+1}-a_n$ for every non-negative integer $n$. For $N\ge 2$, define ${\Delta }^N{a}_n={\Delta }^{N-1}{a}_{n+1}-{\Delta }^{N-1}{a}_n$, and so on; that is, ${\Delta }^N{a}_n={\Delta }^{N-1}({\Delta }^1{a}_n)={\Delta }^{M-1}{a}_{n+1}-{\Delta }^{M-1}{a}_n$ for every non-negative integer $n$.

A sequence is called $M$-self-referential if there exist positive integers $k$ and $\ell$ such that $a_{n+k}={\Delta }^M{a}_n$ for every non-negative integer $n$. Determine, with proof, whether there exists some sequence such that the smallest value of $M$ for which the sequence is $M$-self-referential is $2022$.

Topic: Algebra, Combinatoria Metodo: Ricorsione, Induzione Abilita: Manipolazione algebrica, Astrazione, Riconoscimento di pattern Area: Algebra e Analisi, Combinatoria, Logica e Probabilita Fonte: apri PDF

Sequenza autoreferenziale: trovare il più piccolo M che lo rende autoreferenziale nel 2022

Lasciate che $(a_n{)}_{n\ge 0}$ sia una sequenza di numeri interi. Definire ${\Delta }^1{a}_n=a_{n+1}-a_n$ per ogni numero intero non negativo $n$. Per $N\ge 2$, definire ${\Delta }^N{a}_n={\Delta }^{N-1}{a}_{n+1}-{\Delta }^{N-1}{a}_n$ e così via; cioè ${\Delta }^N{a}_n={\Delta }^{N-1}({\Delta }^1{a}_n)={\Delta }^{M-1}{a}_{n+1}-{\Delta }^{M-1}{a}_n$ per ogni numero intero non negativo $n$.

Una sequenza è chiamata $M$-auto-referenziale se esistono interi positivi $k$ e $\ell$ in modo tale che $a_{n+k}={\Delta }^M{a}_n$ per ogni intero non negativo $n$. Determinare, con la prova, se esiste una sequenza tale che il valore più piccolo di $M$ per la quale la sequenza è $M$-auto-referenziale è $2022$.

src_obm_2022_n3_fx__Q03

Esmeralda erases and writes on board; find largest composite she cannot write

Initially a number is written on the board. Then, each minute, Esmeralda chooses a divisor $d>1$ of the number $n$ written on the board, erases $n$, and writes $n+d$. If the initial number is $2022$, what is the largest composite number that Esmeralda can never write on the board?

Topic: Teoria dei Numeri Metodo: Invarianti, Casework Abilita: Riconoscimento di pattern, Lettura attenta, Conteggio sistematico Area: Aritmetica e Teoria dei Numeri Fonte: apri PDF

Esmeralda cancella e scrive a bordo; trova il composto più grande non riesce a scrivere

Inizialmente sulla lavagna viene scritto un numero. Quindi, ogni minuto, Esmeralda sceglie un divisore $d>1$ del numero $n$ scritto sulla lavagna, cancella $n$ e scrive $n+d$. Se il numero iniziale è $2022$, qual è il numero composto più grande che Esmeralda non può mai scrivere sulla lavagna?

src_obm_2022_n3_fx__Q04

Same-parity sum function: prove growth bound with constant c

Let $n$ be a positive integer. Define $S(n)$ as the smallest positive integer such that $S(n)$ and $n$ have the same parity and there do not exist positive integers $k,x_1,x_2,\dots ,x_k$ such that $x_1+x_2+\cdots +x_k=n$ and $x_1^2+x_2^2+\cdots +x_k^2=S(n)$. Prove that there exist a real constant $c>0$ and a positive integer $n_0$ such that $S(n)\ge c{n}^{3/2}$ for every $n\ge n_0$.

Topic: Combinatoria, Teoria dei Numeri Metodo: Estremalità, Disuguaglianze Abilita: Manipolazione algebrica, Stima, Astrazione Area: Combinatoria, Logica e Probabilita, Aritmetica e Teoria dei Numeri Fonte: apri PDF

*Funzione somma paritaria: dimostrare la crescita legata con costante c *

$n$ sia un numero intero positivo. Definire $S(n)$ come il numero intero positivo più piccolo in modo che $S(n)$ e $n$ abbiano la stessa parità e non esistano **** interi positivi $k,x_1,x_2,\dots ,x_k$ in modo che $x_1+x_2+\cdots +x_k=n$ e $x_1^2+x_2^2+\cdots +x_k^2=S(n)$. Prova che esiste una costante reale $c>0$ e un intero positivo $n_0$ tale che $S(n)\ge c{n}^{3/2}$ per ogni $n\ge n_0$.

src_obm_2022_n3_fx__Q05

10x10 red-painted table: maximum n cells in no special 6-cell set

Some cells of a $10\times 10$ table are painted red. A set of six cells is called special if the six cells are the intersection of three rows and two columns, or two rows and three columns, and all six are painted red. Find the largest value of $n$ for which it is possible to paint $n$ cells of the red table so that no special set appears.

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

10x10 tabella dipinta in rosso: massimo n cellule in nessun gruppo speciale di 6 cellule

Alcune celle di una tabella $10\times 10$ sono dipinte in rosso. Un insieme di sei celle è chiamato special se le sei celle sono l’intersezione di tre righe e due colonne, o due righe e tre colonne, e tutte e sei sono dipinte di rosso. Trova il valore più grande di $n$ per il quale è possibile dipingere le celle $n$ della tabella rossa in modo che non venga visualizzato alcun insieme speciale.

src_obm_2022_n3_fx__Q06