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

Count representations of integers as sums of squares of naturals

Prove that there exists a number that can be represented in at least 2015 different ways as a sum of squares of non-negative integers (not necessarily all distinct), where the order of the summands does not matter. Two sums that differ only in the arrangement of their terms are considered to represent the same way.

For example, $1^2+1^2+3^2+3^2+7^2+10^2+5^2+12^2$ and $1^2+3^2+1^2+3^2+7^2+5^2+10^2+12^2$ are two different orderings of writing 169 as a sum of squares.

Topic: Teoria dei Numeri, Combinatoria Metodo: Induzione, Conteggio Abilita: Modellizzazione, Riconoscimento di pattern, Conteggio sistematico Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

Conteggiamento delle rappresentazioni di numeri interi come somma dei quadrati di naturali

Prove che esiste un numero che può essere rappresentato in almeno 2015 in modi diversi come una somma di quadrati di numeri interi non negativi (non necessariamente tutti distinti), dove l’ordine dei sommi non importa. Due somme che differiscono solo nell’arredamento dei loro termini sono considerate rappresentate nello stesso modo.

Ad esempio, $1^2+1^2+3^2+3^2+7^2+10^2+5^2+12^2$ e $1^2+3^2+1^2+3^2+7^2+5^2+10^2+12^2$ sono due ordini diversi di scrivere 169 come somma di quadrati.

src_obm_2015_n2_f3__Q01

Convex quadrilateral with perpendiculars; concyclic points and tangent circle

Let $ABCD$ be a convex quadrilateral. The lines $AB$ and $CD$ meet at $E$, and the lines $BC$ and $AD$ meet at $F$. Let $P$ and $Q$ be the feet of the perpendiculars from $E$ to the lines $AB$ and $BC$ respectively, and let $R$ and $S$ be the feet of the perpendiculars from $F$ to the lines $AB$ and $CD$ respectively. The lines $ER$ and $FS$ meet at $T$.

a) Show that there is a circle passing through the points $E$, $F$, $P$, $Q$, $R$, and $S$.

b) Prove that the circumcircle of triangle $RST$ is tangent to the circumcircle of triangle $QRB$.

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

Quadrilaterali convexi con perpendicolari; punti conciclici e cerchio tangente

Che $ABCD$ sia un quadrilaterale convex. Le linee $AB$ e $CD$ si incontrano a $E$ e le linee $BC$ e $AD$ si incontrano a $F$. Il $P$ e il $Q$ sono i piedi delle perpendicolari da $E$ alle linee $AB$ e $BC$ rispettivamente, e il $R$ e il $S$ sono i piedi delle perpendicolari da $F$ alle linee $AB$ e $CD$ rispettivamente. Le linee $ER$ e $FS$ si incontrano a $T$.

a) Indicare che esiste un cerchio che attraversa i punti $E$, $F$, $P$, $Q$, $R$ e $S$.

b) Dimostra che il circoncircolo del triangolo $RST$ è tangente al circoncircolo del triangolo $QRB$.

src_obm_2015_n2_f3__Q02

Triangle subdivided by cevians from n equal divisions; count regions

Let $ABC$ be a triangle and $n$ a positive integer. On side $BC$ consider the points $A_1,A_2,\dots ,A_{2^n-1}$ that divide $BC$ into $2^n$ equal parts, so that $B{A}_1=A_1{A}_2=\cdots =A_{2^n-1}C$. Define the points $B_1,B_2,\dots ,B_{2^n-1}$ on sides $CA$ and $AB$ analogously. Draw the segments $A{A}_1,A{A}_2,\dots ,A{A}_{2^n-1}$, $B{B}_1,B{B}_2,\dots ,B{B}_{2^n-1}$, $C{C}_1,C{C}_2,\dots ,C{C}_{2^n-1}$. Determine, as a function of $n$, into how many regions the region bounded by triangle $ABC$ is divided by these segments.

Topic: Combinatoria, Geometria piana Metodo: Induzione, Ricorsione, Conteggio Abilita: Conteggio sistematico, Riconoscimento di pattern, Modellizzazione Area: Combinatoria, Logica e Probabilita, Geometria Fonte: apri PDF

Triangolo suddiviso da ceviani da n divisioni uguali; regioni di conteggio

