I  A resposta de ontem

Três cores, seis casas, uma fila só

Pegue seis peças, duas vermelhas, duas azuis e duas verdes, e chame a vermelha de 1, a azul de 2 e a verde de 3. A meta é enfileirar as seis de modo que haja uma peça entre as vermelhas, duas entre as azuis e três entre as verdes. São seis posições na mesa e três exigências valendo juntas.

O arranjo que resolve, lido da esquerda para a direita, é 3, 1, 2, 1, 3, 2. Na notação compacta ele aparece grudado, como 312132, e qualquer fila que cumpra a regra ganha o nome de emparelhamento de Langford (fila em que cada par respeita a própria distância).

Confira cada cor antes de seguir. Os dois 1 ocupam a segunda e a quarta casa, com apenas o 2 da terceira no meio. Os dois 2 ocupam a terceira e a sexta, com o 1 e o 3 no meio. Os dois 3 ocupam a primeira e a quinta, com três peças no meio.

Existe uma segunda fila que passa no teste, a 2, 3, 1, 2, 1, 3, e ela é a primeira lida de trás para frente. Espelho não conta como arranjo novo, e por essa contagem três cores admitem uma solução única.

Repare no que as três exigências fazem juntas. A cor 3 é a mais exigente, porque precisa de três peças entre as suas duas, e numa fila de seis posições ela só cabe em dois lugares. A cor 1 é a mais dócil, cabe em quase todo canto, e deve entrar por último. A ordem de colocação muda o trabalho inteiro.

A fila não trava por falta de espaço, e sim por excesso de compromisso. Cada peça posicionada assume duas obrigações de uma vez, a da própria cor e a de não roubar a casa que outra cor vai precisar.

Onde o teste de mesa trava

O primeiro erro é começar pela cor 1. Ela encaixa em qualquer buraco, dá a sensação de progresso, e some com as casas que a cor 3 exigia. Comece sempre pela cor de maior distância, que é a que tem menos opções.

O segundo erro é aceitar uma folga temporária com a promessa de ajustar depois. Uma distância errada no meio contamina tudo que vem à direita, e o conserto prometido quase nunca aparece.

O terceiro erro é achar que mais peças significam mais liberdade. Três cores fecham, quatro fecham, cinco não fecham de jeito nenhum e seis também não. A quantidade que funciona segue um padrão próprio, e o enunciado de hoje vive justamente no degrau em que a intuição quebra.

II  O Enigma do dia

Quatro cores e a fila que não perdoa

As regras valem reler. Cada cor entra duas vezes, a fila tem o dobro de casas em relação ao número de cores, e a distância cobrada é a contagem de peças entre as duas irmãs. A resposta pedida traz a fila escrita, o critério que separa as quantidades que funcionam das que falham, o nome de quem provou e o ano.

Onde quase todo mundo trava

O primeiro erro é adivinhar o critério pelos casos pequenos sem contar direito. Três funciona, quatro funciona, cinco falha, seis falha, sete funciona. Quem para nos dois primeiros acertos aposta num padrão simples e erra feio no oitavo caso.

O segundo erro é confundir fracasso pessoal com impossibilidade. A prova de que a fila não existe precisa de um argumento que cubra todas as ordens de uma vez. Com cinco cores são 3.628.800 arranjos das dez peças, e nenhuma tarde cobre essa lista à mão.

O terceiro erro é procurar a prova no lugar errado. O caminho passa por somar as posições ocupadas e comparar o resultado consigo mesmo. A soma denuncia a contradição antes de qualquer peça ir para a mesa.

Responda as três com prova. Escreva a fila de oito peças, o critério que decide quais quantidades de cores funcionam, o nome e o ano de quem fechou a demonstração, e o total de filas distintas com sete cores.

III  Sequência

O resto que a divisão por quatro entrega

O material é papel, lápis e vinte minutos. O procedimento abaixo fecha o caso e serve para qualquer arranjo em que se queira provar que uma montagem não existe.

