Olimpíadas ⇒ Bulgária 2005 - Lógica Tópico resolvido

[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.

[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.