Olimpíada Brasileira de Matemática 2017 — Nível 1 — Fase 2

Prove a nonconstant polynomial with nonneg coefficients whose power is positive is itself positive

We say that a polynomial $f$ is positive if it can be written as the product of two nonconstant polynomials with all real coefficients greater than or equal to $0$. Let $f(x)$ be a nonconstant polynomial with nonnegative coefficients such that $f^n$ is positive for some positive integer $n$. Prove that $f(x)$ is positive.

Remark. The problem statement is incorrect. The hypothesis that the leading coefficient of $f$ is non-zero (i.e., $f$ is non-zero) was missing. Alternatively, the conclusion that $f(x)$ is positive is false as stated, since $f(x)=cx$ with $c$ a positive integer is a counterexample. Students who give an answer correcting the problem by adding a hypothesis such as $f(1)=cx$ with $c$ a positive integer, as well as those who correct the problem by adding such a hypothesis as mentioned above and then solve it, will receive full marks together with an apology from the jury.

Topic: Algebra Metodo: Fattorizzazione Abilita: Manipolazione algebrica, Lettura attenta, Astrazione Area: Algebra e Analisi Fonte: apri PDF

Prove un polinomio non costante con coefficienti non negativi la cui potenza è positiva è anche positiva

Diciamo che un polinomio $f$ è positivo se può essere scritto come il prodotto di due polinomi non costanti con tutti i coefficienti reali superiori o uguali a $0$. $f(x)$ sia un polinomio non costante con coefficienti non negativi in modo tale che $f^n$ sia positivo per qualche intero positivo $n$. Provare che $f(x)$ è positivo.

Rimarca. La dichiarazione del problema è errata. Mancava l’ipotesi che il coefficiente di riferimento di $f$ non fosse zero (cioè $f$ non fosse zero). In alternativa, la conclusione che $f(x)$ è positiva è falsa come indicato, poiché $f(x)=cx$ con $c$ un intero positivo è un controesempio. Gli studenti che rispondono correttando il problema aggiungendo un’ipotesi come $f(1)=cx$ con $c$ un numero intero positivo, così come quelli che correttano il problema aggiungendo un’ipotesi come sopra menzionato e poi risolvendo il problema, riceveranno voti completi insieme ad una scusa dalla giuria.

src_obm_2017_n1_f2__Q01

Find common prime divisors of all terms of sequence a·2017^n + b·2016^n

Fix positive integers $a$ and $b$. Find the set of all prime divisors that are common to all terms of the sequence $a_n=a\cdot 2017^n+b\cdot 2016^n.$

Topic: Teoria dei Numeri Metodo: Congruenze Abilita: Manipolazione algebrica, Riconoscimento di pattern, Ragionamento geometrico Area: Aritmetica e Teoria dei Numeri Fonte: apri PDF

Trova i divisori primi comuni di tutti i termini della sequenza a·2017^n + b·2016^n

Fissare i numeri interi positivi $a$ e $b$. Trova l’insieme di tutti i divisori primi che sono comuni a tutti i termini della sequenza $a_n=a\cdot 2017^n+b\cdot 2016^n.$

src_obm_2017_n1_f2__Q02

Permutation of points on half-disk boundary minimising sum of squared distances

Let $X=\{(x,y)\in {\mathbb{R}}^2:x\ge 0,x^2+y^2=1\}\cup \{(x,0):-1\le x\le 1\}$ be the boundary of the closed half-disk of radius $1$.

a) Let $n>1$ be an integer and $P_1,P_2,\dots ,P_n\in X$. Prove that there exists a permutation $\sigma :\{1,2,\dots ,n\}\to \{1,2,\dots ,n\}$ such that ${\sum }_{i=1}^n|P_{\sigma (i+1)}-P_{\sigma (i)}{|}^2\le 8,$ where we define $\sigma (n+1)=\sigma (1)$.

b) Determine all subsets $\{P_1,P_2,\dots ,P_n\}\subset X$ such that for any permutation $\sigma :\{1,2,\dots ,n\}\to \{1,2,\dots ,n\}$, ${\sum }_{i=1}^n|P_{\sigma (i+1)}-P_{\sigma (i)}{|}^2\ge 8$ (where $\sigma (n+1)=\sigma (1)$).

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

