In partnership with

ED 067

Você escolhe a edição de amanhã: a votação está no fim desta edição.

As 10 mil senhas que cabem em 10.003 toques

Em 1946, Nicolaas de Bruijn descreveu a cadeia de dígitos em que cada senha de quatro números aparece uma vez só, sem toque sobrando.

Teclado numérico e uma longa fila de dígitos em que as senhas se sobrepõem.

Uma fila de dígitos, 10 mil senhas dentro

▼

Quantos toques custa testar todas as senhas de quatro dígitos num teclado? A resposta rápida é 40 mil, e está errada: num certo tipo de teclado, bastam 10.003.

A resposta rápida parte de uma suposição honesta. São 10 mil combinações, de 0000 a 9999, e cada uma pede quatro toques. Multiplicando, saem 40 mil dedadas, uma senha depois da outra, como quem risca uma lista.

Só que muito teclado barato funciona sem tecla de confirmar. Ele guarda os últimos quatro dígitos digitados e abre a porta assim que esses quatro batem com o código. Não existe começo nem fim de tentativa: o aparelho olha uma janela que anda, sempre com os quatro toques mais recentes.

Nesse teclado, quem digita 12345 testou duas senhas: 1234 e 2345. O quinto toque reaproveitou três dígitos do anterior. Cada tecla nova, depois da terceira, cria uma senha nova sem custo extra.

Daí nasce o problema bonito. Existe uma fila de dígitos em que as 10 mil senhas aparecem, cada uma exatamente uma vez, encavaladas umas nas outras? Existe, e tem nome de matemático holandês: sequência de De Bruijn (a cadeia mais curta que contém todas as combinações de um tamanho fixo).

O comprimento sai de um raciocínio de três linhas. Os três primeiros toques ainda não formam senha nenhuma. A partir do quarto, cada toque fecha uma senha. Para fechar 10 mil senhas são precisos 10 mil toques depois dos três iniciais: 10.003 no total.

A diferença assusta quem projeta fechadura. Quatro vezes menos toques significa quatro vezes menos tempo para quem tenta todas as combinações na força bruta (o ataque que testa uma por uma, sem pista nenhuma).

A seguir: quem descreveu a cadeia e o francês que chegou antes dele, um enigma em miniatura para montar com lápis, e a solução, com a regra simples que gera a fila inteira.

Continue lendo ↓

Quem banca a edição de hoje

200 Ways To Make Money With AI

Turns out, AI is good for more than writing emails and generating LinkedIn posts. This guide is packed with 200+ actionable ways to build income with AI.

Inside you'll discover:

200 curated AI income ideas for beginners and pros alike
Easy-to-start opportunities you can launch this week
Real world applications for today’s top AI tools
AI powered business models built for today’s economy
Creative ways to turn trends into revenue

AI is changing how people work and how people earn, far beyond the simple “write me an email” prompt. Discover the possibilities and download the free guide to start cashing in today.

Get The Free Guide

Patrocinadores mantêm a edição gratuita

I A resposta de ontem

O holandês e o francês esquecido

Nicolaas Govert de Bruijn, matemático holandês nascido em Haia em 1918, publicou em 1946 um artigo curto chamado A combinatorial problem (Um problema de combinatória) nos anais da Real Academia Holandesa de Ciências. O texto respondia a uma conjectura do colega Klaas Posthumus sobre a menor fita de zeros e uns que contém todas as palavras binárias de um tamanho dado.

De Bruijn fez mais do que achar uma fita. Ele contou quantas existem. Para palavras binárias de tamanho n, o número de cadeias diferentes é 2 elevado a 2^(n−1) − n. Com tamanho 3, saem duas cadeias; com tamanho 4, dezesseis; com tamanho 5, já são 2.048.

Em 1975, De Bruijn publicou uma nota de reconhecimento: o francês Camille Flye Sainte-Marie tinha resolvido a mesma contagem em 1894, na revista L'Intermédiaire des Mathématiciens. O resultado ficou esquecido por meio século, e o nome do holandês grudou na cadeia antes que alguém achasse o texto antigo.

A ideia é ainda mais velha. Na Índia antiga, o tratado de métrica poética de Pingala listava os oito padrões de três sílabas, cada sílaba curta ou longa. A palavra-memória yamātārājabhānasalagām (um mnemônico em sânscrito, a língua clássica indiana) passa por todos os oito numa fila só, com sílabas encavaladas, o mesmo truque de 1946.

Uma fila de dígitos pode conter milhares de senhas, cada uma usando três dígitos da vizinha.

Por que a cadeia sempre existe

A prova de De Bruijn usa um desenho de pontos e setas, o que matemáticos chamam de grafo (uma rede de pontos ligados por linhas). Para senhas de quatro dígitos, cada ponto é um trio de dígitos, de 000 a 999. Cada seta é uma senha: 1234 sai do ponto 123 e chega ao ponto 234.

Cada ponto tem dez setas saindo e dez chegando, uma para cada dígito possível. Leonhard Euler mostrou em 1736, no problema das pontes de Königsberg, que uma rede com entradas iguais às saídas em todo ponto admite um passeio que usa cada seta uma vez só.

Esse passeio é a sequência de De Bruijn. Percorrer as 10 mil setas, sem repetir nenhuma, é digitar as 10 mil senhas sem repetir nenhuma.

O mesmo desenho explica por que a fila fecha em círculo. O passeio termina no ponto onde começou, e assim a versão circular da cadeia tem exatamente 10 mil dígitos. Quem digita numa linha reta precisa repetir os três primeiros no fim, e daí vêm os três toques extras.

