Olimpíadas ⇒ Bulgá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 ]

Responder

Autor do Tópico
goncalves3718
3 - Destaque
Mensagens: 816
Registrado em: 26 Dez 2019, 15:26
Última visita: 11-04-23
Agradeceu: 19 vezes
Agradeceram: 30 vezes
Jan 2020 24 11:28

Bulgária 2005 - Lógica

Mensagem não lidapor goncalves3718 » 24 Jan 2020, 11:28

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.
Voltar ao topo
Avatar do usuário

AnthonyC
4 - Sabe Tudo
Mensagens: 964
Registrado em: 09 Fev 2018, 19:43
Última visita: 21-02-24
Agradeceu: 1 vez
Agradeceram: 2 vezes
Out 2021 13 21:48

Re: Bulgária 2005 - Lógica

Mensagem não lidapor AnthonyC » 13 Out 2021, 21:48

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]
Voltar ao topo
Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última mensagem
  • Nova mensagem (Bulgária - 2011)
    por futuromilitar » » em Olimpíadas
    2 Respostas
    1192 Exibições
    Última mensagem por Helo
  • Nova mensagem Olimpíada da Bulgária - 2004 - Sequência e Permutação
    por Auto Excluído (ID:17906) » » em Olimpíadas
    0 Respostas
    880 Exibições
    Última mensagem por Auto Excluído (ID:17906)
  • Nova mensagem (Bulgária) Números Complexos
    por Gu178 » » em Olimpíadas
    1 Respostas
    1184 Exibições
    Última mensagem por undefinied3
  • Nova mensagem (Bulgária)Equação
    por Flavio2020 » » em Olimpíadas
    1 Respostas
    867 Exibições
    Última mensagem por Auto Excluído (ID:12031)
  • Nova mensagem (Bulgária) Polinômio
    por Flavio2020 » » em Olimpíadas
    2 Respostas
    1076 Exibições
    Última mensagem por Ittalo25

Voltar para “Olimpíadas”