Permutazione dei punti sul confine di mezzo disco riducendo al minimo la somma delle distanze quadrate

Il $X=\{(x,y)\in {\mathbb{R}}^2:x\ge 0,x^2+y^2=1\}\cup \{(x,0):-1\le x\le 1\}$ deve essere il limite del mezzo disco chiuso del raggio $1$.

a) Che $n>1$ sia un numero intero e $P_1,P_2,\dots ,P_n\in X$. Prove che esiste una permutazione $\sigma :\{1,2,\dots ,n\}\to \{1,2,\dots ,n\}$ tale che ${\sum }_{i=1}^n|P_{\sigma (i+1)}-P_{\sigma (i)}{|}^2\le 8,$ dove definiamo $\sigma (n+1)=\sigma (1)$.

b) Determinare tutti i sottogruppi $\{P_1,P_2,\dots ,P_n\}\subset X$ in modo tale che per qualsiasi permutazione $\sigma :\{1,2,\dots ,n\}\to \{1,2,\dots ,n\}$, ${\sum }_{i=1}^n|P_{\sigma (i+1)}-P_{\sigma (i)}{|}^2\ge 8$ (dove $\sigma (n+1)=\sigma (1)$).

src_obm_2017_n1_f2__Q03

Strictly positive sequence with controlled differences converging to 0 satisfies a_n ≥ d/n

Let $(a_n{)}_{n\ge 1}$ be a sequence of strictly positive terms with ${\lim }_{n\to \infty }{a}_n=0$, such that for some constant $c>0$ and for all $n\ge 1$, $|a_{n+1}-a_n|\le c\cdot a_n^2.$ Prove that there exists $d>0$ such that $a_n\ge \frac{d}{n}$ for all $n\ge 1$.

Topic: Algebra, Insiemi e funzioni Metodo: Induzione, Disuguaglianze Abilita: Manipolazione algebrica, Stima, Lettura attenta Area: Algebra e Analisi Fonte: apri PDF

Sequenza strettamente positiva con differenze controllate convergenti a 0 soddisfa a_n ≥ d/n

Che $(a_n{)}_{n\ge 1}$ sia una sequenza di termini strettamente positivi con ${\lim }_{n\to \infty }{a}_n=0$, in modo tale che per una costante $c>0$ e per tutte le $n\ge 1$, $|a_{n+1}-a_n|\le c\cdot a_n^2.$ dimostri l’esistenza di $d>0$ in modo tale che $a_n\ge \frac{d}{n}$ per tutte le $n\ge 1$.

src_obm_2017_n1_f2__Q04

Distance inequality involving rows of a real d×n matrix and subspace supremum

Let $d\le n$ be positive integers and $A$ a real $d\times n$ matrix. We view $A$ as a linear transformation ${\mathbb{R}}^n\to {\mathbb{R}}^d$ given by $v\mapsto Av$ (viewing elements of ${\mathbb{R}}^n$ as column vectors). Let $\sigma (A)$ be the supremum over all $d$-dimensional subspaces $W$ of ${\mathbb{R}}^n$ of ${\inf }_{w\in W,|w|=1}|Aw|$. For each $i\in \{1,\dots ,d\}$, let $r(i)\in {\mathbb{R}}^n$ be the $i$-th row-vector of $A$, and for $j\in \{1,\dots ,d\}$ with $j\ne i$, let $d(r(i),r(j))$ denote the Euclidean distance between $r(i)$ and $r(j)$.

For each $i\in \{1,\dots ,d\}$, let $e_i$ be the $i$-th element of the canonical basis of ${\mathbb{R}}^d$. Prove that $\sigma (A)\le {\min }_i{\min }_{j:j\ne i}d(r(i),r(j))\le \sqrt{n}\cdot \sigma (A).$

Remark. $|\cdot |$ denotes the Euclidean norm; $A^T$ is the transpose of $A$; $d(r(i),r(j))$, $1\le j\le d$, $j\ne i$, denotes the distance of $r(i)$ from $r(j)$.

