Observações sobre problemas de Matemática e Lógica

     
         Sempre fui fascinado por problemas de raciocínio lógico-matemático, especialmente os da OBM/IMPA.
         Mas não são tão "difíceis" quando se tem uma forma diferente de ver as coisas, construída pela observação de certos fatos que são desconhecidos pela maioria das pessoas. Por isso aqueles problemas parecem impossíveis à primeira vista.
         É possível observar certos padrões,  que vou comentar sobre eles aqui, e que devem ser bem conhecidos daqueles que são interessados em "competições" desse tipo.
         Quando eu falar sobre os conteúdos mais básicos, não vou apresentar as demonstrações, pois se encontram amplamente disponíveis em livros, na Internet, etc. Apenas vou apresentá-los de forma mais detalhada e ao meu estilo.
         Eu terei a preocupação de apresentar as provas, raciocínios e argumentações quando for abordar questões mais específicas de cada assunto. Em muitos casos é necessário que o leitor já tenha conhecimento prévio de fundamentos matemáticos para poder acompanhar as ideias.
         O que se pode aprender com o exemplo que vou colocar abaixo pode ser generalizado para resolver a maioria dos problemas que envolvem expressões onde as variáveis são números inteiros e positivos.
Na olimpíada do ano passado caiu essa questão:



         Nesse tipo de problema é interessante escrever a expressão como um produto de variáveis igualado a uma constante. Quando isso acontece, podemos analisar os divisores positivos dessa constante para obter as informações desejadas. É uma diretriz para resolver esse tipo de problema. 
Claro que tudo varia de acordo com o caso, com o tipo de questão, mas geralmente esse procedimento ajuda muito a resolver o problema. Eu resolvi ir além do que a questão pede e determinar todos os possíveis pares (x, y) inteiros positivos.


A expressão pode ser reescrita assim:




         Essa última forma é interessante. Agora é só procurar os divisores positivos do número 2015² e igualar cada um deles com a expressão (2015-x). Percebendo-se que esses divisores devem ser menores que 2015, pois senão (2015-x) resultará em um número negativo (lembrando que y é um número positivo). Com o valor de x determinado, fica fácil calcular y.


         Então eu listei todos os divisores positivos de 2015² menores ou iguais a 2015 (se eu esqueci algum, me avise!), e montar uma tabela com cada valor possível:




A propósito, respondendo à questão da olimpíada, o menor valor possível para $x + y$ é $1054 + 2210 = 3264$. Alternativa C.

Algumas vezes é necessário recorrer aos números complexos para resolver esse tipo de problema.
Clique aqui para ver um exemplo.

Outro Exemplo

Essa questão caiu na OBMEP de 2016.

Para quantos valores de $n$ o número $ \displaystyle \frac{5n-12}{n-8}$ é um número natural?

Primeiramente, observe que é possível transformar uma expressão de modo que possamos analisar os divisores de um número natural da seguinte forma:

$ \displaystyle \frac{ax + (b +ac)}{x + c} = a + \frac{b}{x +c}$

Comparando essa com a expressão do problema ($n$ no lugar de $x$), temos que:

$c = -8$;
$a = 5$;
$b + ac = -12 \Rightarrow b = 28$.
Logo, a expressão equivale a

$\displaystyle 5 + \frac{28}{n -8}$

Os possíveis valores de $n$ (positivos) que tornam a expressão dada em um número inteiro e positivo são $\{1, 9, 10, 12, 15, 22, 36 \}$.

Existem outros casos de transformações de expressões dessa forma, por exemplo:

${x^2}(ad) + xy(ae +bd) + x(af +cd) + y(fb + ce) + {y^2}(be) + cf - g = 0$

se torna $(ax + by + c)(dx + ey + f) = g$.

Você pode praticar outros tipos de transformações assim com os mais variados tipos de expressões algébricas, a fim de buscar soluções inteiras.

Ache os valores inteiros de $\displaystyle \frac{a}{a-14}$, sendo $a$ um número inteiro.