Che $ABC$ sia un triangolo e $n$ un intero positivo. Al lato $BC$ si considerano i punti $A_1,A_2,\dots ,A_{2^n-1}$ che dividono $BC$ in $2^n$ parti uguali, in modo che $B{A}_1=A_1{A}_2=\cdots =A_{2^n-1}C$. Definire analogamente i punti $B_1,B_2,\dots ,B_{2^n-1}$ sui lati $CA$ e $AB$. Disegnare i segmenti $A{A}_1,A{A}_2,\dots ,A{A}_{2^n-1}$, $B{B}_1,B{B}_2,\dots ,B{B}_{2^n-1}$, $C{C}_1,C{C}_2,\dots ,C{C}_{2^n-1}$. Determinare, in funzione di $n$, in quante regioni la regione delimitata dal triangolo $ABC$ è divisa da questi segmenti.

src_obm_2015_n2_f3__Q03

Minimize leaves in road-reform process on a tree of n cities

In the country of Arnaldópolis, there are cities connected by $n-1$ roads, and from any city it is possible to reach the capital Arnaldópolis using the roads.

During the first $n-1$ days of the year, one road is chosen each day and its traffic is interrupted for a period that will last at least $n$ days. During this process, we call a city a leaf if it is neither the capital nor connected to exactly one other city to which it is connected. Because of this, a road may only be reformed at most once; that is, only when one of the cities it connects is a leaf.

For example, in the map below with $n=9$ cities, determine an appropriate order of reforms for the 8 roads and, subsequently, determine the number of days in which the number of leaves is not altered during the reform process.

Suppose now that $n=230$ and there are initially 69 leaves. Determine the number of days in which the number of leaves is not altered during any reform process involving all roads in the first 229 days.

Topic: Combinatoria, Logica Metodo: Grafi, Invarianti, Casework Abilita: Modellizzazione, Lettura attenta, Ragionamento geometrico, Conteggio sistematico Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Minimizzare le foglie nel processo di riforma stradale su un albero di n città

Nel paese di Arnaldópolis ci sono città collegate da strade $n-1$ e da qualsiasi città è possibile raggiungere la capitale Arnaldópolis utilizzando le strade.

Durante i primi giorni dell’anno, ogni giorno viene scelto una strada e il suo traffico viene interrotto per un periodo che durerà almeno $n$ giorni. Durante questo processo, chiamiamo una città una foglia ** se non è né la capitale né collegata esattamente ad un’altra città a cui è collegata. Per questo motivo, una strada può essere riformata solo una volta al massimo; cioè solo quando una delle città che la collega è una foglia.

Ad esempio, nella mappa di seguito con $n=9$ città, determinare un ordine appropriato di riforme per le 8 strade e, successivamente, determinare il numero di giorni in cui il numero di foglie non è alterato durante il processo di riforma.

Supponiamo ora che $n=230$ e ci sono inizialmente 69 foglie. Determinare il numero di giorni in cui il numero delle foglie non viene modificato durante qualsiasi processo di riforma che coinvolga tutte le strade nei primi 229 giorni.

src_obm_2015_n2_f3__Q04

Divisors sum alternating formula; find n with given alternating sum

Let $n$ be a positive integer and let $n=d_1>d_2>\cdots >d_k=1$ be its positive divisors.

a) Prove that $d_1-d_2+d_3-\cdots +(-1{)}^{k-1}{d}_k=n-1$ if and only if $n$ is prime or $n=4$.

b) Determine the three smallest integers $n$ for which $d_1-d_2+d_3-\cdots +(-1{)}^{k-1}{d}_k=n-4.$

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

Formula di somma alternata dei divisori; trovare n con somma alternata data

Che $n$ sia un intero positivo e che $n=d_1>d_2>\cdots >d_k=1$ sia il suo divisore positivo.

a) Dimostra che $d_1-d_2+d_3-\cdots +(-1{)}^{k-1}{d}_k=n-1$ se e solo se $n$ è primo o $n=4$.

b) Determinare i tre numeri interi più piccoli $n$ per i quali $d_1-d_2+d_3-\cdots +(-1{)}^{k-1}{d}_k=n-4.$

src_obm_2015_n2_f3__Q05

Scalene triangle with internal bisectors; compute angle BCA

Let $ABC$ be a scalene triangle with $AD$, $BE$, and $CF$ as internal bisectors, with $D$ on $BC$, $E$ on $AC$, and $F$ on $AB$. It is given that $\angle AFE=\angle ADC$. Compute the measure of the angle $\angle BCA$.

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

Triangolo di scalene con bisettori interni; angolo di calcolo BCA

Il $ABC$ deve essere un triangolo di scalene con $AD$, $BE$ e $CF$ come bisettori interni, con $D$ su $BC$, $E$ su $AC$ e $F$ su $AB$. È dato che $\angle AFE=\angle ADC$. Calcolare la misura dell’angolo $\angle BCA$.

src_obm_2015_n2_f3__Q06