Problemas em Invariantes e Monovariantes

Prof. George Lucas

Semana Olı́mpica 2024 - Nı́vel 2

1. Inicialmennte os números 3, 4 e 12 estão escritos em uma folha de papel.

Em cada passo, devem-se escolher dois números a e b e substituı́-los por 0.6a +
0.8b e 0.8a − 0.6b.
(a) É possı́vel, em algum momento, obter os números 4, 6 e 12?
(b) É possı́vel, em algum momento, obter números x, y e z tais que |x − 4| <
√1 , |y − 6| < √1 , |z − 12| < √1 ?
3 3 3

2. Cada um dos números de 1 a 106 é repetidamente substituı́do pela soma

de seus dı́gitos até obtermos 106 números de um dı́gito. Teremos mais 1s ou 2s?

3. O número 999...9(19979s) é escrito no quadro. A cada minuto, um dos

números escritos no quadro é fatorado em dois fatores e é apagado do quadro.
Cada um desse fatores é (independentemente) acrescentado ou diminuı́do de
duas unidades, e os dois números resultantes são escritos no quadro. É possı́vel,
em algum momento, obter todos os números escritos no quadro iguais a 9?

4. Um cı́rculo é dividido em seis setores. Então os números 1, 0, 1, 0, 0, 0 são

escritos nos setores, no sentido antihorário. Uma operação permitida é adicionar
uma unidade em dois setores vizinhos. É possı́vel, após um número finito de
operações, obter todos os números dos setores iguais?

5. Em cada casa de um tabuleiro n × n escreve-se um número real. Uma

operação consiste em trocar todos os sinais de uma linha ou coluna. Prove que,
realizando algumas operações, é possı́vel obter um novo tabuleiro para o qual a
soma de cada linha e coluna é não-negativa.

6. Em cada vértice de um quadrado temos certa quantidade de fichas (pos-

sivelmente nenhuma). Uma operação permitida é remover certa quantidade de
fichas de um vértice e colocar o dobro de fichas em um dos vértices adjacentes a
este. Suponha que começamos com apenas uma ficha em algum dos vértices, e os
outros três vértices estando vazios. É possı́vel, após certo número de movimen-
tos, termos 1, 9, 8, 9 fichas nos vértices do quadrado, quando este é percorrida
no sentido horário?

1
 7. Há a fichas, b fichas pretas e c fichas vermelhas em uma mesa. Em
cada passo trocamos duas fichas de cores diferentes por uma da terceira cor.
Determine as condições necessárias e suficientes para a, b, c tal que é possı́vel
chegarmos a apenas uma ficha no final.

8. (IMO Shortlist) Os números de 1 a n são colocados em ordem arbitrária.

Definimos uma operação como segue: Se o primeiro número da sequência é
k, então invertemos a ordem dos k primeiros números na sequência (então o
primeiro se torna o k-ésimo, o segundo se torna o (k − 1)-ésimo e assim suces-
sivamente). Prove que após um número finito de operações, o primeiro termo
será 1.

9. (OBM 2004) Esmeralda tem uma pilha com 100 pedras. Ela divide essa
pilha em duas novas pilhas e em seguida multiplica as quantidades de pedras
nessas duas novas pilhas e escreve o produto no quadro. Ela então escolhe uma
pilha com mais de uma pedra e repete este procedimento: a pilha é dividida
em duas, as quantidades de pedras nessas pilhas são multiplicadas e o produto
é escrito no quadro. Esta operação é realizada até se obter todas as pilhas com
uma pedra. Quais são os possı́veis valores da soma de todos os números escritos
no quadro.

10. (Bulgaria) Há 2000 bolas brancas em uma caixa. Há ainda um número
suficiente de bolas brancas, verdes e vermelhas fora da caixa. As seguintes
operações são permitidas com as bolas:
(a) Trocar duas bolas brancas por uma verde;
(b) Trocar duas bolas vermelhas por uma verde;
(c) Trocar duas bolas verdes por uma branca e uma vermelha;
(d) Trocar uma bola branca e uma verde por uma vermelha;
(e) Trocar uma bola verde e uma vermelha por uma branca.
Após uma quantidade finita de operações, restam três bolas na caixa. Prove que
ao menos uma delas é verde. Existe um número finito de operações que deixa
na caixa somente uma bola?

11. Considere um conjunto de pessoas. Prove que é possı́vel dividir o con-

junto em dois grupos de modo que cada pessoa tenha uma quantidade de amigos
no outro grupo maior ou igual a quantidade de amigos no grupo que está. Con-
sidere a amizade como uma relação recı́proca.

12. Inicialmente temos n > 1 números escritos em uma lousa. Uma operação
permitida com esses números é escolher dois deles, digamos a e b, apagá-los, e
escrever na lousa a+b
4 . Se inicialmente todos os números escritos eram iguais a
1, prove que quando restar apenas um número, ele será maior ou igual a n1 .

13. Seja c um inteiro positivo. São escritos n números inteiros em um quadro.