Fazendo $a - 14 =  b$, a expressão se torna $\displaystyle \frac{b+14}{b} = 1 + \frac{14}{b}$.
O número $\displaystyle \frac{14}{b}$ é inteiro se $b$ for um divisor de 14, ou seja, se $b = \pm 1$ ou $b = \pm 2$ ou $b = \pm 7$ ou $b = \pm 14$.
Como $a = b + 14$, temos as seguintes possibilidades:
$a$ $\displaystyle \frac{a}{a-14}$
0 0
7 -1
12 -6
13 -13
15 15
16 8
21 3
28 2
________________________________________________________________________________
(Atualização em 04/06/2016)

         Eu criei uma subseção na Wikipedia, a enciclopédia livre que aborda de maneira mais geral os problemas sobre sequências numéricas, inclusive generalizando para o caso de uma sequência de ordem $k$. A partir de agora vou escrever os artigos e pequenas "descobertas" sobre essas coisas neste blog. Vou transcrever o conteúdo que coloquei na Wikipédia aqui.

Generalizando-se para o caso de uma sequência de ordem ''k'', as fórmulas abaixo se aplicam para uma sequência de qualquer ordem.
O primeiro termo dessa sequência é aqui designado por $r_0$, a razão primária (diferença entre dois termos consecutivos na sequência primária) por $r_1$,  a razão secundária (diferença entre dois termos consecutivos na sequência formada pelas razões primárias) por $r_2,$ ... a razão de ordem ''k'' por $r_k$.

De modo semelhante ao fato de dois pontos serem suficientes para se determinar uma reta, com dois valores de uma sequência de ordem 1 (linear) e a posição que ocupam, é possível escrever a equação dessa sequência.
Para uma sequência de ordem 2, são necessários e suficientes 3 valores.

Em geral, para uma sequência de ordem $k$ são necessários $k+1$ valores.

Para uma sequência de ordem $k$, o termo geral é calculado por:

$a_n= \displaystyle \sum_{m=0}^{k}{n-1\choose m}r_m$

Nota: os coeficientes $ \displaystyle n-1 \choose m$ são chamados coeficientes binomiais e são definidos como:

${n-1 \choose m}=\frac{(n-1)!}{(n-1-m)!(m)!},$ 

onde $n$ e $m$ são inteiros, $m\leq n-1$ e 


$x! = 1 \times 2 \times \ldots x$ é o fatorial de x.

O coeficiente binomial ${n-1\choose m}$ corresponde, em análise combinatória, ao número de combinações de ''n-1'' elementos agrupados ''m'' a ''m''.

A soma dos primeiros termos da sequência ($S_n$) é calculada por:

$ \displaystyle S_n=\sum_{m=0}^{k}{n\choose m+1}r_m$

Exemplificando:
1) Determinar o termo geral da sequência {4, 9, 16, 25, 36, 49...}. Sendo $a_n$ o n-ésimo termo dessa sequência. É possível ver que se trata de uma sequência de segunda ordem porque a razão secundária é constante (neste caso é igual a 2), como mostrado abaixo. Generalizando, em uma sequência de ordem ''k'', a  sua razão de ordem ''k'' é constante.

$r_0=a_1=4$

$r_1=a_2-a_1=9-4=5$

$r_2=(16-9)-(9-4)=2$

$r_2=(25-16)-(16-9)=2$

$r_2=(36-25)-(25-16)=2$

$\cdots$

$r_2=(a_n-a_{n-1})-(a_{n-1}-a_{n-2})=2$

Aplicando-se a fórmula:

$\displaystyle a_n=\sum_{m=0}^{2}{n-1\choose m}r_m={n-1\choose 0}r_0+{n-1\choose 1}r_1+{n-1\choose 2}r_2$

$a_n={n-1\choose 0}4+{n-1\choose 1}5+{n-1\choose 2}2$

$a_n={4}+{5(n-1)}+ \frac{2(n-1)(n-2)}{2}={1}+{2n}+{n^2}={(n+1)^2}$

$a_n={(n+1)^2}$

2) Encontrar a soma dos ''n'' primeiros termos dessa sequência ($S_n$).

De modo semelhante ao realizado acima:

$\displaystyle S_n=\sum_{m=0}^{2}{n\choose m+1}r_m$

$S_n={n\choose 1}4+{n\choose 2}5+{n\choose 3}2$

