Olimpíada Brasileira de Matemática 2021 — Nível 1 — Fase x

Squared numbers: digit sum is a perfect square

We say that a positive integer is quadradoso (squarish) when the sum of its digits is a perfect square. For example, the numbers 211 and 10 are squarish, because $2+1+1=2^2$ and $1+0=1^2$.

a) What is the smallest squarish number greater than 2021?

b) What is the largest squarish number with no repeated digits?

Topic: Teoria dei Numeri Metodo: Casework Abilita: Lettura attenta, Conteggio sistematico, Casework accurato Area: Aritmetica e Teoria dei Numeri Fonte: apri PDF

Numeri quadrati: la somma di cifre è un quadrato perfetto

Diciamo che un intero positivo è quadradoso (quadrato) quando la somma delle sue cifre è un quadrato perfetto. Ad esempio, i numeri 211 e 10 sono quadrati, perché $2+1+1=2^2$ e $1+0=1^2$.

a) Qual è il numero quadrato più piccolo maggiore del 2021?

b) Qual è il numero quadrato più grande senza numeri ripetuti?

src_obm_2021_n1_fx__Q01

Count triples of positive integers with divisibility conditions

How many triples of positive integers $(a,b,c)$ with $a<b<c$ are there such that $a$ is a divisor of $b$, $b$ is a divisor of $c$, and $a+b+c\le 20$?

Topic: Teoria dei Numeri, Combinatoria Metodo: Casework, Conteggio Abilita: Conteggio sistematico, Casework accurato, Lettura attenta Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

Contare triples di numeri interi positivi con condizioni di divisibilità

Quanti triples di integri positivi $(a,b,c)$ con $a<b<c$ sono tali che $a$ sia un divisore di $b$, $b$ sia un divisore di $c$ e $a+b+c\le 20$?

src_obm_2021_n1_fx__Q02

Two adjacent lots: perimeters, lawn area, equal-area passage

Pedro has two adjacent lots — one rectangular and one square — both facing a street. Each lot has an area of $400{\text{m}}^2$. He built a wall along the front of both lots, 36 m long in total (the thicker line in the figure).

a) What are the perimeters (i.e., the sums of the side lengths) of each lot?

b) Pedro made a lawn 2 m wide, running alongside the wall and the side of the square lot, as shown in the figure. What is the total area of this lawn?

c) Pedro wants to give the lots to his two sons, José and João. Since José does not want the lawn, but João wants a passage of width $x$ through José’s lot, as indicated in the figure, leaving the rest of the lawn to João. Pedro will build a fence, calculating $x$ in such a way that the areas of the two lots remain equal. What should the value of $x$ be?

Topic: Geometria piana, Teoria dei Numeri Metodo: Casework Abilita: Ragionamento geometrico, Manipolazione algebrica, Modellizzazione, Lettura attenta Area: Geometria, Aritmetica e Teoria dei Numeri Fonte: apri PDF

Due lotti adiacenti: perimetri, area di prato, passaggio di superficie uguale

Pedro ha due lotti adiacenti uno rettangolare e uno quadrato entrambi rivolti verso una strada. Ogni lotto ha una superficie di $400{\text{m}}^2$. Costruì un muro lungo la parte anteriore di entrambi i lotti, lungo 36 m in totale (la linea più spessa nella figura).

a) Quali sono i perimetri (cioè la somma delle lunghezze laterali) di ciascun lotto?

b) Pedro realizzò un prato di 2 metri di larghezza, che corse lungo il muro e il lato del terreno quadrato, come mostrato nella figura. Qual è la superficie totale di questo prato?

c) Pedro vuole dare il lotto ai suoi due figli, José e João. Poiché José non vuole il prato, ma João vuole un passaggio di larghezza $x$ attraverso il terreno di José, come indicato nella figura, lasciando il resto del prato a João. Pedro costruirà una recinzione, calcolando $x$ in modo tale che le superfici dei due lotti rimangano uguali. Qual è il valore di $x$?

src_obm_2021_n1_fx__Q03

Students opening lockers: doublings mod 2021, count open lockers

