FATOS MATEMÁTICOS: 2013/02

quinta-feira, 28 de fevereiro de 2013

Grafos e Matrizes de Adjacência (Parte 2)

Neste post, responderemos as duas perguntas que foram apresentadas na parte 1 o qual reproduzimos abaixo:

$[;i);]$ Quais os vértices que estão conectados por uma sequência de dois lados?

$[;ii);]$ Quantas sequências distintas de dois lados conectam cada par de vértices?

Considere a figura acima. Os vértices [;B;] e [;F;] estão conectados por duas sequências de dois lados ([;BCF;] ou [;BEF;]). Note que os dois lados entre [;B;] e [;C;] são indistinguíves.

Seja [;m_{ij};] a [;(i,j);] entrada na matriz de adjacência [;M;]. Note que

[;m_{21}m_{16} + m_{22}m_{26} +m_{23}m_{36} + m_{24}m_{46} + m_{25}m_{56} + m_{26}m_{66} =;]
[; = 1\cdot 0 + 0\cdot 0 + 1\cdot 1 + 0\cdot 0 + 1\cdot 1 + 0\cdot 1 = 2;]
o qual é o número de sequências de dois lados entre [;B;] e [;F;]. Note que, desde que [;B;] conecta com [;C;] e [;C;] com [;F;], [;m_{23}m_{36} = 1;]; desde que [;B;] conecta com [;A;] e [;A;] não conecta com [;F;], [;B;] não conecta com [;F;] através de [;A;] com uma sequência de dois lados, por isso, [;m_{21}m_{16} = 0;]. Somando todos os pontos intermediários temos o resultado.

Agora note que

[;\sum_{k=1}^{6}m_{2k}m_{k6};]

é a entrada [;(2,6);] da matriz [;M^2;].

Observação 1: O número de sequências de dois lados entre o vértice [;i;] e o vértice [;j;] em um grafo com matriz adjacência [;M;] é a entrada [;(i,j);] na matriz [;M^k;]. Se [;M;] é a matriz adjacência para a figura acima, então

Portanto, existe uma sequência de dois passos (lados) de [;C;] a [;F;], e existem [;5;] sequências de [;3;] passos entre [;C;] e [;F;]. Observando a figura abaixo,

As iniciais acima representam as seguintes cidades:

B = Boston

H = Hyannis

