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

Set of positive integers with 2002 elements, no element is a perfect power

Show that there exists a set $A$ formed by positive integers with the following properties:

a) $A$ has 2002 elements.

b) The sum of any quantity of distinct elements of $A$ (at least one) is never a perfect power.

Obs: A perfect power is a number of the form $a^b$, where $a$ and $b$ are positive integers and $b\ge 2$.

Topic: Teoria dei Numeri, Combinatoria Metodo: Casework, Estremalità Abilita: Modellizzazione, Ragionamento geometrico, Manipolazione algebrica, Lettura attenta Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

insieme di integri positivi con elementi 2002, nessun elemento è una potenza perfetta

Indicare che esiste un insieme $A$ formato da integri positivi con le seguenti proprietà:

a) $A$ contiene elementi del 2002.

b) La somma di qualsiasi quantità di elementi distinti di $A$ (almeno uno) non è mai una potenza perfetta.

Obs: Una potenza perfetta è un numero della forma $a^b$, dove $a$ e $b$ sono interi positivi e $b\ge 2$.

src_obm_2002_n3_f3__Q01

Convex cyclic quadrilateral ABCD with point M on CD; triangles ADM and ABCM have equal area and perimeter

$ABCD$ is a convex quadrilateral inscribed in a circle, and $M$ is a point on side $CD$, such that triangle $ADM$ and quadrilateral $ABCM$ have the same area and the same perimeter. Prove that $ABCD$ has two equal sides.

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

ABCD quadrilaterale convex ciclico con punto M su CD; i triangoli ADM e ABCM hanno superficie e perimetro uguali

Il $ABCD$ è un quadrilaterale convex inserito in un cerchio, e il $M$ è un punto laterale $CD$, in modo che il triangolo $ADM$ e il quadrilaterale $ABCM$ abbiano la stessa superficie e lo stesso perimetro. Prove che $ABCD$ ha due lati uguali.

src_obm_2002_n3_f3__Q02

Number cells of m×n grid so adjacent cells in rows i and i+1 share a common side

We number the cells of a quadrille (grid) board of $m\times n$, where $m,n\ge 2$, with the integers $1,2,3,\dots ,mn$ in such a way that, for every $t\le mn-1$, the cells $t$ and $t+1$ have at least one side in common. Show that there exists $i\le mn-3$ such that the cells $i$ and $i+3$ have at least one side in common.

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

Numero di celle della griglia m×n in modo che le celle adiacenti nelle righe i e i+1 condividano un lato comune

Numeriamo le cellule di una scheda quadrillare di $m\times n$, dove $m,n\ge 2$, con i numeri interi $1,2,3,\dots ,mn$ in modo tale che, per ogni $t\le mn-1$, le cellule $t$ e $t+1$ abbiano almeno un lato in comune. Indicare che esiste una $i\le mn-3$ tale che le celle $i$ e $i+3$ abbiano almeno un lato in comune.

src_obm_2002_n3_f3__Q03

Diameter of a nonempty subset of {1,…,n} defined as difference of max and min; sum of diameters of all nonempty subsets

We define the diameter of a nonempty subset of $\{1,2,\dots ,n\}$ as the difference between its largest element and its smallest element (in absolute value). Calculate the sum of the diameters of all nonempty subsets of $\{1,2,\dots ,n\}$.

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

Diametro di un sottoinsieme non vuoto di {1,…,n} definito come differenza di max e min; somma dei diametri di tutti i sottoinsiemi non vuoti

Il diametro di un sottoinsieme non vuoto di $\{1,2,\dots ,n\}$ viene definito come la differenza tra il suo elemento più grande e il suo elemento più piccolo (in valore assoluto). Calcolare la somma dei diametri di tutti i sottoinsiemi non vuoti di $\{1,2,\dots ,n\}$.

src_obm_2002_n3_f3__Q04

Finite set of unit squares with area 4; rearrange to cover a unit square

We have a finite set of squares, of total area $4$. Prove that it is possible to arrange them in such a way as to cover a square of side $1$.

Obs: It is permitted to overlap squares, and parts of them may extend beyond the boundaries of the square to be covered.

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

insieme finito di quadrati unitari con area 4; riorganizzare per coprire un quadrato unitario

Abbiamo un insieme finito di quadrati, di superficie totale $4$. dimostrare che è possibile organizzarli in modo da coprire un quadrato di lato $1$.

Obs: È consentito che i quadrati si sovrappongano e parti di essi possono estendersi oltre i confini del quadrato da coprire.

src_obm_2002_n3_f3__Q05

Arnaldo and Beatriz communicate via smoke signals; bound N ≤ 4096 on dictionary size

Arnaldo and Beatriz communicate during a camping trip using smoke signals, sometimes using a small fire and sometimes a large one. During the time available before morning coffee, Arnaldo manages to send a sequence of 24 smoke puffs. Beatriz and Arnaldo then create a dictionary in order to communicate. The dictionary lists $N$ sequences of 24 puffs of smoke (where $G$ indicates a large smoke puff and $P$ indicates a small smoke puff, for example the sequence $GPGPGPGPGPGPGPGPGPGPGPGPGP$), and the dictionary indicates the meaning of each sequence. To avoid misinterpretations, Arnaldo and Beatriz agree to include in the dictionary only sequences that differ in at least 8 of the 24 positions. More precisely, two sequences are considered close if they differ in at most $8$ of the $24$ positions. Arnaldo and Beatriz agree to not include close sequences in the dictionary.

Prove that $N\le 4096$.

Topic: Combinatoria Metodo: Doppio conteggio, Inclusione-esclusione, Principio dei cassetti Abilita: Modellizzazione, Conteggio sistematico, Ragionamento geometrico, Lettura attenta Area: Combinatoria, Logica e Probabilita Fonte: apri PDF

Arnaldo e Beatriz comunicano tramite segnali di fumo; legato N ≤ 4096 sulla dimensione del dizionario

Arnaldo e Beatriz comunicano durante un viaggio di campeggio usando segnali di fumo, a volte con un piccolo fuoco e a volte con uno grande. Durante il tempo disponibile prima del caffè mattutino, Arnaldo riesce a inviare una sequenza di 24 polveri di fumo. Beatriz e Arnaldo creano poi un dizionario per comunicare. Il dizionario elenca le sequenze $N$ di 24 polveri di fumo (dove $G$ indica un grande polvere di fumo e $P$ indica un piccolo polvere di fumo, ad esempio la sequenza $GPGPGPGPGPGPGPGPGPGPGPGPGP$), e il dizionario indica il significato di ciascuna sequenza. Per evitare interpretazioni errate, Arnaldo e Beatriz concordano di includere nel dizionario solo le sequenze che differiscono in almeno 8 delle 24 posizioni. Più precisamente, due sequenze sono considerate vicine se differiscono in almeno $8$ delle posizioni $24$. Arnaldo e Beatriz concordano di non includere sequenze vicine nel dizionario.

Prove che $N\le 4096$.

src_obm_2002_n3_f3__Q06