$S_n={n}\left(4+\frac{5(n-1)}{2}+\frac{(n-1)(n-2)}{3}\right)$

3) Em uma sequência de terceira ordem, o sétimo termo é igual a 345, o décimo termo é igual a 1002, o décimo quinto termo é igual a 3377 e o vigésimo quinto termo é igual a 15627.
a) Determine o trigésimo termo dessa sequência.
b) Escreva a equação que determina o n-ésimo termo dessa sequência em função de $n.$

a) Usando-se os dados fornecidos (em azul) na fórmula do $r_n:$

$\displaystyle a_n=\sum_{m=0}^{k}{n-1\choose m}r_m$

$\displaystyle a_7=\sum_{m=0}^{3}{7-1\choose m}r_m=\sum_{m=0}^{3}{6\choose m}r_m.$

Como $a_7=345$, vem:

$345=r_0+ r_1{6\choose 1}+r_2{6\choose 2}+r_3{6\choose 3}$

Da mesma forma, para os outros dados:

${\color{blue}{1002}}=r_0+ r_1{{\color{blue}{10}}-1\choose 1}+r_2{{\color{blue}{10}}-1\choose 2}+r_3{{\color{blue}{10}}-1\choose 3}=r_0+ r_1{9\choose 1}+r_2{9\choose 2}+r_3{9\choose 3}$

${\color{blue}{3377}}=r_0+ r_1{{\color{blue}{15}}-1\choose 1}+r_2{{\color{blue}{15}}-1\choose 2}+r_3{{\color{blue}{15}}-1\choose 3}=r_0+ r_1{14\choose 1}+r_2{14\choose 2}+r_3{14\choose 3}$

${\color{blue}{15627}}=r_0+ r_1{{\color{blue}{25}}-1\choose 1}+r_2{{\color{blue}{25}}-1\choose 2}+r_3{{\color{blue}{25}}-1\choose 3}=r_0+ r_1{24\choose 1}+r_2{24\choose 2}+r_3{24\choose 3}$

Desenvolvendo-se as expressões acima, obtemos esse sistema de 4 equações lineares:

$r_0+6r_1+15r_2+20r_3=345$ 

$r_0+9r_1+36r_2+84r_3=1002$ 

$r_0+14r_1+91r_2+364r_3=3377$ 

$r_0+24r_1+276r_2+2024r_3=15627$ 

O conjunto solução desse sistema $(S)$ é:

$r_0=3$

$r_1=7$

$r_2=12$

$r_3=6$

Aplicando-se a fórmula para o caso $n=30,$ obtemos $a_{30}$:

$\displaystyle a_{30}=\sum_{m=0}^{3}{30-1\choose m}r_m$

$a_{30}=r_0+ r_1{{\color{blue}{30}}-1\choose 1}+r_2{{\color{blue}{30}}-1\choose 2}+r_3{{\color{blue}{30}}-1\choose 3}=r_0+ r_1{29\choose 1}+r_2{29\choose 2}+r_3{29\choose 3}$

$a_{30}=3+ 7{{\color{blue}{30}}-1\choose 1}+12{{\color{blue}{30}}-1\choose 2}+6{{\color{blue}{30}}-1\choose 3}=3+ 7{29\choose 1}+12{29\choose 2}+6{29\choose 3}$

Calculando-se a expressão acima, obtém-se:

$a_{30}=27002$

b) De modo semelhante ao usado no exemplo 1, agora que possuímos os valores das razões $r_0, r_1, r_2$ e $r_3$, basta substituir os seus valores na fórmula de $a_n$:

$\displaystyle a_n=\sum_{m=0}^{k}{n-1\choose m}r_m$

$\displaystyle a_n=\sum_{m=0}^{3}{n-1\choose m}r_m$

$a_n= 3+ 7{n-1\choose 1}+12{n-1\choose 2}+6{n-1\choose 3}$.

Logo:

$a_n=n^3+2$.

Obs. Uma das propriedades dos números binomiais, a Relação de Stifel, diz que:

${n-1\choose m}+{n-1\choose m+1}={n\choose m+1}$.

Isso permite verificar uma propriedade de autoconsistência das fórmulas:

