Desafios especiais

Desafio 1: Roberto recebe três retas não paralelas distintas  e um círculo ω no plano. Além de uma régua normal, Roberto tem uma régua especial que, dada uma reta  e um ponto P, constrói uma nova reta que passa por  P  paralela a . (Roberto não tem um compasso.) Mostre que Roberto pode construir um triângulo com um circulo ω cujos lados são paralelos a   em alguma ordem.

Desafio 2: Vinte formigas vivem nas faces de um icosaedro, uma formiga de cada lado, onde o icosaedro tem cada lado com comprimento 1. Cada formiga se move no sentido anti-horário de cada face, ao longo dos lados/bordas. A velocidade de cada formiga não deve ser inferior a 1 sempre. Além disso, se duas formigas se encontrarem, elas devem se encontrar no vértice do icosaedro. Se cinco formigas se encontram ao mesmo tempo em um vértice, chamamos isso de 'colisão'. As formigas podem se mover para sempre, de maneira que não ocorra colisão? Justifique!
-----------------------------------------------------------------------------------------------------------------------------------
                                       
Após concluir um desafio, me mande uma mensagem como toque! Dê a dica de sua solução para que eu possa enviar algo a entrar em contato comigo.

O desafio será aceito por um limite de pessoas [não será exposto aqui]. Caso alguém envie a solução aqui, o prêmio será cancelado para todos os participantes que ainda não responderam os desafios propostos.

Aviso: o prêmio será destinado apenas para olimpistas dedicados.

Desafio 1:


                           

Lema: Dado qualquer segmento XY, podemos construir seu ponto médio.

Prova: XY pode ser paralelo a, no máximo, um dos lados de ΔABC. Suponha que, sem perda de generalidade, não seja paralelo a AB, AC. Deixe as paralelas X, Y a AB, AC se encontrarem em Z, enquanto as paralelas de  X, Y a  AC, AB  se encontrem em W. Claramente, ZXWY é um paralelogramo. Portanto, ZW ∩ XY  fornece o ponto médio de  XY.

Agora, damos uma notação:

• Trace uma reta arbitrária paralela a BC, chame de EF, de modo que  E, F ∈ ω. 
  
• Seja K, L ∈ ω pontos tais que KE||AB, LF||CA. Seja  KE ∩ LF = P. 
  
• Construa o ponto médio M de KL como no lema.
  
• Trace uma paralela de KL a F, e deixe-a encontrar ω novamente em  G. Seja N o ponto médio de FG. Construa N como no lema.
  
• Deixe MN cruzar o arco EKLF de ω a X. 
  
• Desenhe X nas retas paralelas a AB, AC e deixe-as encontrar ω em Y, Z, respectivamente. Afirmamos que XYZ é o triângulo desejado.
  

Agora
                                                         

Feito!

Desafio 2:

Primeira observação: se mais de duas formigas se encontrarem em um vértice, mas não todas as cinco, elas deverão ser capazes de acelerar/desacelerar de modo que realmente não se encontrem. Portanto, a questão é equivalente a saber se é possível que nenhuma formiga se encontre.


Segunda observação: podemos apenas marcar de que lado a formiga está atualmente. Se as formigas não se encontrarem, não haverá duas formigas do mesmo lado, e podemos acelerar/desacelerar arbitrariamente as formigas para que cada formiga passe por um vértice exatamente quando quisermos. Os dados de uma "configuração de formigas" são a escolha de uma aresta para cada uma das faces, nenhuma aresta é escolhida duas vezes e as formigas que se movimentam podem ser interpretadas como a seguinte "operação": para uma face σ, se a aresta  e' ∈ ∂σ ao lado (no sentido anti-horário) da aresta escolhida e ∈ ∂σ não for escolhida pela face adjacente a σ contendo e' , mudamos para a margem escolhida de σ de  e  para  e'.


Terceira observação: se for verdade que as formigas não podem se mover para sempre, deve haver um invariante que é monótona com o passar do tempo. Portanto, existe um exemplo de uma sequência dessas operações ou há uma invariante monótona.

Bem, acontece que existe uma invariante. Aqui está uma construção. Para uma configuração, considere o grafo direcionado  G  que tem vértices os centros das faces {σ_1,..., σ_ {20}} e uma aresta de cada σ_i  a σ_ {f (i)} se as duas faces estiverem adjacentes uma com a aresta comum e, de modo que  e  seja a aresta escolhida de σ_i. Portanto, este é um grafo tal que cada vértice (ou face do icosaedro) tem um grau superior 1. Por esse motivo, existem ciclos neste grafo. Lembre-se de que estamos trabalhando em um icosaedro, nosso caminho pode ser pensado como um caminho no icosaedro. Assim, um ciclo  C  divide o icosaedro em duas partes, uma delas de modo que o caminho esteja no sentido anti-horário no limite e a outra de modo que o caminho seja no sentido horário no limite.

Para cada ciclo C, denote por C° a região de modo que  C  esteja no sentido anti-horário em relação a  C°. Digamos que C  seja mínimo se  C° não contiver outros ciclos e máximo se o complemento de  C° estiver livre de ciclo. (Um ciclo é máximo e mínimo, se e somente se for o único ciclo.) Vamos focar apenas em ciclos mínimos ou máximos. Além disso, denote por vol(C)  o número de vértices (do icosaedro) que estão em  C°. (Se você estiver olhando para o dual do icosaedro, este é o número de pentágonos na região.)