1. Nomeie as posições. Numere as casas da fila de 1 até o dobro do número de cores e chame de p a posição da primeira peça de cada cor. A segunda peça fica na casa p somada à distância cobrada mais 1, porque a distância conta as peças no meio, e não os passos.

2. Some as posições de um jeito. Junte as duas posições de cada cor e depois junte todas as cores. O total é a soma das casas da fila, de 1 até o dobro do número de cores, porque cada casa é ocupada uma vez só.

3. Some as posições do outro jeito. Cada cor contribui com duas vezes a posição da primeira peça, mais a distância dela, mais 1. Somando cor a cor, aparece um termo par, formado pelo dobro das primeiras posições, mais a soma das distâncias, mais a quantidade de cores.

4. Iguale as duas somas e olhe a paridade. Os termos conhecidos se cancelam e sobra uma exigência simples: certas quantidades de cores obrigam o dobro das primeiras posições a valer um número ímpar, o que nenhum inteiro cumpre. As quantidades que criam a contradição são as que falham na mesa.

A resposta das três perguntas vem com todas as letras. A fila de quatro cores existe e é 4, 1, 3, 1, 2, 4, 3, 2, também única a menos do espelho. O critério é o resto da divisão por quatro: a fila existe quando o número de cores deixa resto zero ou resto três, e falha em qualquer outro caso. Quem fechou a demonstração foi Roy Oliver Davies, matemático britânico da Universidade de Leicester, em 1959, pela conta de paridade dos quatro passos acima. Com sete cores existem 26 filas distintas, sem contar os espelhos.

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

O tamanho do problema explode rápido depois do caso de sete. Com oito cores são 150 filas, com onze cores são 17.792, e a contagem para dezesseis cores passa de 326 milhões. Uma equipe liderada por Michel Krajecki, na Universidade de Reims, ocupou uma grade de máquinas por meses para contar o caso de 24 cores, publicado em 2004. O caso de 27 caiu em 2015, com o trabalho de Assarpour, Barnoy e Liotta, e o de 28 continua fora do alcance do hardware atual. Brinquedo de criança virou teste de força computacional.

Antes de gastar a tarde procurando um exemplo, pergunte se o problema tem uma conta de paridade escondida. Se a soma total das posições puder ser escrita de dois jeitos, a comparação decide em cinco minutos o que a tentativa não decide em cinco horas.

"Quantas vezes você insistiu numa montagem que a aritmética já tinha descartado antes da primeira peça?"

Teste hoje, em dez minutos: pegue oito objetos iguais dois a dois, moedas, tampinhas ou cartas, e monte a fila de quatro cores com as distâncias valendo. Comece pelo par de maior distância e deixe o par de distância 1 por último. Você fecha em menos de cinco minutos. Depois acrescente um quinto par e tente de novo: conte quantas montagens completas você tenta antes de desistir. Você vai passar de quinze tentativas sem nenhuma fechar, porque a conta de paridade já tinha descartado a montagem antes da primeira peça.

Segundo o texto, com quais quantidades de cores NÃO existe nenhuma fila que cumpra a regra de Langford?

Veja o ranking de quem mais acerta →

Como foi a edição de hoje?

Civilizações Perdidas

Às 20:20 na sua caixa: o capítulo do dia sobre um império que nasceu, prosperou e colapsou. E o que esse ciclo revela sobre o presente.

Quero receber →

Indique essa newsletter para um amigo

Cada leitor confirmado pelo seu link sobe um degrau da escada de prêmios.

{{indicacoes_confirmadas | 0}} confirmadas · faltam {{indicacoes_falta | 1}} pra próxima recompensa

● 1 Pack de wallpapers

■ 3 Edição de Colecionador do mês

▲ 5 ebook O Silêncio na Mesa

Pegar meu link de indicação →

{{streak_titulo | Comece sua ofensiva hoje}}

sua patente

{{rank_simbolo | ◆}} {{rank_nome | Aprendiz}}

faltam {{xp_falta | 5}} de ouro pra {{rank_prox | próxima patente}}