Experimentar One Stroke grátis no iPhone
Quebra-cabeças infinitos. Dificuldade adaptativa. Sem anúncios forçados.
Como uma simples pergunta sobre uma caminhada de domingo inventou todo um ramo da matemática
No século XVIII, a cidade de Königsberg (atual Kaliningrado, na Rússia) foi construída em ambas as margens do rio Pregel, com duas grandes ilhas no meio. Sete pontes ligavam essas quatro massas de terra.
Os cidadãos tinham uma pergunta simples:É possível caminhar pela cidade, atravessando cada uma das sete pontes exatamente uma vez, sem atravessar nenhuma ponte duas vezes?
Margem Norte (A)
/ | \
b1 b2 b3
/ | \
Ilha | Ilha
(B)----b4----(C)
\ | /
b5 b6 b7
\ | /
Margem Sul (D)
7 pontes conectando 4 massas de terra
Você pode cruzar cada ponte exatamente uma vez?As pessoas tentaram e falharam durante anos. Ninguém conseguiu encontrar uma rota. Mas também ninguém conseguiu provar que isso era impossível – até que um matemático chamado Leonhard Euler aceitou o desafio em 1736.
A genialidade de Euler foi perceber que o layout exato da cidade não importava. O que importava era o estrutura de conexões – quais massas de terra estavam conectadas a quais e por quantas pontes.
Ele eliminou todos os detalhes geográficos e reduziu o problema à sua essência:
A (3 pontes) --- B (5 pontes) | | C (3 pontes) --- D (3 pontes) Cada letra = uma massa de terra (vértice) Cada conexão = uma ponte (borda) Número = quantas pontes tocam aquela massa de terra
Este foi o nascimento do que hoje chamamos de gráfico — um conjunto de vértices (nós) conectados por arestas. Euler acabara de inventar teoria dos grafos.
Euler notou algo crucial sobre o número de pontes que tocam cada massa de terra (o que hoje chamamos de ponte). grau de cada vértice):
Todas as quatro massas de terra têm um número ímpar de pontes. Euler provou que isso torna o problema impossível.
Seu raciocínio: se você anda por uma massa de terra (entrando por uma ponte e saindo por outra), você usa pontes dois de cada vez. Portanto, qualquer massa de terra que não seja o seu ponto inicial ou final deve ter um mesmo número de pontes. Um caminho que atravessa todas as pontes uma vez pode ter no máximo dois vértices de grau ímpar (o início e o fim).
Königsberg tem quatro vértices de grau ímpar. Portanto, não existe solução.
O teorema de Euler nos deu as regras exatas para quando uma travessia de "um golpe" é possível:
Cada jogo de quebra-cabeça de um golpe - incluindo One Stroke - é construído com base nessas regras. Quando o algoritmo de geração processual de One Stroke cria um novo quebra-cabeça, ele usa o teorema de Euler para garantir matematicamente que cada quebra-cabeça tenha pelo menos uma solução.
Quando você joga um quebra-cabeça de um golpe, você está resolvendo o mesmo tipo de problema que Euler resolveu em 1736. Você está fazendo teoria dos grafos - talvez você não saiba disso.
A visão aparentemente simples de Euler sobre pontes lançou todo um campo da matemática. A teoria dos grafos agora é essencial para:
Tudo começou com uma pergunta sobre sete pontes numa cidade prussiana – e um matemático que viu a elegante estrutura escondida por baixo.
É um famoso quebra-cabeça matemático de 1736. A cidade de Königsberg tinha sete pontes ligando duas ilhas e duas áreas continentais. A questão: você consegue andar pela cidade atravessando cada ponte exatamente uma vez? Euler provou que isso era impossível porque todas as quatro massas de terra tinham um número ímpar de pontes.
A solução de Euler é considerada o primeiro teorema da teoria dos grafos - um ramo da matemática agora fundamental para a ciência da computação, análise de redes, roteamento GPS e design de jogos de quebra-cabeça. Todo jogo de quebra-cabeça de um golpe é descendente direto dessa prova de 1736.
Os quebra-cabeças de um golpe fazem a mesma pergunta fundamental das Sete Pontes: você pode percorrer cada caminho exatamente uma vez sem refazer? O teorema de Euler fornece as regras matemáticas para determinar quando isso é possível. Jogos como One Stroke usam essas regras para gerar quebra-cabeças com solução garantida.
Não. Königsberg é agora Kaliningrado, na Rússia. Duas das pontes originais foram destruídas na Segunda Guerra Mundial e outras foram reconstruídas. A cidade moderna tem um layout de ponte diferente - mas a visão matemática que Euler derivou das sete originais permanece atemporal.
Quebra-cabeças infinitos. Dificuldade adaptativa. Sem anúncios forçados.