$ \begin{matrix}\underbrace{\displaystyle\sum_{m=0}^{k}{n-1\choose m}r_m}\\a_n\end{matrix}+\begin{matrix}\underbrace{\displaystyle\sum_{m=0}^{k}{n-1\choose m+1}r_m}\\S_{n-1}\end{matrix}=\begin{matrix}\underbrace{\displaystyle\sum_{m=0}^{k}{n\choose m+1}r_m}\\S_n\end{matrix}$
        Sejam, por exemplo, só para ilustrar a ideia, (claro que isso pode ser generalizado) $F_1$, $F_2$ e $F_3$ funções de um certo número de variáveis, de modo que $F_1$ = $F_2$ + $F_3$, podemos aplicar os somatórios com os mesmo limite de variação.
Acho que o leitor já ouviu falar do Triângulo de Pascal, que possui algumas propriedades interessantes, como, por exemplo, a Relação de Stifel:

${n-1\choose m}+{n-1\choose m+1}={n\choose m+1}$.




Aplicando aos dois lados da equação o somatório com o mesmo limite de variação, de $0$ até $k$, ela se torna:


$\displaystyle \sum_{m=0}^{k}{n-1\choose m} = \displaystyle \sum_{m=0}^{k}{n-1\choose m+1}+ \displaystyle \sum_{m=0}^{k}{n\choose m+1}$


Multiplicando-se tudo agora por $r_m$:


$\displaystyle \sum_{m=0}^{k}{n-1\choose m}\cdot r_m = \displaystyle \sum_{m=0}^{k}{n-1\choose m+1}\cdot r_m+ \displaystyle \sum_{m=0}^{k}{n\choose m+1}\cdot r_m$


Veja que $\displaystyle \sum_{m=0}^{k}{n-1\choose m}\cdot r_m$ é o termo geral $a_n$ de uma progressão aritmética de ordem $n$:


$\begin{matrix}\underbrace{\displaystyle \sum_{m=0}^{k}{n-1\choose m}r_m}\\a_n\end{matrix} = \begin{matrix}\underbrace{\displaystyle \sum_{m=0}^{k}{n\choose m+1}r_m}\\S_n\end{matrix} - \begin{matrix}\underbrace{\displaystyle \sum_{m=0}^{k}{n-1\choose m+1}r_m}\\S_{n-1}\end{matrix}$


Incrível, não?

______________________________________________________________________

Balanças de dois pratos e pesagens de valores inteiros
(Atualização em 09/06/2016)

Uma balança de dois pratos é aquela onde se colocam pesos (confeccionados geralmente de metal) e no outro lado se coloca o que se deseja pesar. É possível também colocar pesos nos dois pratos. Para valores inteiros, é possível representar os números usando-se pesos cujos valores são potências de 3, de 1 até $3^n$.

Por exemplo, usando-se os pesos $1 (=3^0)$, $3$ e $3^2$ unidades, (apenas um peso de cada valor!) é possível representar os valores inteiros de 1 até 13 (as somas correspondem aos pesos colocados no mesmo prato da balança que o objeto a ser pesado, enquanto as diferenças são os contrapesos, ou seja, os pesos colocados no outro prato).

Assim:


Número
Representação
1
1
2
3-1
3
3
4
3+1
5
9-(3+1)
6
9-3
7
9-3+1
8
9-1
9
9
10
9+1
11
9+3-1
12
9+3
13
9+3+1

         De um modo geral, usando-se pesos de $1$, $3$, $3^2$,$\cdots$, $3^n$, podemos pesar 

em uma balança valores inteiros de $1$ até $\displaystyle \sum_{p=1}^{n}3^p=\frac{3^{n+1}-1}{2}$.

         Naturalmente que, para pesagens mais precisas, podemos usar valores maiores expressando-se as quantidades em unidades submúltiplas de peso. Por exemplo, 1 Kg pode ser expresso como 1000 gramas.

_________________________________________________________________________________
Somatórios de Frações
(Atualização em 24/11/2017)

Eu complementei também o artigo na Wikipédia sobre somatórios com o conteúdo que vou apresentar a seguir:

1) $\displaystyle \sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{{\pi}^2}{6}$.

