Cássio
Membro Iniciante
Posts: 23 
|
Post by Cássio on Jan 6, 2015 10:46:16 GMT -3
Esse problema é do livro do Elon. Tenho uma solução legal, mas achei um pouco técnica. Queria ver algo mais 'free'  Seja $X \subset \mathbb R^n$ tal que a métrica euclidiana induz em $X$ a métrica zero-um. Prove que $X$ tem no máximo $n+1$ elementos. |
|
|
|
Post by joaomarcos on Jan 6, 2015 21:36:53 GMT -3
Eu consegui resolver provando esse resultado "Seja $X$ um espaço vetorial sobre $\mathbb{R}$ com produto interno e $A \subset X$, um conjunto com n elementos com a propriedade $<a_i,a_i>=1$ para $1\leq i \leq n$ e $<a_i-a_j,a_i-a_j> =1$ para $i\neq j$ então A é L.I." Demonstração: Seja $i \neq j$, $<a_i-a_j,a_i-a_j> =<a_i,a_i>-2<a_i,a_j>+<a_j,a_j>=1$, assim temos que, $<a_i,a_j>=\frac{1}{2}$. Sejam $c_1, c_2, ..., c_n$ constantes reais tais que, $c_1a_1+ c_2a_2+ ...+ c_na_n=0$, desse modo $-c_ia_i=c_1a_1+...+c_{i-1}a_{i-1}+c_{i+1}a_{i+1}+...+ c_na_n$ e então $-c_i=\frac{1}{2}(c_1+...+c_{i-1}+c_{i+1}+...+c_n) \Rightarrow c_1+...+c_{i-1}+c_{i+1}+...+c_n=-2c_i \Rightarrow c_1+...+c_n=-c_i$ para todo i, assim, $c_1=c_2=...=c_n$, e então temos $-c_i=nc_i$ segue que $c_i=0$, logo A é L.I. A solução que você tem usou esse resultado? |
|
|
|
Post by Walner Mendonça on Jan 7, 2015 2:33:17 GMT -3
Bom, esse problema apareceu um dia desses no grupo do FM no facebook. Só que foi enunciado de uma maneira diferente, mas equivalente. Vou adaptar a minha solução para o atual contexto. O ponto é que dizer que $X\subseteq \mathbb{R}^n$ é tal que a métrica euclidiana induz em $X$ a métrica zero-um é a mesma coisa que dizer que a distância euclidiana entre pontos distintos de $X$ é 1. Um subconjunto $X\subseteq \mathbb{R}^n$ desse tipo vou chamar de configuração boa. Primeiro, vamos mostrar que o número máximo de pontos numa configuração boa em $\mathbb{R}^n$ contida numa esfera $k$-dimensional é no máximo $k+1$. Por indução. $k=1$ é fácil. Suponha que vale para $k-1$, $k>1$. Provemos que vale para $k$. Suponha, por absurdo, que exista $k+2$ pontos formando uma configuração boa contida numa esfera $k$-dimensional $S$. Tome um ponto $P$ dentre esses $k+2$ pontos. Seja $S(P)$ a esfera unitária centrada em $P$. Os $k+1$ pontos restantes deverão estar na interseção de $S$ com $S(P)$. Mas esta interseção é uma esfera $(k-1)$-dimensional. Portanto os $k+1$ pontos formam uma configuração boa contida numa esfera $(k-1)$-dimensional. O que contradiz a hipótese de indução. Com isso, podemos mostrar que o número de pontos numa configuração em $\mathbb{R}^n$ é no máximo $n+1$. O caso $n =1$, é fácil. Suponha, então, $n>1$. Por absurdo, suponha que há uma configuração boa com $n+2$ pontos em $\mathbb{R}^n$. Pegue um ponto $P$. Os $n+1$ pontos restantes formam uma configuração boa em $\mathbb{R}^n$ contida na esfera $S(P)$, cuja a dimensão é $n-1$. Pela o que fizemos no parágrafo acima, o número máximo de uma configuração boa contida em $S(P)$ é $n$. Contradição. Logo o número máximo de pontos numa configuração boa em $\mathbb{R}^n$ é $n+1$. |
|
Cássio
Membro Iniciante
Posts: 23
|
Post by Cássio on Jan 7, 2015 7:22:39 GMT -3
João, eu usei isso mesmo que você postou, mas o que achei complicado foi como construir um exemplo em $\mathbb R^n$ com $n+1$ pontos. Vocês chegaram a pensar nisso?
|
|
|
|
Post by joaomarcos on Jan 7, 2015 11:30:21 GMT -3
Cássio, eu acho que não é necessário construir o exemplo.
|
|
Cássio
Membro Iniciante
Posts: 23
|
Post by Cássio on Jan 9, 2015 7:43:26 GMT -3
Precisar não precisa, mas eu gostaria de ver kkkkk
Bom, mas consegui de um jeito melhor. Na verdade, eu achei umas anotações de quando fiz a matéria e eu tinha feito esse
Considere a matriz $n \times n$: $$ G = \frac{1}{2} \begin{pmatrix} 2 & 1 & \cdots & 1 \\ 1 & 2 & \cdots & 1 \\ \vdots & \vdots & \ddots & \vdots \\ 1 & 1 & \cdots & 2 \end{pmatrix} $$
Ou seja, $G_{ii} = 1$ e $G_{ij} = \dfrac{1}{2}$ se $i \neq j$. $G$ é simétrica, e definida positiva, então podemos escrever $G = PDP^t$. Tomando $A = P \sqrt{D}$, teremos $G = AA^t$. Então tomamos $x_i = A_{i1}e_1 + A_{i2}e_2+ \cdots + A_{in}e_n$ a $i$-ésima linha de $A$. Dessa forma, a distância entre dois elementos distintos do conjunto $\{ x_0, x_1, \dots, x_n \}$ é $1$, sendo $x_0 = 0$. De fato, $\langle x_i,x_j \rangle = G_{ij}$. Daí, $\| x_i \|^2 = G_{ii} = 1 $ e $\| x_i - x_j \|^2 = G_{ii} - G_{ij} - G_{ji} + G_{jj} = 1$
|
|
