Olimpíada Brasileira de Matemática 2006 — Nível 2 — Fase 3

Min steps to rewrite sequence 1..n in order

We write, in a row, the numbers $1,2,3,\dots ,n$. At each step, we take the last two numbers of the current row, write the last one first and the second-to-last one last, and then place the remaining $n-2$ numbers in between. For example, for $n=12$ we obtain: $1,2,3,4,5,6,7,8,9,10,11,12\to 12,11,1,2,3,4,5,6,7,8,9,10$ $\to 10,9,12,11,1,2,3,4,5,6,7,8\to \cdots$

What is the minimum number of steps needed to write $1,2,3,\dots ,n$ in order again, when

(a) $n=2006$?

(b) $n=2005$?

Topic: Teoria dei Numeri, Combinatoria Metodo: Invarianti, Ricorsione, Casework Abilita: Riconoscimento di pattern, Conteggio sistematico, Ragionamento geometrico Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

Min passi per riscrivere la sequenza 1..n nell’ordine

Scriviamo, in fila, i numeri $1,2,3,\dots ,n$. Ad ogni passo, prendiamo gli ultimi due numeri della riga corrente, scriviamo l’ultimo prima e l’ultimo dopo l’ultimo, e poi mettiamo i restanti numeri $n-2$ in mezzo. Per esempio, per $n=12$ otteniamo: $1,2,3,4,5,6,7,8,9,10,11,12\to 12,11,1,2,3,4,5,6,7,8,9,10$ $\to 10,9,12,11,1,2,3,4,5,6,7,8\to \cdots$

Qual è il numero minimo di passi necessari per scrivere $1,2,3,\dots ,n$ in ordine di nuovo, quando

(a) $n=2006$?

(b) $n=2005$?

src_obm_2006_n2_f3__Q01

Max collinear vertices in a 12-sided polygon

Among all polygons with 5 sides, the maximum number of collinear vertices (i.e., belonging to a single line) is three, as shown below.

What is the maximum number of collinear vertices that a polygon with 12 sides can have?

Attention: after drawing a 12-gon with the maximum number of collinear vertices, remember to show that no other 12-gon has more collinear vertices than yours.

Topic: Geometria piana, Combinatoria Metodo: Estremalità, Casework Abilita: Ragionamento geometrico, Astrazione, Stima Area: Geometria, Combinatoria, Logica e Probabilita Fonte: apri PDF

Vincenti collineari massimi in un poligono a 12 lati

Tra tutti i poligoni con 5 lati, il numero massimo di vertici collineari (cioè appartenenti a una singola linea) è di tre, come mostrato di seguito.

Qual è il numero massimo di vertici collineari che un poligono con 12 lati può avere?

Attenzione: dopo aver disegnato un 12-gon con il numero massimo di vertici collineari, ricorda di mostrare che nessun altro 12-gon ha più vertici collineari del tuo.

src_obm_2006_n2_f3__Q02

Find all integer pairs with x^3 - y^3 = 3(x^2 - y^2)

Find all ordered pairs $(x,y)$ of integers such that $x^3-y^3=3(x^2-y^2)$.

Topic: Algebra, Teoria dei Numeri Metodo: Fattorizzazione, Casework Abilita: Manipolazione algebrica, Conteggio sistematico, Lettura attenta Area: Algebra e Analisi, Aritmetica e Teoria dei Numeri Fonte: apri PDF

*Ricerca tutte le coppie di numeri interi con x^3 - y^3 = 3(x^2 - y^2) *

Trova tutte le coppie ordinate $(x,y)$ di integri come $x^3-y^3=3(x^2-y^2)$.

src_obm_2006_n2_f3__Q03

Count 3-element subsets {a,b,c} of {1..100} with b arithmetic mean of a and c

How many three-element subsets $\{a,b,c\}$ of $\{1,2,3,\dots ,100\}$ are such that $b$ is the arithmetic mean of $a$ and $c$ (with $a<b<c$)?

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

Contare i sottogruppi di 3 elementi {a,b,c} di {1..100} con b media aritmetica di a e c

Quanti sottoinsiemi di tre elementi $\{a,b,c\}$ di $\{1,2,3,\dots ,100\}$ sono tali che $b$ sia la media aritmetica di $a$ e $c$ (con $a<b<c$)?

src_obm_2006_n2_f3__Q04

Find angle MNR in acute triangle given orthocenter and midpoints

Let $ABC$ be an acute triangle and $H$ its orthocenter. Let $M$, $N$, and $R$ be the midpoints of $AB$, $BC$, and $AH$, respectively. Find the measure of angle $M\hat{N}R$ if angle $A\hat{B}C=70^{\circ }$.

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

Trovare l’angolo MNR in un triangolo acuto dato il centro ortografico e i punti medi

Che $ABC$ sia un triangolo acuto e $H$ il suo centro orto. $M$, $N$ e $R$ siano rispettivamente i punti intermedi di $AB$, $BC$ e $AH$. Trova la misura dell’angolo $M\hat{N}R$ se angolo $A\hat{B}C=70^{\circ }$.

src_obm_2006_n2_f3__Q05

Prove tournament with no k-cycle has a winner and a loser

In a table tennis tournament (in which no game ends in a draw), each of the $n$ participants played exactly once against each of the others. It is known that for all $k>2$, there do not exist $k$ players $J_1,J_2,\dots ,J_k$ such that $J_1$ beat $J_2$, $J_2$ beat $J_3$, $J_3$ beat $J_4$, $\dots$, $J_{k-1}$ beat $J_k$, and $J_k$ beat $J_1$.

Prove that there exists a player who beat all the others and there exists a player who lost to all the others.

Topic: Combinatoria, Logica Metodo: Induzione, Estremalità, Grafi Abilita: Ragionamento geometrico, Astrazione, Modellizzazione Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Il torneo di prova senza k-cycle ha un vincitore e un perdente

In un torneo di tennis da tavolo (in cui nessuna partita termina in pareggio), ciascuno dei partecipanti $n$ gioca esattamente una volta contro ciascuno degli altri. È noto che per tutti i $k>2$ non esistono $k$ giocatori $J_1,J_2,\dots ,J_k$ in modo che $J_1$ batta $J_2$, $J_2$ batta $J_3$, $J_3$ batta $J_4$, $\dots$, $J_{k-1}$ batta $J_k$ e $J_k$ batta $J_1$.

Prove che esiste un giocatore che ha battuto tutti gli altri e esiste un giocatore che ha perso agli altri.

src_obm_2006_n2_f3__Q06