Topic: Algebra, Geometria analitica Metodo: Disuguaglianze Abilita: Manipolazione algebrica, Astrazione, Ragionamento geometrico Area: Algebra e Analisi, Geometria Fonte: apri PDF

Inequità di distanza che coinvolge righe di una matrice reale d×n e di un supremo sottospazio

$d\le n$ siano numeri interi positivi e $A$ una matrice reale $d\times n$. Vediamo $A$ come una trasformazione lineare ${\mathbb{R}}^n\to {\mathbb{R}}^d$ data da $v\mapsto Av$ (visualizzando gli elementi di ${\mathbb{R}}^n$ come vettori di colonna). $\sigma (A)$ sia la suprema su tutti i sottospazi $d$-dimensionali $W$ di ${\mathbb{R}}^n$ di ${\inf }_{w\in W,|w|=1}|Aw|$. Per ogni $i\in \{1,\dots ,d\}$, $r(i)\in {\mathbb{R}}^n$ è il $i$-th row-vector di $A$, e per $j\in \{1,\dots ,d\}$ con $j\ne i$, $d(r(i),r(j))$ indica la distanza euclidica tra $r(i)$ e $r(j)$.

Per ogni $i\in \{1,\dots ,d\}$, $e_i$ sia l’elemento $i$- della base canonica di ${\mathbb{R}}^d$. Provare che $\sigma (A)\le {\min }_i{\min }_{j:j\ne i}d(r(i),r(j))\le \sqrt{n}\cdot \sigma (A).$

Remark. $|\cdot |$ indica la norma euclidiana; $A^T$ è la trasposizione di $A$; $d(r(i),r(j))$, $1\le j\le d$, $j\ne i$, indica la distanza di $r(i)$ da $r(j)$.

src_obm_2017_n1_f2__Q05

Words over {a,b}: m-equivalence of two words of length l via subword deletion

We consider here words over the alphabet $\{a,b\}$: sequences of $a$‘s and $b$‘s of finite length. We write $v⪯w$ if $v$ is a subword of $w$, that is, $v$ can be obtained from $w$ by deleting some letters (for example, $aba⪯abba$). We say that two words $x$ and $y$ are $m$-equivalent if $u⪯x$ as well as $u⪯y$, or neither $u⪯x$ nor $u⪯y$, for every word $u$ with $|u|\le m$ (i.e., whether $u$ is a subword of $x$ is the same as whether $u$ is a subword of $y$, for all words $u$ of length at most $m$).

Let $l$ and $m$ be positive integers.

a) Prove that if $2m\le l$, then there exist two distinct words $x$ and $y$ of length $l$ that are $m$-equivalent.

b) Prove that if $2m>l$, then two distinct words $x$ and $y$ of length $l$ cannot be $m$-equivalent.

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

Parolle sopra {a,b}: m-equivalenza di due parole di lunghezza l tramite cancellazione delle sottoscritte

Prendiamo qui le parole sopra l’alfabeto $\{a,b\}$: sequenze di $a$ e $b$ di lunghezza finita. Scriviamo $v⪯w$ se $v$ è una sottoscrizione ** di $w$, cioè $v$ può essere ottenuto da $w$ eliminando alcune lettere (ad esempio, $aba⪯abba$). Diciamo che due parole $x$ e $y$ sono $m$-equivalenti se $u⪯x$ così come $u⪯y$, o né $u⪯x$ né $u⪯y$, per ogni parola $u$ con $|u|\le m$ (cioè, se $u$ è una sottoscrizione di $x$ è lo stesso che se $u$ è una sottoscrizione di $y$, per tutte le parole $u$ di lunghezza massima $m$).

Lasciate che $l$ e $m$ siano integri positivi.

a) dimostrare che se $2m\le l$, esistono due parole distinte $x$ e $y$ di lunghezza $l$ che sono equivalenti a $m$.

b) dimostrare che se $2m>l$, allora due parole distinte $x$ e $y$ di lunghezza $l$ non possono essere $m$-equivalenti.

src_obm_2017_n1_f2__Q06