ajuda

["Luis Lopes" <llopes@xxxxxxxxxxxxx>]

Oi Filho,

Segue a solução do prof. Rousseau para o problema

Um quadrilátero tem um vértice em cada lado de um quadrado unitário. Mostre
que os comprimentos a,b,c e d do quadrilátero satisfazem as desigualdades: 2
<= a ^ 2 + b ^ 2 + c ^ 2 + d ^ 2 <= 4 .

e também aquela do problema abaixo.

[ ]'s
Luís

-----Mensagem Original-----
De: Filho
Para: discussão de problemas
Enviada em: Quarta-feira, 6 de Setembro de 2000 22:06
Assunto: ajuda


Qual é o menor número de retas que se devem traçar em um plano de
modo a obter n pontos de interseção ?

===
Dear Luis:

   By the Pythagorean Theorem, the expression a^2 + b^2 + c^2 + d^2
can be written as the sum of eight squares, and these 8 squares can be
grouped into four pairs of the form x^2 + y^2 where x + y = 1.
>From
                        (x+y)^2 = x^2 + y^2 + 2xy
                        (x-y)^2 = x^2 + y^2 - 2xy
we have
                  1 \leq  (x+y)^2 + (x-y)^2 = 2(x^2 + y^2),
so
                               x^2 + y^2 \geq 1/2.
Adding four such terms, we have the lower bound.   This is achieved
by selecting the four vertices of the inscribed quadrilateral to be the
midpoints of the sides of the square.  For the upper  bound, just observe
that x^2 + y^2 = x^2 + (1-x)^2 = 2x^2 - 2x + 1
is convex, so its maximum value is achieved at an endpoint (x = 0
or x = 1); thus x^2 + y^2 \leq 1.  Adding four such terms gives the
upper bound.  This is achieved by selecting the vertices of the
inscribed quadrilateral to be the same as the vertices of the square.
                                       x                      y
                                xxxxxxxxxxxxxxxxxxxxxxxx
                                x              x                       x
                                x                   x                  x
                                x                        x             x
                                x                     a        x      x
                                x                                     xx
                                x                                       x
                                xxxxxxxxxxxxxxxxxxxxxxxx


If there are k lines, there are at most k(k-1)/2 intersection points since
there that many pairs of lines and each pair contributes one intersection
point if nonparallel and 0 if parallel.  Thus we want the smallest k such
that k(k-1)/2 \geq n.  This gives

                    k \geq \lceil \frac{1 + \sqrt{8n + 1}}{2} \rceil.

I think that both of these are right, but you should check carefully.

Cecil
===

OBS.:  o resultado acima está escrito em TeX. \lceil x \rceil representa
a função ceiling ou teto. É o menor inteiro >= x .
\frac{x}{y} representa a fração x/y.

Pode-se ler sobre as funções floor (piso) e ceiling (teto) nos livros do
Knuth e no livro sobre Logaritmos que escrevi (característica e mantissa).