FANDOM


A parte inteira de um número real $ x $ é o maior inteiro menor ou igual a $ x $. Esta também é chamada de função chão. Denotaremos a parte inteira de $ x $ por $ \lfloor x\rfloor $.

Também podemos definir a parte fracionária de $ x $ (que será denotada por $ \{x\} $) como sendo $ \{x\}=x-\lfloor x\rfloor $. Observe que $ 0 \leq \{x\} <1 $.

PropriedadesEditar

(i) Sejam $ a $ inteiro e $ x $ um número real. Então $ \lfloor x\rfloor=a \Leftrightarrow a \leq x <a+1 $ ou ainda $ \lfloor x\rfloor=a \Leftrightarrow x-1 <a \leq x. $.

(ii) Podemos pensar na propriedade anterior como sendo: $ a-1 < \lfloor a \rfloor \leq a $ ou $ \lfloor a \rfloor \leq a < \lfloor a \rfloor + 1 $.

(iii) $ a $ é inteiro se, e somente se, $ \lfloor a \rfloor = a $.

(iv) Se $ a $ é inteiro, então $ \lfloor x+a\rfloor=\lfloor x\rfloor+a $

(v) $ \lfloor \{x\}\rfloor=0 $.

(vi) $ \{\{x\}\}=\{x\} $.

(vii) $ \{\{a\}+\{b\}\}=\{a+b\} $.

(viii) Se $ n $ é natural, então $ \{n\{x\}\}=\{nx\} $.

(ix) $ \lfloor x\rfloor+\lfloor y\rfloor \leq \lfloor x+y\rfloor $.

(x) $ \{x\}=\{y\} $ se, e somente se, $ x-y $ é inteiro.

Quantidade de algarismos de um númeroEditar

Se $ x $ for um número inteiro positivo, então ele possui $ \lfloor \log{x} \rfloor+1 $ algarismos.

Exemplo (OBM 2013 - 3ª Fase - Nível 2) Editar

(a) Encontre todos os inteiros positivos $ n $ tais que $ \lfloor \sqrt{n}\rfloor=2013 $.

(b) Sejam $ a $ e $ b $ inteiros positivos tais que $ \lfloor \sqrt{ab}\rfloor = \lfloor \sqrt{a}\rfloor.\lfloor \sqrt{b}\rfloor $. Prove que pelo menos um dos dois inteiros positivos deve ser quadrado perfeito.

Solução:

(a) Observe que

$ \lfloor \sqrt{n} \rfloor = 2013 \Leftrightarrow 2013 \leq \sqrt{n} <2014 \Leftrightarrow 2013^2 \leq n < 2014^2 $.

Logo, os possíveis valores de $ n $ são $ 2013^2,2013^2+1,\dots,2014^2-1 $.

(b) Suponha, por absurdo, que nenhuma destas igualdades sejam válidas. Vamos usar a definição da função parte inteira. Se considerarmos $ N=\lfloor \sqrt{a} \rfloor $, então

$ N \leq \sqrt{a} < N+1 \Leftrightarrow N^2 \leq a < (N+1)^2 \Leftrightarrow 0 \leq a-N^2 < 2N+1 $.

Podemos considerar $ x $ inteiro tal que

$ a=N^2+x $

E aqui $ 1 \leq x \leq 2N $. Observe que não podemos ter $ x=0 $ pois isto implicaria $ N $ inteiro.

Analogamente, para $ M=\lfloor \sqrt{b} \rfloor $ e $ y $ inteiro, podemos ter $ b=M^2+y $, com $ 1 \leq y \leq 2M $.

Vamos usar essas informações para compararmos $ \lfloor \sqrt{ab} \rfloor $ com $ \lfloor \sqrt{a}\rfloor \lfloor\sqrt{b} \rfloor $. Provaremos aqui que, neste caso, $ \lfloor \sqrt{ab} \rfloor > \lfloor \sqrt{a}\rfloor \lfloor\sqrt{b} \rfloor $.

Observe que, como $ x,y \geq 1 $

$ \lfloor \sqrt{ab} \rfloor = \lfloor \sqrt{(N^2+x)(M^2+y)}\rfloor \geq \lfloor \sqrt{(N^2+1)(M^2+1)}\rfloor = \lfloor \sqrt{N^2M^2+N^2+M^2+1} \rfloor $.

