OlimpíadasBulgária 2005 - Lógica Tópico resolvido

Aqui devem ser postados problemas Olímpicos. Informe a olimpíada e o ano no título do tópico. Exemplo: (OBM - 2008).

Moderador: [ Moderadores TTB ]

Autor do Tópico
goncalves3718
2 - Nerd
Mensagens: 693
Registrado em: Qui 26 Dez, 2019 15:26
Última visita: 16-10-21
Jan 2020 24 11:28

Bulgária 2005 - Lógica

Mensagem não lida por goncalves3718 »

(Bulgária 2005) Ivo escreve todos os inteiros de [tex3]1[/tex3] a [tex3]100[/tex3] (inclusive) em cartas e dá algumas delas para Iana. Sabe-se que para quaisquer duas destas, uma de Ivo e outra de Iana, a soma dos números não está com Ivo e o produto não está com Iana. Determine o número de cartas de Iana sabendo que a carta [tex3]13[/tex3] está com Ivo.




Avatar do usuário
AnthonyC
4 - Sabe Tudo
Mensagens: 704
Registrado em: Sex 09 Fev, 2018 19:43
Última visita: 14-10-21
Out 2021 13 21:48

Re: Bulgária 2005 - Lógica

Mensagem não lida por AnthonyC »

Se Ivo tiver o [tex3]1[/tex3] , pra qualquer carta de valor [tex3]n[/tex3] que Iana tiver, basta pegar a carta [tex3]1[/tex3] de Ivo e a carta [tex3]n[/tex3] de Iana e multiplicar as duas, resultando em [tex3]n[/tex3] . Mas como Iana não pode ter o produto, então ela não pode conter a carta [tex3]n[/tex3] , para qualquer valor de [tex3]n[/tex3] . Em outras palavras, Iana não pode ter nenhuma carta. Mas segundo o enunciado, Iana contém uma quantidade não nula de cartas. Logo, este caso é impossível.

Portanto, Iana contém o [tex3]1[/tex3]. Como Ivo contém a carta [tex3]13[/tex3], então a carta [tex3]13+1=14 [/tex3] não está com Ivo, pois ele não contém a soma. Assim, [tex3]14[/tex3] está com Iana. Analogamente, [tex3]13+14=27[/tex3] não está com Ivo, assim como as cartas [tex3]13+27=40[/tex3], [tex3]13+40=53[/tex3], [tex3]13+53=66[/tex3], [tex3]13+66=79[/tex3] e [tex3]13+79=92[/tex3]. Assim, pra cada carta [tex3]v[/tex3] que Ivo possui e para cada carta [tex3]a[/tex3] que Iana possuí, as cartas da forma [tex3]a+k\cdot v, k\in \mathbb{N}[/tex3] não estarão com Ivo (vou deixar como tarefa pra você provar isso, dica: indução). Como [tex3]13[/tex3] está com Ivo, vamos estudar o seguinte caso:
[tex3]13=a+kv[/tex3]
Para cada solução inteira que obtivermos da equação acima, teremos uma impossibilidade, pois teremos a soma como sendo 13 e a soma não pode estar com Ivo. Vamos então considerar os casos de [tex3]v<13[/tex3] :
  • [tex3]v=2[/tex3] , não é possível, pois [tex3]13=1+6\cdot 2[/tex3] , logo, 2 está com Iana;
  • [tex3]v=3[/tex3] , não é possível, pois [tex3]13=1+4\cdot 3[/tex3] , logo, 3 está com Iana;
  • [tex3]v=4[/tex3] , não é possível, pois [tex3]13=1+3\cdot 4[/tex3] , logo, 4 está com Iana;
  • [tex3]v=5[/tex3], não é possível, pois [tex3]13=3+2\cdot 5[/tex3], logo, 5 está com Iana;
  • [tex3]v=6[/tex3] , não é possível, pois [tex3]13=1+2\cdot 6[/tex3] , logo, 6 está com Iana;
  • [tex3]v=7[/tex3] , não é possível, pois [tex3]13=6+1\cdot 7[/tex3] , logo, 7 está com Iana;
  • [tex3]v=8[/tex3] , não é possível, pois [tex3]13=7+1\cdot 8[/tex3] , logo, 8 está com Iana;
  • [tex3]v=9[/tex3] , não é possível, pois [tex3]13=8+1\cdot 9[/tex3] , logo, 9 está com Iana;
  • [tex3]v=10[/tex3], não é possível, pois [tex3]13=9+1\cdot 10[/tex3], logo, 10 está com Iana;
  • [tex3]v=11[/tex3] , não é possível, pois [tex3]13=10+1\cdot 11[/tex3] , logo, 11 está com Iana;
  • [tex3]v=12[/tex3] , não é possível, pois [tex3]13=11+1\cdot 12[/tex3] , logo, 12 está com Iana;
Assim, os números da forma [tex3]a+13k[/tex3] , com [tex3]1\leq a\leq 12[/tex3] não estão com Ivo. Mas, como [tex3]0< a<13[/tex3] , então [tex3]a[/tex3] não é divisível por 13. E como [tex3]13k[/tex3] é divisível por 13, então [tex3]a+13k[/tex3] não é divisível por 13. Portanto, todos os números que não são múltiplos de 13 estão com Iana. E, como o produto de [tex3]a[/tex3] com [tex3]v[/tex3] não está com Iana, então os números da forma [tex3]13a[/tex3] (em outras palavras, os múltiplos de 13) não estão com Iana. Portanto, Iana contém todos os números de 1 a 100, exceto os múltiplos de 13. Como [tex3]{100\over 13}\approx 7,69[/tex3] então há 7 múltiplos de 13 menores que 100. Portanto, Iana possuí 93 cartas.



[tex3]\color{YellowOrange}\textbf{Não importa o quanto se esforce ou evolua, você sempre estará abaixo do Sol}[/tex3]
[tex3]\textbf{Escanor}[/tex3]

Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Olimpíadas”