2
Uma operação consiste em escolher dois números escritos x e y, 0 ≤ x − y ≤ c, e
substituı́-los por x + 1 e y − 1. Prove que, após um número finitos de operações,
não será possı́vel realizar mais operação alguma.

14. Cada termo da sequência 1, 0, 1, 0, 1, 0, ... começando pelo sétimo é o

último dı́gito da soma dos seis últimos termos. Prove que a subsequência de seis
termos consecutivos 0, 1, 0, 1, 0, 1 nunca aparece.

15. (IMO Shortlist) Considere 2009 cartas, cada uma com um lado lumi-
noso e um lado negro enfileirados paralelamente sobre uma longa mesa. Dois
jogadores, do mesmo lado da mesa, Luke e Darth, jogam um jogo com movi-
mentos alternados. Cada movimento consiste em escolher um bloco de 50 cartas
consecutivas, cuja mais à esquerda exiba seu lado luminoso, e virá-las. Assim
as que exibem o lado luminoso passam a exibir o lado negro e vice-versa. Quem
não puder mais realizar um movimento, perde.
(a) Prove que o jogo necessariamente termina.
(b) Sabendo que Luke é o primeiro a jogar, quem tem a estratégia vencedora?

16. Considere as palavras formadas pelas letras a e b. São permitidas as

seguintes operações:
(i) Trocar um bloco aba por um bloco b e vice-versa;
(ii) Trocar um bloco bba por um bloco a e vice-versa.
É possı́vel obter a sequência baa...a (com 2023as) a partir da sequência aaa...ab
(com 2023as)?

17. Os números 1 a 100 são escritos em um tabuleiro em um tabuleiro 10×10

tal que a intersecção da i-ésima linha com a j-ésima coluna tem escrito o número
10(i − 1) + j. Em cada passo realizamos o seguinte movimento: escolhemos uma
casa e dois de seus vizinhos opostos (isto é, o de cima e o de baixo ou o da
direita e da esquerda e decrescemos duas unidades desse número e acrescenta-
mos uma unidade a cada um de seus vizinhos escolhidos ou acrescentamos duas
unidades a esse número e decrescemos uma unidade de cada um de seus vizin-
hos escolhidos. Após um número finito de movimentos, obtemos novamente os
números 1, 2, ..., 100 em alguma ordem. Prove que eles estão na mesma ordem
que estavam no inı́cio.

18. (Teste Cone Sul 2016) Em uma lousa estão escritos alguns números in-
teiros. Wesley pode fazer duas operações com os números escritos na lousa. A
operação saf a consiste em apagar dois número n e n + 1 e escrever o número
n − 2. A operação f adao consiste apagar dois números n e n + 4 e escrever o
número n − 1. Wesley pode fazer saf a ou f adao quantas vezes quiser.
(a) Prove que é possı́vel Wesley escrever uma quantidade finita de inteiros pos-
itivos distintos dois a dois na lousa e, usando as operações, obter o número
−3. Observe que após as operações podem ter números repetidos, mas não há
inteiros positivos repetidos entre os números inicialmente escritos por Wesley.

3
(b) Prove que, partindo de inteiros positivos distintos dois a dois, não é possı́vel
obter um inteiro menor que −3.

19. (Russia) São dados quatro triângulos retângulos congruentes. Uma

operação consiste em cortar um dos triângulos ao longo de sua altura relativa a
hipotenusa, substituindo-o pelos dois novos triângulos resultantes. Prove que,
independente de como realizamos as operações, sempre haverá dois triângulos
congruentes.

20. (OBM 2022) Um jogo para uma pessoa tem as seguintes regras: Inicil-
amente há dez pilhas de pedras, com 1, 2, ..., 10 pedras, respectivamente. Uma
jogada consiste em fazer uma das duas seguintes operações:
(i) escolher duas pilhas, cada uma com pelo menos duas pedras, juntá-las e de-
pois adicionar mais duas pedras a nova pilha;
(ii) escolher uma pilha com pelo menos 4 pedras, tirar duas pedras dela e separá-
la em duas pilhas de quantidade de pedras positivas escolhidas pelo jogador.
Tal jogador realiza operações até um momento que não é possı́vel mais realizar
operações.
Mostre que o número de pilhas com apenas uma pedra ao final do jogo é sempre
o mesmo, independente de como se realizam as jogadas.

21. (Teste Cone Sul 2023) Os números 1, 2, 3, ..., 50 são escritos em um

quadro. Letı́cia faz as seguintes operações: ela apaga dois números, a e b,
do quadro, depois escreve no mesmo o resultado de a + b e anota o número
ab(a + b) no seu caderno. Após realizar 49 dessas operações, quando há apenas
um número escrito no quadro, Letı́cia calcula a soma S dos 49 números que
escreveu no caderno.
(a) Mostre que S não depende da ordem em que Letı́cia escolhe os números para
realizar as operações.
(b) Encontre o valor de S.