| Fórum de Matemática | DÚVIDAS? Nós respondemos! https://forumdematematica.org/ |
|
| ∆∊∫afi∅s https://forumdematematica.org/viewtopic.php?f=23&t=2145 |
Página 1 de 1 |
| Autor: | Lucas de Alkmim [ 31 mar 2013, 12:42 ] |
| Título da Pergunta: | ∆∊∫afi∅s [resolvida] |
Desafio 4: 50 pontos são marcados em uma folha de papel. É sempre possível construir uma reta que separa os pontos em dois grupos de 25 pontos cada? |
|
| Autor: | Sobolev [ 02 abr 2013, 12:33 ] |
| Título da Pergunta: | Re: ∆∊∫afi∅s |
Sim, é sempre possível. Apesar de existirem algoritmos determinísticos para resolver este problema ( com complexidade O(n) ou O(n log n) ), uma forma simples de encontrar a recta que divide o conjunto de pontos é a seguinte: 1. Escolher uma recta ao acaso (podem ser usados alguns critérios baseados nas médias ou medianas das coordenadas dos pontos mas não é muito relevante) 2. Projectar todos os pontos sobre essa recta. 3. Ordenar as projeções e escolher um ponto Q da recta que divida em duas partes iguais os pontos projectados. (isto pode nem sempre ser possível devido à possibilidade de diversos pontos terem a mesma projecção). 4. A recta perpendicular à recta inicial que passa no ponto Q tem igual número de pontos de cada lado. Naturalmente, se o passo 3 não for possível deve ser escolhida outra recta. |
|
| Autor: | Rui Carpentier [ 02 abr 2013, 13:57 ] |
| Título da Pergunta: | Re: ∆∊∫afi∅s |
Uma outra maneira de chegar à solução é a seguinte: 1) Escolha-se um ponto P que não seja colinear com qualquer par dos 50 pontos dados; 2) Toma-se uma reta que passe pelo ponto P e não passe por nenhum dos 50 pontos; 3) Escolhe-se uma orientação para a reta, e seja E(0) o nº de pontos à esquerda da reta (na orientação escolhida) e D(0) o nº de pontos à esquerda da reta; 4) Vai-se rodando a reta continuamente e para cada ângulo \(\alpha\) seja \(E(\alpha)\) o nº de pontos à esquerda da reta e \(D(\alpha)\) o nº de pontos à esquerda da reta; Temos então que, para \(\alpha=180^o\), \(E(\alpha)=D(0)\) e \(D(\alpha)=E(0)\). E como \(E(\alpha)\) e \(D(\alpha)\) variam em + ou - 1 à medida que variamos \(\alpha\) (é aqui que é importante o facto de P não ser colinear com 2 ou mais pontos) temos que haverá um ângulo \(\alpha\) entre 0 e 180º tal que \(E(\alpha)=D(\alpha)=25\). |
|
| Autor: | Lucas de Alkmim [ 02 abr 2013, 15:15 ] |
| Título da Pergunta: | Re: ∆∊∫afi∅s |
obrigado, caras. |
|
| Página 1 de 1 | Os Horários são TMG [ DST ] |
| Powered by phpBB® Forum Software © phpBB Group https://www.phpbb.com/ |
|