In a certain school there are 2021 lockers numbered from 1 to 2021. On a certain day, 2021 students decided to play a game. Initially, all lockers were closed. The students lined up in order in front of the lockers. Student number 1 was called first, student number 2 second, and so on, up to student 2021.

When student $i$ arrives, if locker $i$ is closed he opens it, and if it is open he closes it; he then records the number of the locker he altered and repeats the following process: he doubles the number of the last locker altered; if the result is greater than 2021, he subtracts 2021 from the result obtained, and opens or closes the locker whose number is the new result. For example, student 1 alters lockers $1,2,4,8,\dots ,512,1024$. When doubling 1024 we get 2048, and $2048-2021=27$, so next he alters locker 27. The student continues until the result is 2021, at which point he alters locker 2021 and ends his participation. When student 1 reaches 2048 he gets 2048 and $2048-2021=27$, so the sequence is $1,2,4,8,\dots ,512,1024,27,54,\dots$ and finishes at 2021. By doubling we reach 2048 in $2048-2021=27$, and so on, ending at student 2048, concluding student 1’s participation.

a) After student 16 passes, which lockers numbered 1 to 16 are open?

b) Write the prime factorizations of the numbers listed in the previous item.

c) After all 2021 students have passed, how many lockers are open?

Topic: Teoria dei Numeri, Combinatoria Metodo: Casework, Congruenze, Invarianti Abilita: Riconoscimento di pattern, Conteggio sistematico, Manipolazione algebrica, Lettura attenta Area: Aritmetica e Teoria dei Numeri, Combinatoria, Logica e Probabilita Fonte: apri PDF

Studenti che aprono casili: doppio mod 2021, contare i casili aperti

In una certa scuola ci sono 2021 armadietti numerati dal 1 al 2021. Un certo giorno, 2021 studenti hanno deciso di giocare a un gioco. Inizialmente, tutti gli armadi erano chiusi. Gli studenti si schierarono in ordine davanti ai armadietti. Lo studente numero 1 è stato chiamato primo, lo studente numero 2 secondo, e così via, fino allo studente 2021.

Quando arriva lo studente $i$, se locker $i$ è chiuso lo apre, e se è aperto lo chiude; quindi registra il numero del locker che ha modificato e ripete il seguente processo: raddoppia il numero dell’ultimo locker modificato; se il risultato è superiore al 2021, sottrae il 2021 dal risultato ottenuto, e apre o chiude il locker il cui numero è il nuovo risultato. Per esempio, lo studente 1 cambia i cacciatorni $1,2,4,8,\dots ,512,1024$. Quando raddoppiamo 1024 otteniamo 2048, e $2048-2021=27$, quindi successivamente cambia lo scrigno 27. Lo studente prosegue fino al risultato del 2021, momento in cui cambia locker 2021 e termina la sua partecipazione. Quando lo studente 1 raggiunge il 2048 ottiene il 2048 e $2048-2021=27$, quindi la sequenza è $1,2,4,8,\dots ,512,1024,27,54,\dots$ e termina nel 2021. Doppiando raggiungiamo il 2048 in $2048-2021=27$, e così via, terminando allo studente 2048, concludendo la partecipazione dello studente 1.

a) Dopo il passaggio dello studente 16, quali cassonette numerate da 1 a 16 sono aperte?

b) Scrivere le fatturazioni prime dei numeri elencati nella voce precedente.

c) Dopo che tutti gli studenti del 2021 sono passati, quanti armadietti sono aperti?

src_obm_2021_n1_fx__Q04

Code lock with n buttons: minimum presses to guarantee opening

A certain store sells models of safes with code locks that have $n$ buttons numbered from 1 to $n$ and a button $C$ to start.

The password to open the safe is a non-empty subset of the set $\{1,2,\dots ,n\}$. To open it, the person must press $C$ and then enter a sequence that forms the password. If the safe does not open, the person can press $C$ again and try a new sequence.