Seria legal se, nessa desigualdade acima, tirássemos as raízes. Uma maneira é fazermos aparecer um quadrado perfeito. Existe um quadrado perfeito parecido: $ N^2M^2+2NM+1 $. Para fazermos ele aparecer, basta mostrarmos que $ M^2+N^2 \geq 2MN $. Mas isto é consequência imediata da Desigualdade das Médias. Assim,

$ \lfloor \sqrt{N^2M^2+N^2+M^2+1} \rfloor \geq \lfloor \sqrt{N^2M^2+2NM+1} \rfloor = \lfloor \sqrt{(NM+1)^2} \rfloor = $.

$ =\lfloor MN+1 \rfloor = MN+1 > MN= \lfloor \sqrt{a} \rfloor.\lfloor \sqrt{b} \rfloor $

Ou seja, se $ a $ e $ b $ não são quadrados perfeitos, então

$ \lfloor \sqrt{ab} \rfloor > \lfloor \sqrt{a}\rfloor \lfloor\sqrt{b} \rfloor $.

Logo, para que $ \lfloor \sqrt{ab} \rfloor = \lfloor \sqrt{a}\rfloor \lfloor\sqrt{b} \rfloor $, precisamos que $ a $ ou $ b $ seja quadrado perfeito.

Exemplo (Cone Sul 1995) Editar

Seja $ n $ natural, seja $ f(n)=2n-1995\lfloor\frac{n}{1000}\rfloor $.

(a) Demonstrar que se para algum $ r $, $ f(f(f\dots f(n) \dots))=1995 $ (onde se aplica $ r $ vezes a função $ f $), então $ n $ é múltiplo de $ 1995 $.

(b) Demonstrar que se $ n $ é múltiplo de $ 1995 $, então existe um $ r $ tal que $ f(f(f\dots f(n) \dots))=1995 $ (onde se aplica $ r $ vezes a função $ f $).

(c) Determinar $ r $ se $ n=1995 \times 500=997500 $.

Solução:

(a) Para facilitar a nossa escrita, ao invés de escrevermos $ f(f(f\dots f(n) \dots)) $ (onde $ f $ aparece $ r $ vezes) por $ f^r(n) $.

Já que estamos falando sobre múltiplos de $ 1995 $, vamos olhar módulo $ 1995 $. A vantagem de usá-lo é que $ \lfloor\frac{n}{1000}\rfloor $ some. De fato, como esse número é inteiro,

$ f(n) \equiv 2n \pmod{1995}, $

para todo $ n $ natural. Inclusive se trocarmos $ n $ por $ f(n) $ (para fazermos aparecer $ f(f(x)) $). Se fizermos isto

$ f(f(n)) \equiv 2f(n) \equiv 2^2n \pmod{n}. $

Se continuarmos este raciocínio, podemos conjecturar (e provar por indução) que para todo $ r $ natural

$ f^r(n) \equiv 2^rn \pmod{1995}. $

Se existe $ r $ natural tal que $ f^r(n)=0 $, então

$ 2^rn \equiv 0 \pmod{1995} \Leftrightarrow n \equiv 0 \pmod{1995}, $

pois $ \operatorname{mdc}(2^r,1995)=1 $, para todo $ r $ natural.

(b) Suponha, por absurdo, que existe $ n $ inteiro positivo múltiplo de $ 1995 $ tal que $ f^r(n) $ é diferente de $ 1995 $, para todo $ r $ natural. Chegaremos em um absurdo.

A estratégia aqui é a seguinte: iremos considerar $ m $ o menor valor de $ f^r(n) $, onde $ r $ está variando e encontraremos um valor menor que ele nessas condições: o que nos dará um absurdo.

Observe que se $ t $ é um número natural tal que $ m=f^t(n) $, então, se aplicarmmos $ f $ em ambos os lados da igualdade, $ f(m)=f^{t+1}(n) $. Mostraremos que $ 0<f(m)<m $. Assim, contradiremos a minimalidade de $ m $.

