Indian National Mathematical Olympiad 2023

Finite set with 2023 square-product pairs; find 4 elements with no square pairwise product

Let $S$ be a finite set of positive integers. Assume that there are precisely 2023 ordered pairs $(x,y)$ in $S\times S$ so that the product $xy$ is a perfect square. Prove that one can find at least four distinct elements in $S$ so that none of their pairwise products is a perfect square.

Note: As an example, if $S=\{1,2,4\}$, there are exactly five such ordered pairs: $(1,1)$, $(1,4)$, $(2,2)$, $(4,1)$, and $(4,4)$.

Topic: Teoria dei Numeri, Combinatoria Metodo: Grafi, Casework, Estremalità Abilita: Manipolazione algebrica, Astrazione, Riconoscimento di pattern Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

Set finito con 2023 coppie di prodotti quadrati; trovare 4 elementi senza prodotto in coppie quadrate

Che $S$ sia un insieme finito di interi positivi. Supponiamo che ci siano precisamente 2023 coppie ordinate $(x,y)$ in $S\times S$ in modo che il prodotto $xy$ sia un quadrato perfetto. Prova che si possono trovare almeno quattro elementi distinti in $S$ in modo che nessuno dei loro prodotti in coppia sia un quadrato perfetto.

Nota: Ad esempio, se $S=\{1,2,4\}$, ci sono esattamente cinque coppie ordinate: $(1,1)$, $(1,4)$, $(2,2)$, $(4,1)$ e $(4,4)$.

src_inmo_2023__Q01

101 cyclic polynomials in positive reals; show not all can have all real roots

Suppose $a_0,a_1,\dots ,a_{100}$ are positive reals. Consider the following polynomial for each $k$ in $\{0,1,\dots ,100\}$: $a_{101+k}{x}^{100}+100a_{k+1}{x}^{99}+a_{k+2}{x}^{98}+\cdots +a_{k+99}x+a_k,$ where indices are taken modulo 101, i.e., $a_{101m}=a_0$ for any $i$ in $\{1,2,\dots ,100\}$.

Show that it is impossible that each of these 101 polynomials has all its roots real.

Topic: Algebra Metodo: Disuguaglianze, Simmetria Abilita: Manipolazione algebrica, Astrazione, Stima Area: Algebra e Analisi Fonte: apri PDF

101 polinomi ciclici nei reali positivi; mostrare che non tutti possono avere tutte le radici reali

Supponiamo che $a_0,a_1,\dots ,a_{100}$ siano numeri reali positivi. Si consideri il seguente polinomio per ogni $k$ in $\{0,1,\dots ,100\}$: $a_{101+k}{x}^{100}+100a_{k+1}{x}^{99}+a_{k+2}{x}^{98}+\cdots +a_{k+99}x+a_k,$ in cui gli indici sono presi modulo 101, cioè $a_{101m}=a_0$ per qualsiasi $i$ in $\{1,2,\dots ,100\}$.

Mostrare che è impossibile che ciascuno di questi 101 polinomi abbia tutte le sue radici reali.

src_inmo_2023__Q02

Find all c >= 1 for which a function f: N -> N satisfies two conditions

Let $\mathbb{N}$ denote the set of all positive integers. Find all real numbers $c\ge 1$ for which there exists a function $f:\mathbb{N}\to \mathbb{N}$ satisfying: (a) for any $x,n\in \mathbb{N}$, the quantity $\frac{f(x+n)-f(x)}{n^c}$ is an integer if and only if $n=1$; (b) for all $x\in \mathbb{N}$, $|f(x+1)-f(x)|<2023$.

Topic: Insiemi e funzioni, Teoria dei Numeri Metodo: Casework, Congruenze, Induzione Abilita: Manipolazione algebrica, Astrazione, Lettura attenta Area: Algebra e Analisi, Aritmetica e Teoria dei Numeri Fonte: apri PDF

Ricerca tutte le c >= 1 per le quali una funzione f: N -> N soddisfa due condizioni

$\mathbb{N}$ indichi l’insieme di tutti gli integri positivi. Trova tutti i numeri reali $c\ge 1$ per i quali esiste una funzione $f:\mathbb{N}\to \mathbb{N}$ che soddisfa: (a) per qualsiasi $x,n\in \mathbb{N}$, la quantità $\frac{f(x+n)-f(x)}{n^c}$ è un numero intero se e solo se $n=1$; (b) per tutti $x\in \mathbb{N}$, $|f(x+1)-f(x)|<2023$.