For example, for $n=4$, if someone presses the sequence $C413$, the safe is open if the password is $\{4\},\{1\},\{3\},\{4,1\},\{1,3\},\{4,1,3\}$ or $\{4,1,3,\dots \}$ — the order of the elements does not matter. If the safe does not open, the person can press $C$ again and continue testing. A new attempt could be the sequence $C3412$, which would open the safe if the password is $\{3\},\{4\},\{1\},\{2\},\{3,4\},\{4,1\},\{1,2\},\{3,4,1\},\{4,1,2\}$ or $\{3,4,1,2\}$.

For some values of $n$, what matters is the smallest number of times a person needs to press the buttons to guarantee that the safe is opened. For example, for $n=2$, it is necessary to press 5 times and the sequence $C12C2$ covers all possibilities: $\{1\}$ or $\{2\}$ or $\{1,2\}$ — and the sequence $C12C2$ covers all these subsets. You need to press $C$ 2 more times, buttons $C1$ or $C2$, to test the subset $\{1,2\}$ plus 2 more button presses $C1$ or $C2$, to test the element. You need to press 3 buttons to test $\{1,2\}$ and 2 more presses for $\{1\}$ or $\{2\}$ alone with $C2$, covering all possibilities.

Attention: For each item you must present a sequence with the minimum number of presses you found and prove that by pressing fewer times there is always some combination that is not tested.

a) For $n=3$, what is the minimum number of times the buttons $C$, 1, 2, and 3 must be pressed to guarantee that the safe is opened?

b) For $n=4$, what is the minimum number of times the buttons $C$, 1, 2, 3, and 4 must be pressed to guarantee that the safe is opened?

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

Lock di codice con n pulsanti: pressioni minime per garantire l’apertura

Un certo negozio vende modelli di casseforti con serrature a codice che hanno pulsanti $n$ numerati da 1 a $n$ e un pulsante $C$ per avviare.

La password per aprire la cassaforte è un sottogruppo non vuoto del set $\{1,2,\dots ,n\}$. Per aprirlo, la persona deve premere $C$ e quindi inserire una sequenza che forma la password. Se la cassaforte non si apre, la persona può premere di nuovo $C$ e provare una nuova sequenza.

Per esempio, per $n=4$, se qualcuno premesse la sequenza $C413$, la cassaforte è aperta se la password è $\{4\},\{1\},\{3\},\{4,1\},\{1,3\},\{4,1,3\}$ o $\{4,1,3,\dots \}$ l’ordine degli elementi non importa. Se la cassaforte non si apre, la persona può premere di nuovo $C$ e continuare il test. Un nuovo tentativo potrebbe essere la sequenza $C3412$, che aprirebbe la cassaforte se la password è $\{3\},\{4\},\{1\},\{2\},\{3,4\},\{4,1\},\{1,2\},\{3,4,1\},\{4,1,2\}$ o $\{3,4,1,2\}$.

Per alcuni valori di $n$, ciò che conta è il minor numero di volte che una persona deve premere i pulsanti per garantire che la cassaforte sia aperta. Per esempio, per $n=2$ è necessario premere 5 volte e la sequenza $C12C2$ copre tutte le possibilità: $\{1\}$ o $\{2\}$ o $\{1,2\}$ e la sequenza $C12C2$ copre tutti questi sottoinsiemi. È necessario premere $C$ 2 volte di più, i pulsanti $C1$ o $C2$, per testare il sottogruppo $\{1,2\}$ più 2 pulsanti $C1$ o $C2$, per testare l’elemento. È necessario premere 3 pulsanti per testare $\{1,2\}$ e altre 2 pulsanti per $\{1\}$ o $\{2\}$ da solo con $C2$, coprendo tutte le possibilità.

*Attenzione: * Per ogni elemento è necessario presentare una sequenza con il numero minimo di presse che si trovano e dimostrare che premendo meno volte c’è sempre una combinazione che non viene testata.

a) Per $n=3$, qual è il numero minimo di volte che occorre premere i pulsanti $C$, 1, 2 e 3 per garantire l’apertura della cassaforte?

b) Per $n=4$, qual è il numero minimo di volte che è necessario premere i pulsanti $C$, 1, 2, 3 e 4 per garantire l’apertura della cassaforte?

src_obm_2021_n1_fx__Q05