Precisamos de uma desigualdade que envolva $ m $ e $ f(m) $. Como na definição da $ f(m) $ aparece $ \lfloor \frac{m}{1000} \rfloor $, vamos usá-la para conseguirmos uma desigualdade:

$ \frac{m}{1000}-1<\lfloor \frac{m}{1000} \rfloor \leq \frac{m}{1000} \Leftrightarrow \frac{m}{200} \leq f(m) < \frac{m}{200}+1995. (*) $

Como podemos usar que $ n $ é múltiplo de $ 1995 $? Observe que, pela resolução do item anterior, $ f^r(n) \equiv 2^rn \pmod{1995}. $ Desta forma, se $ n $ é múltiplo de $ 1995 $, então $ f^r(n) $ também será, para todo $ r $ natural.

E como podemos usar isso na nossa desigualdade? Ora, se $ f^r(n) $ é múltiplo de $ 1995 $ e diferente dele, segue que $ f^r(n) \geq 2.1995 $, para quaisquer $ r $ e $ n $ naturais e assim $ m \geq 2.1995 $. Agora sim temos condições de mostrarmos que $ 0<f(m)<m $.

Se mostrarmos que $ \frac{m}{200}+1995 < m $, pela desigualdade $ (*) $, podemos concluir que $ f(m)<m $. Porém

$ \frac{m}{200}+1995 < m \Leftrightarrow m> \frac{1995.200}{199}. $

Logo, $ f(m)<m $. E como mostrar que $ f(m)>0 $? Basta vermos que, por $ (*) $

$ f(m)\geq \frac{m}{200} >0 $. Logo, $ 0<f(m)<m $, o que contradiz a minimalidade de $ m $, o que nos dá um absurdo. Logo, existe um $ r $ tal que $ f^r(n)=1995 $.

(c) Vamos determinar $ f^r(n) $ para valores pequenos de $ r $, para ver se conseguimos descobrir alguma coisa. Comecemos com $ f(n) $ para $ n=1995.500 $.

Comecemos calculando $ f(1995.500) $. Para isso, usaremos $ (*) $ do exercício anterior:

$ \frac{1995.500}{200} \leq f(1995.500) < \frac{1995.500}{200}+1995 \Leftrightarrow \frac{1995.5}{2} \leq f(1995.500)<\frac{1995.7}{2}. $

Como $ f(1995.500) $ é múltiplo de $ 1995 $, segue que $ f(1995.500)=3.1995 $. Calculemos $ f^2(1995.500) $, isto é, $ f(f(1995.500))=f(3.1995) $. Se usarmos $ (*) $ novamente

$ \frac{1995.3}{200} \leq f(1995.3) < \frac{1995.3}{200}+1995. $

Já que $ f(1995.3) $ é múltiplo de $ 1995 $, segue que $ f(1995.3)=1995 $. Portanto, $ f^2(1995.500)=1995 $, de onde segue que $ r=2 $.

Exemplo (Cone Sul 1993)Editar

Encontre o número de elementos que um conjunto $ B $ contido em $ \{1,2,...,n\} $ pode ter com a seguinte propriedade: para quaisquer elementos $ a $ e $ b $ de $ B $ ($ a \neq b $), $ (a-b) \nmid (a+b) $.

Solução: Façamos alguns casos particulares para entendermos melhor.

  • $ n=1 $

$ B=\{1\} $ satisfaz as condições do enunciado. Aliás todo conjunto com apenas um elemento satisfaz as condições do enunciado.

  • $ n=2 $

$ B=\{1,2\} $ não satisfaz as condições do enunciado, pois $ (2-1)|(2+1) $. A partir daqui, podemos suspeitar de alguma coisa? Sim: dois números consecutivos não podem estar em $ B $. De fato, isso acontece: se $ n $ e $ n+1 $ pertencessem a $ B $, então $ [(n+1)-n]|[(n+1)+n] $. Absurdo. Logo, neste caso, $ B $ pode ter no máximo $ 1 $ elemento.

  • $ n=3 $

Já sabemos que $ B $ pode ter um elemento. E dois? Como não podemos colocar números consecutivos em $ B $, segue que ele não pode ser $ \{1,2\} $ e nem $ \{2,3\} $. Mas $ B $ pode ser igual a $ \{1,3\} $? Não, pois $ (3-1)|(3+1) $.