De Bruijn seguiu em frente com uma carreira longa. Lecionou na Universidade Técnica de Eindhoven, criou nos anos 1960 o Automath, um dos primeiros programas para conferir provas matemáticas por computador, e viveu até 2012.

O truque saiu do papel em 2015. O pesquisador de segurança americano Samy Kamkar apresentou o OpenSesame, um brinquedo eletrônico adaptado que abria portões de garagem com controle de código fixo. Os portões aceitavam a janela deslizante, e Kamkar mostrou que a cadeia derrubava o tempo do ataque de minutos para segundos.

II O Enigma do dia

Oito códigos em dez dígitos

Um cadeado digital aceita só os dígitos 0 e 1, e a senha tem três dígitos. Ele abre quando os três últimos toques batem com o código. Primeira pergunta: quantos códigos diferentes existem? Segunda: qual o menor número de toques que garante testar todos? Terceira: escreva uma fila com esse comprimento que passe por todos os códigos.

Antes das pistas, um aviso sobre o teclado: ele não tem tecla de confirmar e não trava depois de erros. Você digita quantos zeros e uns quiser, em fila, e ele só olha os três mais recentes.

Comece listando os códigos. Com dois símbolos e três posições, cada posição dobra as possibilidades. Escreva todos, do 000 ao 111, para não perder nenhum.

A primeira pista trata do tamanho. Os dois primeiros toques não fecham código nenhum. Do terceiro toque adiante, cada toque fecha exatamente um código novo.

A segunda pista trata da construção. Comece pela fila 000. A cada passo, tente acrescentar o dígito 1; se o código formado pelos três últimos dígitos já apareceu, acrescente 0. Pare quando nenhum dos dois servir.

A terceira pista trata da conferência. Deslize uma janela de três casas pela fila, uma posição por vez, e anote cada código que aparece. Se algum surgir duas vezes, a fila ficou maior que o necessário.

Onde o raciocínio escorrega

A primeira armadilha é multiplicar oito códigos por três toques e responder 24. Esse número serve para o teclado com tecla de confirmar, que zera a memória a cada tentativa.

A segunda é esquecer os dois toques iniciais e responder 8. Com oito toques, a janela só desliza seis vezes depois de cheia.

A terceira é começar a regra do 1 por uma fila qualquer. Partindo de 000, a regra nunca trava cedo; partindo de outro ponto, ela pode parar antes de passar por todos.

Na cadeia mais curta, cada toque depois dos primeiros abre uma porta que nenhum outro toque abriu.

Responda por escrito: quantos códigos existem, quantos toques bastam e a fila que você montou.

Quem banca a edição de hoje

Silver Has Beaten Gold Before. It's Doing It Again.

From 1974 to 1987, silver more than doubled gold's returns. After 2008, it beat gold five-fold in three years. Since March 2020, silver is up 402% against gold's 186%. Our research team's free playbook explains why, and how the team would position.

Get the Free Playbook

Patrocinadores mantêm a edição gratuita

III Sequência

A fila que passa por todas as portas

Códigos: dois símbolos em três posições dão 2 × 2 × 2 = 8. São 000, 001, 010, 011, 100, 101, 110 e 111.

Toques: os dois primeiros não fecham código; cada um dos seguintes fecha um. Oito códigos pedem oito toques depois dos dois iniciais, 10 no total.

Fila: a regra do 1, partindo de 000, gera 0001110100. Deslizando a janela, aparecem 000, 001, 011, 111, 110, 101, 010 e 100, os oito, sem repetição.

Nenhuma fila de nove toques resolve. Com nove dígitos a janela só mostra sete códigos, e falta pelo menos um.

O nome da regra é algoritmo de preferência pelo 1, descrito pelo matemático americano Monroe Harnish Martin em 1934. Para senhas decimais, a versão prefere o maior dígito ainda livre e entrega as 10 mil senhas em 10.003 toques.

Para montar a sua cadeia, siga quatro passos.

1. Escreva tantos zeros quanto o tamanho da senha.

2. Acrescente o maior dígito que forme, com os anteriores, um código ainda não visto.

3. Se nenhum dígito servir, pare: a fila está completa.

4. Confira deslizando a janela e riscando cada código numa lista.

A cadeia aparece longe das fechaduras também. Mágicos usam a versão binária em truques de cartas: o baralho é arrumado de modo que a cor de cinco cartas seguidas revela a posição exata no maço. Na indústria, fitas de posição gravadas com uma cadeia de De Bruijn deixam um sensor ler poucos riscos e saber onde está na fita inteira.

A defesa contra o ataque é simples. Teclado que exige tecla de confirmar, ou que trava depois de três erros, devolve o custo aos 40 mil toques ou mais. A cadeia só vence aparelho que esquece onde cada tentativa começa.

A fechadura que não pergunta quando a senha acabou entrega três quartos do trabalho de graça.

A Sequência é o placar de quem fecha sozinho. Um ponto por enigma resolvido antes de conferir a solução, e o placar zera quando você espia fora da hora.

“Quantos toques bastariam para testar todas as senhas de dois dígitos decimais?”

Teste hoje: escreva a cadeia para senhas de dois dígitos usando só 0, 1 e 2, começando por 00 e preferindo sempre o maior dígito livre. Cronometre. O esperado é uma fila de 10 dígitos com os nove pares, cada um uma vez; se algum par repetir, volte ao ponto em que a regra foi quebrada.