Ronald
Kyrmse
kyrmse@yahoo.com.br
COMUNICAÇÃO
DE WALDIR QUANDT SOBRE POLÍGONOS CANÔNICOS — 16Nov1999
[Editado por
RK]
TEOREMA: Se um PC é convexo,
tem no máximo oito lados.
Dem.: A soma (das medidas)
dos ângulos internos de um polígono convexo de n lados (PC
ou não) é (n - 2) pi. Para um PC, o valor máximo
dessa soma é n (3pi / 4); daí:
3n (pi / 4) >= (n
- 2) pi
3n >= 4n -
8
n <= 8
.
COROLÁRIO: Só
há dez possíveis configurações angulares para
um PC convexo.
Dem.: Num PC convexo de
n
lados, sejam x o número de ângulos internos de medida
pi/4, y o número de ângulos internos de medida pi/2
e z o … 3pi/4. Então
x (pi / 4) + y
(pi / 2) + z (3pi / 4) = (n - 2) pi, e daí temos
x + y + z
= n
x + 2y + 3z
= 4n - 8
3 <= n <= 8
(do teor. anterior)
Esse sistema tem exatamente
dez soluções, a saber:
|
n
|
x
|
y
|
z
|
|
3
|
2
|
1
|
0
|
|
4
|
0
|
4
|
0
|
|
4
|
1
|
2
|
1
|
|
4
|
2
|
0
|
2
|
|
5
|
0
|
3
|
2
|
|
5
|
1
|
1
|
3
|
|
6
|
1
|
0
|
5
|
|
6
|
0
|
2
|
4
|
|
7
|
0
|
1
|
6
|
|
8
|
0
|
0
|
8
|
.
Agora a análise de
cada caso […] elimina os indesejáveis e conduz aos oito PCs conhecidos.
O interessante é que, como no teor. das quatro cores, tem-se o resultado
sem que ele tenha uma conexão lógica com algum fato conhecido
anteriormente…
[...]
Um detalhe: como se obtém
[FA 33333333] ou [FA 333333] ou [FA 53225322] por
recorrência?
[...]
Obs. que nem mesmo
para n ímpar se conseguem todos por recorrência (é
preciso usar dualidade ou rebatimento [...]) [Esta observação
de WQ parece implicar que o processo recursivo não gera todos os
PCs]
[Uma maneira de construir
PCs]
Cada PC é uma seqüência
de n objetos do conjunto {1, -1, i, -i, 1+i, 1-i, -1+i, -1-i}, sujeita
a algumas restrições, como:
-
a soma da seqüência
é zero (é um circuito fechado)
-
a soma de qualquer “fragmento”
da seqüência não é nula (o circuito não
fecha com menos de n etapas)
-
dois elementos consecutivos
não são iguais nem diferem só pelo sinal
-
não é permitido
o grupamento …, 1+i, -i, -1+i, … […]
(“fragmento” é um grupamento
de termos consecutivos)
É claro que duas seqüências
são equivalentes se:
a) diferem só na
ordem de leitura
b) diferem só na
escolha do 1º termo (são lidas ciclicamente)
Além disso, duas seqüências
são equivalentes se uma puder ser obtida da outra por uma ou mais
das seguintes operações:
-
multiplicação
por 1, por -1, por i, ou por -i
-
conjugação
Ex.: [figuras eliminadas]
(1 + i, 1, -1 + i, -1
- i, -i) -> [x i] -> (-1 + i, i, -1 - ii, 1 - i, 1)
-> [conjugado] -> (-1 -
i, -i, -1 + i, 1 + i, 1) -> [x -1] -> (1 + i, i, 1 - i, -1 - i, -1)
Uma seqüência
é equivalente a si mesma; se duas seqüências são
equivalentes a uma terceira, o são entre si; se a seq. A é
equivalente à B, B é equivalente a A.
Destarte, um PC é
a classe de equivalência de uma seqüência, i. e.,
o conjunto das seqüências equivalentes. Para desenhar um PC
basta tomar um representante da classe.
Dois PCs são duais
se uma seqüência representante de um deles puder ser convertida
numa seqüência representante do outro através das seguintes
substituições:
|
substitua
|
->
|
por
|
|
1
|
|
1+i
|
|
-1
|
|
-1-i
|
|
i
|
|
-1+i
|
|
-i
|
|
1-i
|
|
1+i
|
|
i
|
|
-1-i
|
|
-i
|
|
-1+i
|
|
-1
|
|
1-i
|
|
1
|
|
por
|
<-
|
substitua
|
[…]
Obviamente a auto-dualidade
é apenas uma reflexão e/ou rotação; o dual
do dual é o mesmo caso.
Agora, mãos à
obra: um bom programador pode fazer um programa de geração
de seqüências adequado (creio que Pascal ou C++ dão
conta do recado). “Basta” usar espertamente os recursos mais sofisticados
para eliminar equivalências. Uma observação óbvia
mas útil: o perímetro de uma seqüência (a1,a2,…,an)
é Somatóriaj=1…n|aj|
e seqüências de perímetros distintos não são
equivalentes.
Também o óbvio:
sempre se pode tomar a1 = 1 e a2 =
1+i [nota de rodapé: ou a1 = 1 e a2
= i].
[…]
Veja como é fácil
determinar o diâmetro: dada uma seqüência (a1,a2,…,an),
construa a seq. associada (b1,b2,…,bn)
fazendo b1 = 0, bj = bj-1
+ aj-1 (2 <= j <= n).
Calcule as n (n - 1) / 2 diferenças bj
- bk, 1 <= j <= n-1, j+1 <=
k
<= n. O maior dos números |bj - bk|
é o diâmetro.
[Adendo de 23Nov1999]
1) É claro que todo PC
auto-dual tem número par de lados: se n(o) é o número
de lados ortogonais e n(d) o de diagonais, o dual tem n(d)
lados ortogonais e n(o) lados diagonais. Como é auto-dual,
n(d)
= n(o), e o número de lados é 2n(o).
2) Dado um PC A por uma
de suas seqüências (a1,a2,…,an),
considere a seqüência associada (A1,A2,…,An)
(lembrando que A1 = 0). Defina H(A) = max {Re(Aj);
j
= 1, 2, …, n} - min{Re(Ak); k = 1, 2, …,
n}
e V(A) = max {Im(Aj); j = 1, 2, …, n} -
min{Im(Ak); k = 1, 2, …,
n}. O índice
de quadratura é Iq = min{H(A), V(A)} / max{H(A), V(A)}.
Quanto mais próximo de 1 for esse índice, mais “próximo”
de um quadrado está A. O índice de convexidade é Ic
= Área(A) / (H(A).V(A)). Quanto mais próximo de 1 for esse
índice, “mais convexo” é A. Palpite: à medida que
n
aumenta, os valores médios de Iq e de Ic (calculados
para os PCs de n lados) tendem a 1/2.
wquandt@mtm.ufsc.br
COMMUNICATION
BY WALDIR QUANDT ON CANONICAL POLYGONS— 16Nov1999
[Edited by
RK]
THEOREM: If a CP is convex it
has at most eight sides.
Proof: The sum (of the measures)
of the internal angles of a convex polygon with n sides (CP or not)
is (n - 2) pi. For a CP, the maximum value of this sum is n
(3pi / 4); therefore:
3n (pi / 4) >= (n
- 2) pi
3n >= 4n -
8
n <= 8
.
COROLLARY: There are only
ten possible angular configurations for a convex CP.
Proof: In a convex CP with
n sides, let x be the number of internal angles with measure pi/4,
y
the number of internal angles with measure pi/2 and z the … 3pi/4.
Then
x (pi / 4) + y
(pi / 2) + z (3pi / 4) = (n - 2) pi, so we have
x + y + z
= n
x + 2y + 3z
= 4n - 8
3 <= n <= 8
(from the previous theorem)
This system has exactly
ten solutions, namely:
|
n
|
x
|
y
|
z
|
|
3
|
2
|
1
|
0
|
|
4
|
0
|
4
|
0
|
|
4
|
1
|
2
|
1
|
|
4
|
2
|
0
|
2
|
|
5
|
0
|
3
|
2
|
|
5
|
1
|
1
|
3
|
|
6
|
1
|
0
|
5
|
|
6
|
0
|
2
|
4
|
|
7
|
0
|
1
|
6
|
|
8
|
0
|
0
|
8
|
.
Now the analysis of each
case […] eliminates the undesirable ones and leads to the eight known CPs.
What is interesting is that, as in the four-colour theorem, the result
arises without there being a logical connection with any previously known
fact…
[...]
One detail: how does one
obtain [FA 33333333] or [FA 333333] or [FA 53225322]
through recurrence?
[...]
Observe that not even for
odd n all may be obtained through recurrence (it is necessary to
use duality or flipping [...]) [This remark by WQ seems to imply that the
recursive process does not generate all CPs]
[A way of constructing CPs]
Each CP is a sequence of n objects
from the set {1, -1, i, -i, 1+i, 1-i, -1+i, -1-i}, subject to some restrictions,
such as:
-
the sum of the sequence is zero
(it is a closed circuit)
-
the sum of any “fragment” of
the sequence is non-zero (the circuit does not close in less than n
steps)
-
two consecutive elements neither
are equal nor differ only in sign
-
the grouping …, 1+i, -i, -1+i,
… is not allowed […]
(“fragment” is a grouping of
consecutive terms)
Clearly two sequences are
equivalent if:
a) they differ only in order
of reading
b) they differ only in choice
of 1st term (are read cyclically)
Furthermore two sequences are
equivalent if one can be obtained from the other through one or more among
the following operations:
-
multiplication by 1, by -1,
by i or by -i
-
conjugation
Ex.: [drawings deleted]
(1 + i, 1, -1 + i, -1
- i, -i) -> [x i] -> (-1 + i, i, -1 - ii, 1 - i, 1)
-> [conjugate] -> (-1 -
i, -i, -1 + i, 1 + i, 1) -> [x -1] -> (1 + i, i, 1 - i, -1 - i, -1)
A sequence is equivalent
to itself; if two sequences are equivalent to a third, they are so between
themselves; if sequence A is equivalent to B, B is equivalent to A.
Thus a CP is the equivalence
class of a sequence, i. e., the set of equivalent sequences. To
draw a CP it suffices to take a representative of the class.
Two CPs are dual if a representative
sequence of one can be converted into a representative sequence of the
other through the following substitutions:
|
substitute
|
->
|
by
|
|
1
|
|
1+i
|
|
-1
|
|
-1-i
|
|
i
|
|
-1+i
|
|
-i
|
|
1-i
|
|
1+i
|
|
i
|
|
-1-i
|
|
-i
|
|
-1+i
|
|
-1
|
|
1-i
|
|
1
|
|
by
|
<-
|
substitute
|
[…]
Obviously auto-duality is
only a reflection and/or rotation; the dual of the dual is the same case.
Now for some work: a good
programmer will be able to set up an adequate sequence-generating program
(I believe Pascal or C++ will do). It is “enough” to use advisedly
the most sophisticated resources to eliminate equivalencies. An obvious
but useful remark: the perimeter of a sequence (a1,a2,…,an)
is Sumj=1…n|aj| and sequences
of unequal perimeters are not equivalent.
Also obvious: one may always
take a1 = 1 and a2 = 1+i [footnote:
or a1 = 1 and a2 = i].
[…]
See how easy it is to determine
the diameter: given a sequence (a1,a2,…,an),
construct the associated sequence (b1,b2,…,bn)
making b1 = 0, bj = bj-1
+ aj-1 (2 <= j <= n).
Calculate the n (n - 1) / 2 differences bj
- bk, 1 <= j <= n-1, j+1 <=
k
<= n. The largest among the numbers |bj - bk|
is the diameter.
[Addendum of 23Nov1999]
1) It is clear that every auto-dual
CP has an even number of sides: if n(o) is the number of orthogonal
sides and n(d) that of diagonal sides, the dual has n(d)
orthogonal sides and n(o) diagonal sides. As it is auto-dual, n(d)
= n(o), and the number of sides is 2n(o).
2) Given a CP A by one of
its sequences (a1,a2,…,an),
consider the associated sequence (A1,A2,…,An)
(remembering that A1 = 0). Define H(A) = max {Re(Aj);
j
= 1, 2, …, n} - min{Re(Ak); k = 1, 2, …,
n}
and V(A) = max {Im(Aj); j = 1, 2, …,
n}
- min{Im(Ak); k = 1, 2, …,
n}. The index
of quadrature is Iq = min{ H(A), V(A)} / max{ H(A), V(A)}. The
nearer to 1 this index is, the “nearer” to a square will A be. The index
of convexity is Ic = Area(A) / (H(A).V(A)). The nearer to 1
this index is, the “more convex” is A. Guess: with increasing
n,
the average values of Iq and Ic (calculated for CPs
of n sides) tend towards 1/2.
wquandt@mtm.ufsc.br
HOME