Podemos, com isso, nos fazer a seguinte pergunta: $ n $ e $ n+2 $ podem pertencer simultaneamente a $ B $? Não, pois $ [(n+2)-n]|[(n+2)+n] $.

Vale a pena continuar explorando mais: em quais casos $ n $ e $ n+3 $ pertencem simultaneamente a $ B $. Observe que

$ [(n+3)-n]|[(n+3)+n] \Leftrightarrow 3|(2n+3) \Leftrightarrow 3|2n \Leftrightarrow 3|n. $

Com isso, $ n $ e $ n+3 $ pertencem simultaneamente a $ B $ se, e somente se, $ 3 $ não for um divisor de $ n $.

Por isso, parece interessante observarmos o problema módulo $ 3 $. A primeira coisa que podemos suspeitar é: se dois números possuem resto $ 1 $ na divisão por $ 3 $, então eles podem estar no mesmo conjunto? Observe que se $ x $ e $ y $ possuem resto $ 1 $ na divisão por $ 3 $, então existem $ a $ e $ b $ inteiros tais que $ x=3a+1 $ e $ y=3b+1 $. Então

$ x-y=3(a-b) $

$ x+y=3(a+b)+2 $

Então $ (x-y) \nmid (x+y) $, pois $ 3(a-b) \nmid 3(a+b)+2 $, já que $ 3\nmid 3(a+b)+2 $. Analogamente se dois números possuem resto $ 2 $ na divisão por $ 3 $, então eles podem estar no mesmo conjunto.

Com isso, podemos considerar

$ B_1=\{k \in \mathbb{Z}: 1 \leq k \leq n \text{ e } k \equiv 1 \mod 3\} $ ou $ B_2=\{k \in \mathbb{Z}: 1 \leq k \leq n \text{ e } k \equiv 2 \mod 3\}. $

E estes conjuntos irão satisfazer as condições do enunciado. Quantos elementos cada um deles possui? Comecemos com $ B_1 $. Neste caso, podemos escrever o conjunto na forma $ \{1,4,7,...,3a-2\} $, onde $ a $ é o número de elementos. Como determinár $ a $?

Basta notarmos que $ 3a-2 $ pertence ao conjunto, mas $ 3(a+1)-2 $ não. Assim

$ 3a-2 \leq n < 3(a+1)-2 \Leftrightarrow \frac{n+2}{3}-1 < a \leq \frac{n+2}{3} \Leftrightarrow a=\lfloor \frac{n+2}{3}\rfloor. $

Analogamente, $ B_2 $ possui $ \lfloor \frac{n+1}{3}\rfloor $ elementos. Observe que se $ 1 \leq x \leq \lfloor \frac{n+2}{3}\rfloor $, então conseguimos um conjunto de $ x $ elementos que satisfaz as condições do enunciado (basta tomarmos um subconjunto de $ B_1 $ com $ x $ elementos).

Podemos montar algum conjunto com mais de $ \lfloor \frac{n+2}{3}\rfloor $ elementos. Já vimos que não podemos colocar 2 ou mais múltiplos de $ 3 $ em um conjunto.

Além disso, se colocarmos algum número da forma $ 3k $, não podemos colocar nenhum cuja diferença é $ 1 $ ou $ 2 $, ou seja, ficarão de fora $ 3k-2 $, $ 3k-1 $, $ 3k+1 $ e $ 3k+2 $. Ou seja, colocar múltiplos de $ 3 $ faz com que "percamos" elementos para colocar no conjunto e eles só atrapalham na hora de maximizar.

E dá para combinar números a $ 1 $ e $ 2 $ módulo $ 3 $ no mesmo conjunto? Se colocarmos um número da forma $ 3k+1 $, devemos tirar do conjunto os números $ 3k+2 $ e $ 3(k-1)+2 $. Portanto os conjuntos que maximizam são $ B_1 $ e $ B_2 $.

Finalmente, só podemos montar conjuntos $ B $ satisfazendo as condições do enunciado com uma qualquer quantidade menor ou igual a $ \lfloor \frac{n+2}{3}\rfloor $ elementos.

Páginas RelacionadasEditar

Aritmética Modular