($n$ é inteiro positivo).

 $ \displaystyle \sum_{n=-\infty}^\infty |a_n|^2 = \frac{1}{2\pi}\int_{-\pi}^\pi x^2 \, dx,$

Onde:
                       Para $n \ne 0$, e $a_0=0$; Com isso,

                       $|a_n|^2 = $

                       $\frac{1}{n^2}$,  se $n \neq 0$

                       $0$, para $n = 0$,



e

$ \displaystyle \sum_{n=-\infty}^\infty |a_n|^2 = 2\sum_{n=1}^\infty \frac{1}{n^2} = \frac{1}{2\pi} \int_{-\pi}^\pi x^2 \, dx.$

Portanto:

$ \displaystyle \sum_{n=1}^\infty \frac{1}{n^2} = \frac{1}{4\pi}\int_{-\pi}^\pi x^2 \, dx = \frac{\pi^2}{6}$


2) Fixando-se, por exemplo, $n=2$ nas expressões abaixo:

$ \displaystyle\sum_{p=1}^{n}\frac{1}{p} =1+\frac{1}{2}+ \cdots$

$ \displaystyle \sum_{p=1}^{n}\frac{1}{p+1} =\frac{1}{2}+\frac{1}{3}$.

Para $n=3$:
$ \displaystyle\sum_{p=1}^{n}\frac{1}{p} =1+\frac{1}{2}+\frac{1}{3}+\cdots$

$ \displaystyle \sum_{p=1}^{n}\frac{1}{p+1} =\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+ \cdots$

Comparando as expressões, dá para observar de um modo geral que:

$ \displaystyle \sum_{p=1}^{n}\frac{1}{p+1} = \sum_{p=1}^{n}\frac{1}{p} -1 + \frac{1}{n+1}$

Ou melhor:

$ \displaystyle \sum_{p=1}^{n}\frac{1}{p}-\sum_{p=1}^{n}\frac{1}{p+1}=1-\frac{1}{n+1}$

Desenvolvendo-se cada um dos lados:

$ \displaystyle \sum_{p=1}^{n}\left(\frac{1}{p}-\frac{1}{p+1}\right)=\sum_{p=1}^{n}\frac{1}{p(p+1)}=\frac{n}{n+1}$.

Logo:

$\color{blue}{\displaystyle\sum_{p=1}^{n}\frac{1}{p(p+1)}=\frac{n}{n+1}}$.

Observe que, se $n$ for um número muito grande, ou melhor, se ele tender a infinito, essa soma será 1, pois:

$ \displaystyle \lim_{n \to \infty} \frac{n}{n+1}=1$.


Exemplo, calcular a soma:

$\frac{1}{1 \times 2}+\frac{1}{2 \times 3}+\frac{1}{3 \times 4}+\frac{1}{4 \times 5}+\frac{1}{5 \times 6}+\cdots+\frac{1}{2016 \times 2017}$.

Aplicando-se a fórmula para $n =2016$:

$ \displaystyle \sum_{p=1}^{2016}\frac{1}{p(p+1)}=\frac{2016}{2017}=0,99950421417$.

Com esse procedimento também é possível encontrar muitos outros somatórios de frações, como por exemplo:

3) $ \displaystyle \sum_{p=1}^{n}\frac{1}{p^2+3p+2}=\frac{n}{2(n+2)}$

4) $ \displaystyle \sum_{p=1}^{n}\frac{1}{p(p+1)(p+2)}=\frac{n^2+3n}{4n^2+12n+8}$

Perceba que nas expressões (3) e (4), quando $n$ tender a infinito, o valor do somatório tenderá, respectivamente a $\frac{1}{2}$ e $\frac{1}{4}$



5) $\displaystyle \sum_{n=0}^{\infty}(-1)^n\frac{4}{2n+1}= \pi = 3,1415...$
____________________________________________________________________

Alguns problemas interessantes

Um número inteiro $n$, de seis algarismos, tem a propriedade de que ao ser multiplicado por 2, ou 3, 4, 5 ou 6, o resultado sempre é formado pelos mesmos seis algarismos, mas apenas trocando a ordem desses algarismos. Ache esse número.


