Tip:
Highlight text to annotate it
X
JAMES GRIME: Certo.
Vamos falar sobre números nas notícias, porque
recentemente, o número 17 apareceu nas notícias.
Esta é para os fãs de Sudoku, porque foi recentemente provado
por um homem chamado Gary McGuire, que é um
matemático da Universidade de Dublin, provou que
um Sudoku precisa de pelo menos 17 pistas para ser resolvido.
Portanto, Sudoku, se não sabe o que é,
vem do ***ão.
Destacou-se na década de 1980, mas foi apenas um destaque entre tantos outros.
Aqui está um Sudoku.
É uma grelha 9x9, e o objectivo é preencher cada linha com
números de 1 a 9, sem repetições.
Preenche-se cada coluna com números de 1
a 9, sem repetições.
E para aumentar a dificuldade, preenchem-se estes quadrados,
estes quadrados 3x3 com números de 1
a 9, sem repetições.
E a ideia do Soduku é que traga já algumas pistas.
Eles tirarão grande parte disto.
E ficará uma coisa com este aspecto.
Darão algumas pistas, e pedirão para
completar a grelha do Sudoku, sendo que só deve haver
uma forma de completar a grelha do Sudoku.
Se virem nos jornais, os jornais
dão cerca de 25 pistas para resolver a grelha, mas o que os fãs de Sudoku
queriam saber era qual o número mínimo de
pistas necessárias para preencher a grelha?
E os fãs de the Sudoku tentaram encontrar
o numero mínimo necessário.
Encontraram puzzles com 17 números, mas não conseguiram
encontrar nehum com 16 números.
Se tentarmos encontrar puzzles com 16 números, a resposta
a que chegaremos não é única.
Conseguiríamos uma ou duas respostas a partir desse puzzle.
Então pensaram que talvez 17 fosse
o número mais pequeno possível.
Gary McGuire conseguiu prová-lo no início deste mês, usando
um método parcialmente matemático
parcialmente com recurso a poder computacional.
Falemos no número de Sudokus existentes.
Certo, se quisermos preencher uma grelha de Sudoku com esta,
o número de grelhas possível é, deixem-me escrevê-lo
para vocês.
Vejamos, número de grelhas.
E vamos pôr um S no fim disto.
O número de grelhas de Sudoku é, por palavras, 6 700
milhões de milhões de milhões.
Os matemáticos escrevem-no assim.
6,7 vezes 10 elevado a 21.
Este é o número de grelhas de Sudoku existentes.
De relevar que o que eles estão a dizer não é que
todas as grelhas de Sudoku podem ser resolvidas com 17 pistas.
O que eles estão a dizer é que nenhuma grelha de Sudoku pode
ser resolvida com 16 pistas ou menos.
Pelo menos não de forma única.
Portanto uma forma de resolver este puzzle é verificar todas as grelhas
de Sudoku possíveis e depois verificá-las todas para 16 pistas
iniciais.
E verificar se isso vos dá uma solução única.
Essa é uma forma de o fazer.
É uma forma de o fazer usando força bruta.
Quantas formas há de gerar 16 pistas
para uma grelha de Sudoku?
Esse número, das 16 pistas, (não consigo escrever...).
Com 16 pistas é cerca de 33 milhões de milhares de milhões.
Cerca de 33 vezes 10 elevado a 16.
Acho que acertei.
3,3 vezes 10 elevado a 16.
Este é um número gigantesco.
O problema é que quem escreveu isto, Gary McGuire,
estimou que se usasse o método que tinha,
um computador precisaria de cerca de 300 000 anos para
verificar todas as soluções possíves para grelhas de Sudoku
com 16 pistas iniciais.
Portanto teve que simplificar o problema.
Isto foi o que ele fez.
Vejamos, Sudokus...
podemos pegar nas duas primeiras linhas e trocá-las,
continuaria a ser uma grelha válida.
Isto é permitido, certo?
Da mesma forma, se pegarmos em qualquer das três primeiras linhas
e as trocarmos, ainda teríamos uma grelha válida.
O mesmo é verdade para as próximas três linhas.
Trocamo-las, e temos uma grelha válida.
E as últimas três linhas.
Trocamo-las, e temos uma grelha válida.
Idem para estas secções.
Se pegarmos nestas secções e as trocarmos, ainda temos
uma grelha válida.
Pelo que se tivermos 16 pistas iniciais válidas,
essas 16 pistas iniciais continuariam válidas
se trocássemos as linhas.
E obtemos uma família de Sudokus.
A mesma coisa para as colunas.
É também semelhante se rodarmos a grelha
e se trocarmos os números.
Se trocarmos todos os 3 por 5,
ainda teríamos uma grelha válida.
Temos uma família inteira.
Só precisamos de um representante de cada
família de grelhas de Sudoku.
Agora, quantos representantes existem?
Só é preciso verificar um
representante de cada família.
Também podemos reduzir o número a quantidade de grelhas de 16 pistas
que é preciso verificar.
Este número.
O que se pode fazer, aqui está a minha grelha de Sudoku novamente.
Olhem para isto.
Vêem o 7 e o 9?
E aqui em baixo um 7 e um 9 nas mesmas colunas.
Se trocarmos os 7 com os 9 obtemos uma outra
grelha válida.
Não queremos duas soluções possíveis
para o Sudoku.
Para conseguir uma solução única, uma das pistas tem que ser
um destes quatro números.
Estes são quadrados inevitáveis.
Pelo menos uma das pistas tem que ser um destes quadrados.
Se encontrarmos os quadrados inveitáveis, conseguimos
reduzir o número de 16 pistas que temos que verificar.
Foi o que eles fizeram.
Procuraram quadrados inevitáveis
e os representantes das famílias de grelhas
e começaram, usando força bruta e um computador,
a analisá-las.
Demoraram sete milhões de horas de processamento a consegui-lo.
Começaram em Janeiro de 2011.
Terminaram em Dezembro de 2011 e
provaram que, naquilo que verificaram, nenhuma grelha com 16 pistas
resulta num Sudoku válido.
Sabemos que existem puzzles com 17 pistas.
Existem com 17 pistas, portanto eles provaram-no.
17 é o número mínimo de quadrados, o número mínimo de pistas
para resolver uma grelha de Sudoku de solução única.
E esta é a parte mais importante.
BRADY: Isto é perguntado a toda a hora a cientistas e matemáticos,
mas se existe momento apropraido para o fazer
esse momento é agora.
De certeza que há coisas melhores para fazeres com o teu tempo...
JAMES GRIME: Sim.
Certo.
Percebo perfeitamente.
Percebo perfeitamente.
Bem, para começar estamos a falar disto porque
é engraçado, certo?
As pessoas sabem o que são Sudokus, portanto percebem
o que estou a tentar resolver aqui, o problema.
Ao fazer isto, o método...
É um problema difícil.
É um problema difícil.
Os métodos que eles tiveram que desenvolver para resolver este problema
podem ser usados para outras coisas, possivelmente mais sérias.
Noutros problemas matemáticos.
Noutros problemas de combinatória.
E apesar de parecer trivial,
isto estende os limites do nosso conhecimento.
Portanto não é assim tão inútil.
Queres ouvir a minha piada Gary McGuire?
BRADY: Claro.
JAMES GRIME: Esta é a minha piada Gary McGuire.
Gary McGuire foi a pessoa que resolveu este puzzle, certo?
E aqui vai a minha piada Gary McGuire.
O que é que o Sudoku disse a Gary McGuire?
Tu completas-me.
Esta é uma referência ao filme Jerry Maguire.
Yeah.
É uma piada.
BRADY: Pois.
JAMES GRIME: Não é bem uma piada, tens razão.
Sou sincero, Sudoku não é o meu tipo favorito de puzzles,
porque é um jogo de lógica pura.
As pessoas acham que os matemáticos são máquinas da lógica,
como se fossem robôs.
Mas a Matemática não é isso.
Quero muito frisar que
a Matemática não é isso.
É algo muito mais criativo do que isso.
E, para mim, por ser um jogo de lógica pura que
eu sei que um computador consegue resolver, não tenho interesse nele.
Mas é muito popular entre as pessoas, e entre palavras cruzadas
e Sudokus, estes são
tipos de puzzles muito populares.