Problemas

Publicarei aqui alguns problemas interessantes. Quem quiser, podem enviar soluções (digitadas ou escaneadas) para o meu email  (walnermendonca@gmail.com) ou podem até postar nos comentários desta página. Também estão convidados a proporem problemas.

Em cada questão pode aparecer símbolos como ☺ e ☻  indicando a possível dificuldade da questão. Assim, temos

☺ =  não tive dificuldade em resolver;
☺☺ = tive que pensar um pouco para resolvê-la;
☺☺☺ = só consegui resolver com alguma ajuda;
☻ = não resolvi ainda;
☻☻ = não resolvi ainda, mas me disseram que é difícil;
☻☻☻ = não resolvi ainda, mas me disseram que é muito difícil.

1.☺[Geometria] Mostre que todo polígono convexo de área 1 está contido em um retângulo de área 2.

2.☺☺[Teoria dos Grafos] Seja $G$ um grafo simples com $n$ vértices. Suponha que $G$ não contém triângulos. Mostre que $G$ contém no máximo $\frac{n^2}{4}$ arestas. Para cada $n$ par, dê um exemplo de um grafo com $n$ vértice e com exatamente $\frac{n^2}{4}$ arestas.

3.☻☻☻[Revista Eureka, nº35] Denominamos Máquina de Conway o par $C = (e;S)$ formado por uma entrada $e = 2^{a_1}$, $a_1\in\mathbb{N}$, e uma sequência finita $S = (s_i)_{1\leq i \leq n}$ de racionais não nulos, com $s_n \in \mathbb{N}$.

Dada uma máquina de Conway $C$ construímos uma sequência $p_i$ definida por:

1. $p_1 = e$;
2. $p_k = p_{k-1} \cdot s_i$, onde $i$ é o menor número inteiro positivo tal que $p_{k-1} \cdot s_i \in \mathbb{N}$. 

Dizemos que $a\in\mathbb{N}$ é uma saída de $C$ se, e somente se, existe um inteiro positivo $k$ tal que $p_{k} = 2^a$. O conjunto de todas as saídas é denominado conjunto gerado por $C$. 

Exemplo: A máquina de Conway formada pela entrada $2^2$ e pela sequência

$$\frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{14}, \frac{15}{2}, 55$$

gera os números primos.

Mostre que é possível construir uma Máquina de Conway que gere o conjunto dos quadrados perfeitos.

4.☺[Elementar] Um dragão possui 100 cabeças. Um cavaleiro pode cortar 15, 17, 20, ou 5 cabeças, respectivamente, com um golpe da sua espada. Em cada um dos casos, 24, 2, 14, ou 17 novas cabeças surgem no dragão. Se todas as cabeças são cortadas, o dragão morre. Pode o dragão morrer?


5.☺☺ [Geometria] Sejam $r$ e $s$ duas retas concorrentes e $A$ um ponto que não pertence nem a $r$ nem a $s$. Determine os pontos $B$ em $r$ e $C$ em $s$ tais que $ABC$ é um triângulo de perímetro mínimo.

6.☺☺[Álgebra] Para $x$ e $y$ números reais, considere as duas operações $\oplus$ e $\odot$ definidas por

$$x \oplus y = \min\{x,y\}\quad \text{ e } \quad x\odot y = x + y.$$
Também incluímos $\infty$ no nosso conjunto, e ele satisfaz $x \oplus \infty = x$ e $x \odot \infty = \infty$, para todo $x$. Quando não especificado, $\odot$ precede $\oplus$ na ordem das operações. Denotamos por $x^{\underline{n}} = x \odot x \odot \cdots \odot x$, com $x$ aparecendo $n$ vezes. Por polinômio tropical, nos referimos a uma função da forma
$$p(x) = a_0 \oplus a_1\odot x \oplus a_2\odot x^{\underline{2}}\oplus \cdots \oplus a_n\odot x^{\underline{n}}, \quad a_n \neq \infty.$$
Prove que vale o Teorema Fundamental da Álgebra: dado $p(x)$ um polinômio tropical de grau $n$, com $a_n\neq \infty$, existem $r_1,r_2,\ldots,r_n \in \mathbb{R}\cup\{\infty\}$ tais que
$$p(x) = a_n \odot (x \oplus r_1) \odot (x \oplus r_2) \odot \cdots \odot (x \oplus r_n),$$
para todo $x$.


7.☺☺[Teoria dos Números] Seja $f$ uma função que a cada número inteiro positivo $q$ associa um número real positivo $f(q)$. Suponha que
$$\sum_{q=1}^{\infty} f(q) < \infty.$$
Mostre que para quase todo número $\alpha$, a desigualdade
$$\left| \alpha - \frac{p}{q} \right| <\frac{f(q)}{q}$$
contém apenas um número finito de soluções racionais $p/q$.

[Durante uma palestra do professor Gugu (IMPA) na UFC, foi mencionado o teorema de Khintchine. Tal teorema trata de uma espécie de dicotomia a respeito da convergência da série mencionada no problema. Se a série converge, então para quase todo número $\alpha$ a desigualdade acima possui apenas um número finito de soluções. Se, por outro lado, a série diverge, então para quase todo número $\alpha$ a desigualdade acima possui um número infinito de soluções. Na ocasião, a hipótese que $qf(q)$ seja decrescente foi considerada como fundamental para a parte em que a série diverge, mas desnecessária para a parte em que a série converge. A parte em que a série converge foi deixada pelo profº Gugu como exercício. E este é o problema acima.]

8.☺☺☺[Análise]  Sejam $a,b,c>0$. Mostre que
$$\frac{a + \sqrt{ab} + \sqrt[3]{abc}}{3} \leq \sqrt[3]{a \cdot \frac{a+b}{2} \cdot \frac{a+b+c}{3}}.$$

9.☺☺[Análise] Exiba um compacto $K\subseteq \mathbb{R}$ tal que $K + K = \{x+y\;|\; x\in K, y \in K\}$ tenha medida nula e $K - K = \{x-y\;|\; x\in K, y \in K\}$ seja um intervalo não degenerado.