Se $n$ e $6n$ possuem os mesmos algarismos, então $6n + n = 7n$ e designando por $a_k$, com $k$ variando de $0$ a $5$, cada um de seus algarismos e $a_p = 9 - a_k$,


$\sum_{k=0}^{5} 10^k a_k + \sum_{p=0}^{5} (10^p - 1) a_p$


$7n = 999999 \Rightarrow n = 142857$.


De fato:


$142857 \times 2 = 285714$

$142857 \times 3 = 428571$
$142857 \times 4 = 571428$
$142857 \times 5 = 714285$
$142857 \times 6 = 857142$
________________________________________________________________

Encontre o número de pares ordenados $(x,y)$ que satisfazem à equação $x^8+3y^4 = 4x^2y^3$, para $1 \le y \le 2017$.


Dividindo tudo por $x^8$, vem:

$1+{(y/x^2)}^4 = 4{(y/x^2)}^3$
Fazendo $y/x^2 = z$, vem
$3z^4 - 4z^3 +1 = 0$, ou melhor $(z-1)^2(3z^2+2z+1) = 0$
A única raiz racional é $z=1$, de onde vem $y=x^2$ e pela limitação de que $1 \le y \le 2017$, y pode ser qualquer número quadrado perfeito nesse intervalo, ou seja, $1^2, 2^2, 3^2...44^2$, totalizando 44 pares ordenados.
________________________________________________
Qual o menor valor inteiro possível para o perímetro de um triângulo que possui um dos lados com medida igual a $ \frac{5\sqrt{3}}{2}$?

Em um triângulo qualquer, a soma das medidas dos dois lados menores deve ser maior que a medida do lado maior.

Então, sendo $x$ a soma dos outros dois lados e $P$ o perímetro:

Lembrando que $x + \frac{5\sqrt{3}}{2}=P$.


$x > \frac{5\sqrt{3}}{2} \Leftrightarrow P >5\sqrt{3} \Leftrightarrow P=9$.

___________________________________________________________________________

São desenhados $n$ retângulos em uma superfície plana. Determine o número máximo de regiões distintas não subdivididas que podem ser formadas pelas intersecções desses retângulos.

Resposta: ${(2n-1)}^2$.

___________________________________________________________________________

Probabilidades com eventos viciados

Se a chance de um jogador acertar um pênalti é 0,6, então qual é a chance de ele acertar exatamente 2 pênaltis com 3 chutes (tentativas)?

Esse é um evento "viciado" porque normalmente consideramos que a chance de acerto é igual à chance de erro (50% ou 0,5).
Se não houvesse esse dado de a probabilidade de acerto ser 0,6 (ou seja, se fosse um evento não viciado), poderíamos simplesmente tomar o espaço amostral, sendo A o acerto e E o erro, da seguinte forma:
Todas as possibilidades considerando-se as 3 tentativas:
AAA, AAE, AEA, AEE, EAA, EAE, EEA, EEE (8 possibilidades).
A chance de obter exatamente 2 acertos é, então igual a 3/8.

Mas voltemos ao problema inicial, supondo que a chance de um acerto é 0,6.
Se a chance de acerto é 0,6, então a chance de erro é a probabilidade complementar, ou seja, 1 - 0,6 = 0,4.

Por exemplo, a chance de acertar os 3 chutes (AAA) é igual a $0,6 \times 0,6 \times 0,6 = {0,6}^3$.

Para todas as possibilidades listadas acima, temos o seguinte total:
$\displaystyle {0,6}^3 + 3 \times {{0,6}^2}\times{0,4} + 3 \times {0,6}\times{{0,4}^2} + {0,4}^3 = 1$
(Lembre-se do Binômio de Newton). A probabilidade de obter exatamente 2 acertos é $3 \times {{0,6}^2}\times{0,4}$.

Dividindo esse resultado pelo obtido acima $(1)$, obtemos $3 \times {{0,6}^2}\times{0,4} = 0,432 = 43,2$%.

De um modo geral, considerando-se $m$ lançamentos com probabilidade de acerto de cada um deles igual a $p$, a probabilidade de se obter $n$ acertos, com $0 \leq n \leq m$ é igual a $ \displaystyle C_{m,n} \times p^{n} \times {(1 - p)}^{m - n}$.





Comentários