src_inmo_2023__Q03

Calvin and Hobbes coin game on a circle; find all k for which Calvin wins

Let $k\ge 1$ and $N>1$ be two integers. On a circle are placed $2N+1$ coins all showing heads. Calvin and Hobbes play the following game. Calvin starts and on his move can turn any coin from heads to tails. Hobbes on his move can turn at most one coin that is next to the coin that Calvin turned just now from tails to heads. Calvin wins if at any moment there are $k$ coins showing tails after Hobbes has made his move. Determine all values of $k$ for which Calvin wins the game.

Topic: Combinatoria Metodo: Invarianti, Casework, Estremalità Abilita: Astrazione, Modellizzazione, Riconoscimento di pattern, Ragionamento geometrico Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Calvin e Hobbes gioco di monete su un cerchio; trovare tutti i k per cui Calvin vince

$k\ge 1$ e $N>1$ siano due numeri interi. Su un cerchio sono posizionate monete $2N+1$ tutte con teste. Calvin e Hobbes giocano il seguente gioco. Calvin inizia e in movimento può trasformare qualsiasi moneta da testa a coda. Hobbes in movimento può trasformare al massimo una moneta che si trova accanto alla moneta che Calvin ha appena trasformato dalle code alle teste. Calvin vince se in qualsiasi momento ci sono monete che mostrano code dopo che Hobbes ha fatto la sua mossa. Determinare tutti i valori di $k$ per i quali Calvin vince la partita.

src_inmo_2023__Q04

n Euclidean points; Gauss records floor(log2 d) for each pair; show fewer than 2n distinct values

Euler marks $n$ different points in the Euclidean plane. For each pair of marked points, Gauss writes down the number $\lfloor {\log }_{2}d\rfloor$ where $d$ is the distance between the two points. Prove that Gauss writes down less than $2n$ distinct values.

Note: For any $d>0$, $\lfloor {\log }_{2}d\rfloor$ is the unique integer $k$ such that $2^k\le d<2^{k+1}$.

Topic: Combinatoria, Geometria piana Metodo: Estremalità, Principio dei cassetti, Doppio conteggio Abilita: Ragionamento geometrico, Stima, Astrazione Area: Combinatoria, Logica e Probabilita, Geometria Fonte: apri PDF

n punti euclidici; Gauss registra il livello di < log2 d) per ciascuna coppia; mostrano meno di 2n valori distinti

Euler segna $n$ punti diversi nel piano euclidico. Per ogni coppia di punti segnalati, Gauss scrive il numero $\lfloor {\log }_{2}d\rfloor$ dove $d$ è la distanza tra i due punti. Prove che Gauss scrive meno di $2n$ valori distinti.

*Nota: * Per qualsiasi $d>0$, $\lfloor {\log }_{2}d\rfloor$ è l’intero unico $k$ tale che $2^k\le d<2^{k+1}$.

src_inmo_2023__Q05

Using a cyclos tool, construct a circle centered at one of two given points passing through the other

Euclid has a tool called cyclos which does the following:

• Given three non-collinear marked points, draw the circle passing through them.
• Given two marked points, draw the circle with them as endpoints of a diameter.
• Mark any intersection points of two drawn circles or mark a new point on a drawn circle.

Show that given two marked points, Euclid can draw a circle centered at one of them and passing through the other, using only the cyclos.

Topic: Geometria piana Metodo: Backward, Coordinate Abilita: Ragionamento geometrico, Modellizzazione, Lettura attenta, Astrazione Area: Geometria Fonte: apri PDF

Utilizzando uno strumento di ciclo, costruire un cerchio centrato su uno dei due punti dati che attraversano l’altro

Euclide ha uno strumento chiamato cyclos che fa quanto segue: - Dati tre punti non collineari, disegnare il cerchio che li attraversa. - Dati due punti segnati, disegnare il cerchio con loro come punti finali di diametro. - Marcare eventuali punti di intersezione di due cerchi disegnati o marcare un nuovo punto su un cerchio disegnato.

Mostra che dato due punti segnati, Euclide può disegnare un cerchio centrato su uno di essi e passando attraverso l’altro, utilizzando solo i cicli.

src_inmo_2023__Q06