A resposta de ontem Quantas voltas dá o círculo de raio 1 por dentro do de raio 3? Daria 2 voltas. Por dentro, o centro do círculo pequeno percorre um caminho de raio 2 (3 menos 1), de comprimento 4π, e cada volta do pequeno cobre 2π desse caminho. A viagem agora gira no sentido contrário ao do rolamento e tira uma volta das três da borda: a conta geral vira R/r menos 1, a mesma da hipocicloide. |
Gary McGuire, professor de matemática da University College Dublin, assinou a prova com dois colegas, Bastian Tugemann e Gilles Civario. O trio publicou o resultado no começo de 2012 no arXiv (repositório aberto de artigos científicos), com um título sem rodeio: “Não existe sudoku de 16 pistas”.
A ideia central tem nome técnico: conjunto inevitável (grupo de casas de uma grade completa capaz de trocar valores sem quebrar as regras). Se nenhuma pista cai dentro desse grupo, os números dali podem ser permutados, e o quebra-cabeça ganha uma segunda solução.
O exemplo mais simples tem quatro casas. Dois números, digamos 3 e 8, ocupam os cantos de um retângulo: 3 e 8 numa linha, 8 e 3 na outra, nas mesmas colunas, espalhados por duas caixas. Trocar os quatro deixa a grade válida. Um sudoku com solução única precisa de pelo menos uma pista nesse retângulo.
A busca virou uma caça de alvos. Para cada grade completa, o programa listava os conjuntos inevitáveis e perguntava: dá para escolher 16 casas capazes de acertar todos eles? Se não dá, nenhum sudoku de 16 pistas nasce daquela grade.
O programa, batizado de checker (verificador), percorreu as 5.472.730.538 grades essencialmente diferentes, uma por uma. Nenhuma aceitou um conjunto de 16 casas tocando todos os alvos.
A vantagem do método está no corte. Em lugar de testar bilhões de escolhas de 16 casas por grade, o verificador descartava de saída qualquer escolha que deixasse um conjunto inevitável sem pista, e quase todas caíam nesse filtro logo nos primeiros alvos.
Sete milhões de horas
A varredura rodou no Stokes, supercomputador do Irish Centre for High-End Computing (centro irlandês de computação de alto desempenho), ao longo de 2011. O artigo de McGuire de 2012 registra 7,1 milhões de horas de processamento, contadas núcleo por núcleo.
Num computador doméstico com um núcleo só, a mesma busca levaria mais de 800 anos. O Stokes dividia o trabalho entre milhares de núcleos rodando juntos, e o calendário encolheu para algo perto de um ano.
Antes de soltar a busca grande, a equipe testou o verificador nas grades conhecidas de 17 pistas. Ele precisava achar todas, sem perder nenhuma; se deixasse escapar uma de 17, também poderia deixar escapar uma de 16.
O resultado saiu revisado em 2014 na revista Experimental Mathematics. Desde então, 17 é o número oficial: existe sudoku de 17 pistas com solução única, e nenhum com 16.
|
Para um sudoku ter resposta única, as pistas precisam tocar cada grupo de casas capaz de trocar de lugar sem quebrar a grade.
|
A prova tem um limite honesto: ela depende de programa de computador, e ninguém escreveu ainda um argumento curto, de lápis e papel, para o piso de 17. O motivo é o tamanho; os conjuntos inevitáveis mudam de grade para grade, e nenhum padrão geral apareceu até hoje.
| 