M = Martha`s Vineyard

Na = Nantucket

Ne = New Bedford

P = Providence

Pr = Provincetown

vemos que Nantucket é conectada em duas etapas a partir de Boston (via Hyannis ou Martha's Vineyard), mas observe que existe um vôo direto entre as duas cidades. Assim, temos a seguinte pergunta:

Qual é o menor número de arestas (lados) que devem ser percorridos para ir de um vértice [;A;] para um vértice [;B;]?

Para responder esta questão, considere a matriz

[;S_k = M + M^2 + \ldots + M^k;]

A [;(i,j);] entrada nesta matriz fornece o número de maneiras de interligar o vértice [;i;] ao vértice [;j;] em [;k;] passos ou menos. Se tal viagem é impossível, esta entrada será zero. Portanto, para encontrar o menor número de passos entre os vértices continue calculando [;S_k;] à medida que aumenta [;k;], o primeiro [;k;] para o qual a entrada [;(i,j);] em [;S_k;] é diferente de zero é o menor número de passos entre [;i;] e [;j;].

Outra questão referente a um grafo é se é possível ir de um vértice a qualquer outro. Se um grafo possui a propriedade de que cada vértice está ligado a todos os outros em um determinado número de passos dizemos que ele está conectado.

Como podemos determinar se um grafo está conectado?

Isso é fácil de ver se o grafo é pequeno. Mas é mais difícil de ver a partir da matriz de adjacência. No entanto, existe um cálculo que pode ser feito.

Suponha que o grafo possui [;n;] vértices. Então o maior número de passos que poderia tomar para ir de um vértice para qualquer outro é [;n;] passos. Assim,

[;S_n = \sum_{k=1}^{n}M^k;]

pode nos ajudar. Se houver qualquer zero nesta matriz será impossível conectar um par de vértices e portanto, o grafo não está conectado.

Gostará de ler também:
- Grafos e Matrizes de Adjacência (Parte 1);
- Matrizes (Parte 1);

sábado, 23 de fevereiro de 2013

O Valor Médio de uma Função

Uma das aplicações interessantes das integrais definidas além do cálculo da área de uma região curvilínea e do volume de um sólido de revolução, é determinar o valor médio de uma função sobre um intervalo [;[a,b];] . Esta grandeza já foi abordada no post Teoremas Relativos a Integral Definda (Parte 3) no qual foi apresentado o Teorema Fundamental do Cálculo.

A forma apresentada foi através de uma definição, sem muita explicação que a expressão em termos de integral realmente está relacionada com uma média. Pensando sobre este assunto, apresentaremos neste post a média de uma função de uma forma construtiva.

Definição 1: Dado o conjunto de pontos [;\{y_1,y_2,\ldots,y_n\};], o valor médio denotado por [;VM;] é igual a soma desses números divididos por [;n;], ou seja,

[;VM = \frac{y_1 + y_2 + \ldots + y_n}{n} \qquad (1);]

Esta expressão é muito útil para valores discretos. Por exemplo, o valor médio do conjunto de pontos [;\{1.2,1.5,2.4,3.1\};] é [;VM = 2.05;]. Na Matemática e em outros campos da ciência aplicada, existem muitos modelos contínuos os quais precisamos calcular o valor médio. Deste modo surge a pergunta:

Como calcular o valor de médio de um conjunto contínuo de pontos, tal como uma imagem de uma função contínua definida em um intervalo?

Para responder esta pergunta, seja [;f;] uma função contínua sobre o intervalo [;[a,b];]. Em seguida, dividimos [;[a,b];] em [;n;] subintervalos pelos pontos [;a = x_0,x_1,x_2,\ldots,x_n = b;]. Para facilitar o entendimento, suponhamos que os intervalos são uniformes. Deste modo, o comprimento de cada um deles é [;\Delta x = (b - a)/n;] conforme a figura abaixo.

Tome um ponto [;\xi_1;] no subintervalo [;[a,x_1);], [;\xi_2;] em [;[x_1,x_2);] ou em geral, [;\xi_k;] no subintervalo [;[x_k,x_{k+1});] para [;k=0,1,\ldots,n-1;]. O valor médio de [;f;] no conjunto [;\{\xi_1,\xi_2,\ldots,\xi_n\};] de acordo com a expressão [;(1);] é:

[;VM = \frac{f(\xi_1) + f(\xi_2) + \ldots + f(\xi_n)}{n} = \frac{1}{n}\sum_{k=1}^{n}f(\xi_k);]

Sendo [;n = \frac{b - a}{\Delta x};], segue que

[;VM = \frac{1}{b - a}\sum_{k=1}^{n}f(\xi_k)\Delta x \qquad (2);]

Sendo [;f;] contínua, a medida que aumentamos o número de pontos, a expressão [;(2);] aproxima-se da integral definda de [;f;] sobre [;[a,b];]. Deste modo, definimos a valor médio de [;f;] sobre [;[a,b];] por

[;VM(f) = \lim_{n \to \infty} VM = \lim_{n \to \infty}\biggl[\frac{1}{b - a}\sum_{k=1}^{n}f(\xi_k)\Delta x\biggr];]

[;= \frac{1}{b - a}\quad \lim_{n \to \infty}\sum_{k=1}^{n}f(\xi_k)\Delta x = \frac{1}{b - a}\int_{a}^{b}f(x)dx \qquad (3);]

Exemplo 1: Determine a temperatura média de uma estufa, sabendo que [;T(t);] é dada pela função

[;T(t) = -\frac{t^2}{60} + \frac{t}{2} + 20 \qquad t \in [8,18];]

Resolução: Da expressão [;(3);] acima, temos

[;VM(T) = \frac{1}{18-8}\int_{8}^{18}\biggl(-\frac{t^2}{60} + \frac{t}{2} + 20\biggr)dt = 23,5^{\circ} \ C;]

Teorema 1: Se [;f;] é uma função contínua em [;[a,b];], então existem [;\alpha;], [;\beta \in [a,b];] tal que [;f(\alpha) \leq f(x) \leq f(\beta);] para todo [;x \in [a,b];].

A prova envolve conceitos matemáticos sofisticados e portanto neste post, será omitida.

Corolário 1: Se [;f;] é uma função contínua em [;[a,b];], existe [;c \in [a,b];] tal que [;VM(f) = f(c);].

Demonstração: Pelo teorema 1, existem [;\alpha, \beta \in \mathbb{R};] tais que [;m \leq f(x) \leq M;], seando [;m = f(\alpha);] e [;M = f(\beta);]. Integrando esta desigualdades de [;a;] a [;b;], temos:

[;\int_{a}^{b}mdx \leq \int_{a}^{b}f(x)dx \leq \int_{a}^{b}Mdx \quad \Rightarrow;]

[;m(b - a) \leq \int_{a}^{b}f(x)dx \leq M(b - a) \quad \Rightarrow \quad m \leq VM(f) \leq M;]

sendo [;f;] contínua, existe [;c \in [a,b];] tal que [;VM(f) = f(c);].

terça-feira, 19 de fevereiro de 2013

Editorial Fevereiro/2013

Prezados leitores e admiradores do blog.

Venho comunicar a todos que o blog após três anos, está um problema técnico de não renderizar as equações matemáticas e por isso, todos os posts estão "indecifráveis". Tais posts foi escrito na linguagem tex e usando o complemento Graeseymonkey que apesar de instalado, está com mal funcionamento.

Adotei este sistema pela sua praticidade há mais de três anos e neste período, foram quase 700 posts, sendo que mais de 90% deles possuem alguma fórmula ou expressão matemática. Já descobri duas outras maneiras distintas de colocar as equações no blog, mas terei que alterar manualmente todas as equações, algo completamente inviável.

Peço a paciência e atenção de todos durante este período turbulento. Toda sugestão será bem-vinda.

Atenciosamente,

Prof. Paulo Sérgio C. Lino

Articulador do blog

sexta-feira, 15 de fevereiro de 2013

Problemas dos Fatos Matemáticos (Parte 22)

65) Dada a expressão

$V_n = \sin x_1\cos x_2 + \sin x_2\cos x_3 + \ldots + \sin x_n\cos x_1$

onde $x_1,x_2,\ldots,x_n$ são números reais arbitrários, mostre que $V_n \leq n/2$ .

66) Ache todas as soluções reais do sistema de equações

$\begin{cases} x^3 = 2y - 1\\ y^3 = 2z - 1\\ z^3 = 2x - 1 \end{cases}$

67) Sejam $a,b$ e $c$ números reais não-negativos tal que $a + b + c \geq abc$ . Prove que $a^2 + b^2 + c^2 \geq abc$ .

68) Considere três jarras com capacidade para $3,5$ e $8$ litros. A jarra de $8$ litros está cheia de água. Você é capaz de medir exatamente $4$ litros?

Observação: Você não possui outros recipientes para trabalhar e os recipientes não estão marcados, indicando as frações. Você pode despejar a água de um recipiente em outro quantas vezes quiser.

Observação: A novidade dos Problemas dos Fatos Matemáticos neste ano é o número questões que passa de três para quatro em cada mês.

Vejamos agora, a solução dos problemas dos Fatos Matemáticos (Parte 21).

61) Prove que

$\sqrt[n]{n} < 1 + \sqrt{\frac{2}{n}}$

se $n$ é um inteiro positivo.

Resolução: Pelo binômio de Newton,

$\biggl(1 + \sqrt{\frac{2}{n}}\biggr)^n = \sum_{k=0}^{n}\binom{n}{k}\biggl(\sqrt{\frac{2}{n}} \biggr)^k$

$\geq 1 + n\sqrt{\frac{2}{n}} + \frac{n(n-1)}{2}\biggl(\sqrt{\frac{2}{n}}\biggr)^2$

$= 1 + \sqrt{2n} + n - 1 > n$

de modo que

$\sqrt[n]{n} < 1 + \sqrt{\frac{2}{n}}$

62) Na figura abaixo, $AP/PB = 3/4$ e $AR/RC = 3/2$ . Sendo $BC = 1$ , prove que $C$ é o ponto médio de $BZ$ .

Resolução: Seja $D$ um ponto sobre o prolongamento de $AC$ de modo que $RC = CD$ , conforme a figura abaixo.

Afirmação 1: $\triangle APR \sim \triangle ABD$
De fato,

$\frac{AP}{PB} = \frac{3}{4}$

$\frac{AR}{RD} = \frac{AR}{RC + RD} = \frac{AR}{2RC} = \frac{3/2}{2} = \frac{3}{4}$

Assim,

$\frac{PB}{AP} = \frac{4}{3} \quad \Rightarrow \quad \frac{PB}{AP} + 1 = \frac{4}{3} + 1 \quad \Rightarrow \quad \frac{PB + AP}{AP} =\frac{AB}{AP} = \frac{7}{3}$

Analogamente,

$\frac{AC}{AR} = \frac{7}{3}$

Portanto, $PR \parallel BD$ donde segue o resultado.

Afirmação 2: $\triangle BCD \sim \triangle CRZ$
De fato, sendo $BD \parallel RZ$ , então $C\hat{R}Z = B\hat{D}C$ e $\hat{C} = \hat{C}$ (opostos pelo vértice). Assim,

$\frac{BC}{CZ} = \frac{RC}{CD} = 1 \quad \Rightarrow \quad BC = CZ$

ou seja, $C$ é ponto médio de $BZ$ .

63) Prove que existe exatamente uma única terna de números $(n,n+2,n+4)$ no qual os três números são primos.

Resolução: Se $n$ é par, então, então $n + 2$ e $n + 4$ também são. Mas apenas o $2$ é um primo par. Assim, $n$ deve ser ímpar. Nesse caso, $n + 2$ e $n + 4$ também são ímpares.

Afirmação: $n$ , $n + 2$ ou $n + 4$ é divisível por $3$ .
De fato, se $n$ não é divisível por $3$ , então $n = 3k + 1$ ou $n = 3k + 2$ , sendo $k$ natural. Se $n = 3k + 1$ , então $3 \mid n+2$ e se $n = 3k+2$ , então $3 \mid n+4$ . Analogamente, se $n + 2$ não é divisível por $3$ , então $n + 2 = 3k+1$ ou $n + 2 = 3k+2$ . Ambos os casos, $3 \mid n+4$ ou $3 \mid n$ .

A única possibilidade de um número ser divisível por $3$ e primo é que ele seja o próprio $3$ . Assim, $n = 3, n+2 = 5$ e $n+4 = 7$ . Portanto, a terna procurada é $(3,5,7)$ .

Observe que qualquer outra terna da forma $(n,n+2,n+4)$ com n ímpar distinto de $3$ deve conter pela afirmação acima, um número que é múltiplo de $3$ . Logo, a terna $(3,5,7)$ é única.

64) Mostre que

$\int_{0}^{\pi/2}\sqrt{1 + \sin \theta}d\theta = 2$

Resolução: Seja $\theta = \alpha + \pi/2$ . Assim,

$1 + \sin \theta = 1 + \sin(\alpha + \pi/2) = 1 + \cos \alpha = 2\cos^2(\alpha/2)$

Logo,

$\int_{0}^{\pi/2}\sqrt{1 + \sin \theta}d\theta = \int_{-\pi/2}^{0}\sqrt{2\cos^2(\alpha/2)}d\alpha$

$= \sqrt{2}\int_{-\pi/2}^{0}\cos \bigl(\frac{\alpha}{2}\bigr)d\alpha = 2\sqrt{2}\sin\bigl(\frac{\alpha}{2}\bigr) \mid_{-\pi/2}^{0} = 2$

O leitor Sebá enviou a solução do Problema 63.

Participe enviando as soluções dos problemas 65), 66), 67) e 68) no formato doc ou pdf para linnux2001@gmail.com. O prazo de entrega para enviar as soluções destes problemas encerra no dia 10/03/2013.

Gostará de ler também:

-Problemas dos Fatos Matemáticos (Parte 20);
-Problemas dos Fatos Matemáticos (Parte 19).

Páginas

Membros