Vamos analisar quando os ciclos mínimo/máximo aparecem ou desaparecem. Observe que sempre que fazemos uma operação, no máximo um ciclo desaparece e, no máximo, um ciclo aparece. Aqui está o resultado:

(1) Quando movemos uma aresta que não faz parte de um ciclo mínimo/máximo, mas um novo ciclo aparece, o novo ciclo não pode ser máximo. Observe que é possível que alguns ciclos mínimos/máximos não sejam mais mínimos/máximos devido à introdução de um novo ciclo.
(2) Quando movemos uma aresta que faz parte de um ciclo mínimo/máximo, (i) o ciclo original é removido e nenhum ciclo mínimo/máximo aparece, ou (ii) há um novo ciclo mínimo/máximo estritamente menor volume.
(3) Em (2), se movermos uma aresta que faz parte de um ciclo mínimo, sempre haverá um novo ciclo, e esse novo ciclo será mínimo.

Prova: 1) Quando movemos uma aresta que não faz parte de um ciclo mínimo/máximo para a próxima aresta e um novo ciclo é exibido. Eu afirmo que este não pode ser um ciclo máximo. Suponha que o novo ciclo C = v_0 →...→ v_ {n-1} → v_0  seja o novo ciclo, onde alteramos v_0 → w → v_0 → v_1. Nesse caso,  v_0 → w deve estar apontando para o complemento de C°. Depois, seguir o caminho  v_0 → w → ... deveria ter nos dado um ciclo B, antes de efetuado a operação. Existem dois casos possíveis: (i) B: v_0 → w → ... → v_0 contém  v_0  ou (ii) B é disjunto de  C. (i) Se  B  continha  v_0, o ciclo teria se parecido com


                                                 

Pela nossa suposição, B não deve ser máximo/mínimo e, portanto, deve haver um ciclo em ambos os lados de  B. Nesse caso, quando fazemos a operação e formamos C, esses dois ciclos ainda permanecem em ambos os lados de C e, portanto, C não é mínimo nem máximo. (ii) Se  B é completamente disjunto de  C, ele está contido no complemento de C°. Mas, depois de alterar v_0 → w → v_0 → v_1, vemos que B ainda é um ciclo, contido no complemento de  C°. Portanto, o novo ciclo C não pode ser máximo.

(2) Quando movemos uma aresta que faz parte de um ciclo mínimo/máximo. Claramente, esse ciclo será destruído, mas existe a possibilidade de um novo ciclo mínimo/máximo aparecer. Suponha que o ciclo original C desapareça e um novo ciclo C' apareça. Se C: v_0 → ... → v_ {n-1} → v_0  fosse o ciclo original, e movemos v_0 → v_1  para v_0 → w, então v_0 → w deve estar em  C°. Como existe um novo ciclo C', a nova borda v_0 → w → ... deve fazer parte de C' e, portanto, C' deve estar em C°. Portanto, (C') ^ ° ⊂ C°, portanto vol(C)>vol(C'). Em outras palavras, um ciclo desaparece ou é substituído por um ciclo com volume menor.

(3) Em (2), suponha que movemos uma aresta que faz parte de um ciclo mínimo. Aqui, eu afirmo que um novo ciclo sempre será criado e sempre será mínimo. Isso é bastante simples de ver. Se C: v_0 → ... → v_ {n-1} → v_0 fosse o ciclo original, e movemos  v_0 → v_1 →  v_0 → w, então  v_0 → w deve estar em  C°. Então v_0 → w→ ... agora será um ciclo mínimo.

Depois de todo esse trabalho, deixe-me escrever o invariante. Considere primeiro

                                                                       

Em (1), os ciclos máximos não podem surgir se a operação não estiver em ciclos mínimos/máximos. Em (2), se fizermos a operação em um ciclo máximo para obter outro ciclo, apenas obteremos um ciclo de volume menor. Por (3), se fizermos a operação em um ciclo mínimo, obteremos um ciclo mínimo. Isso implica que, se fizermos a operação em um ciclo não máximo, podemos esperar apenas obter um ciclo não máximo. Portanto, X_1 nunca pode aumentar. Além disso, ele deve diminuir estritamente sempre que fazemos uma operação em um ciclo máximo. Isso mostra que X_1  deve diminuir para  0 se as formigas se moverem infinitamente.

Isso mostra que, eventualmente, não haverá ciclos máximos. Observe que sempre haverá ciclos em um grafo com grau superior 1 e, em seguida, sempre haverá um ciclo máximo ou mínimo. Isso mostra que existe pelo menos um ciclo mínimo. Agora considere

                                                                       

Em (1), novos ciclos mínimos podem surgir, mas isso apenas diminui X_2. Por (2) e (3), se removermos um ciclo mínimo, ele dará origem a um ciclo mínimo com volume menor. Isso mostra que X_2 nunca aumenta e deve diminuir estritamente sempre que fazemos uma operação em um ciclo mínimo de volume mínimo. Isso contradiz X_2 ≥ 0.

Observe que esse argumento funciona para qualquer grafo planar (embutido em S ^ 2).

Feito!