In partnership with

ED 044

Os 36 oficiais que não cabem no quadrado

Leonhard Euler propôs em 1782 um arranjo de seis regimentos e seis patentes num tabuleiro 6 por 6, e a conta só fechou 118 anos depois.

Tabuleiro quadriculado de seis fileiras por seis colunas com peças militares de seis cores, uma casa vazia no canto.

Seis regimentos, seis patentes, um tabuleiro que resiste

▼

Por que um tabuleiro de 6 por 6 aceita seis regimentos em qualquer fileira, aceita seis patentes em qualquer fileira, e trava quando as duas exigências valem juntas? Porque as duas disputam as mesmas 36 casas, e o encaixe que resolve uma estraga a outra. Quem tenta na mão fecha quatro fileiras sem esforço e empaca sempre perto do fim.

O enunciado nasceu num texto acadêmico e virou passatempo depois. Leonhard Euler, matemático suíço nascido na Basileia em 1707, apresentou em 1782 à Academia de Ciências de São Petersburgo a memória Recherches sur une nouvelle espèce de quarrés magiques (Pesquisas sobre uma nova espécie de quadrados mágicos), e ali descreveu o arranjo que ficou conhecido como problema dos 36 oficiais.

O desenho cabe num parágrafo. Tome seis regimentos e seis patentes militares. Cada cruzamento de um regimento com uma patente produz um oficial, e os cruzamentos somam 36. Ponha os 36 num quadrado de seis fileiras por seis colunas, de modo que nenhuma fileira e nenhuma coluna repita regimento, e nenhuma fileira e nenhuma coluna repita patente.

Euler escreveu as patentes com letras latinas e os regimentos com letras gregas, e por causa dessa notação o arranjo passou a se chamar quadrado greco-latino (tabuleiro com dois alfabetos sobrepostos). Cada alfabeto, tomado sozinho, forma um quadrado latino (tabuleiro em que cada símbolo aparece uma vez por fileira e uma vez por coluna).

A armadilha mora na palavra nenhuma. Cada uma das duas proibições, sozinha, se cumpre de milhões de maneiras. O tabuleiro só interessa quando a mesma distribuição obedece às duas ao mesmo tempo, e a exigência dupla derruba quase tudo que se constrói por tentativa.

Euler examinou o caso de seis, não achou arranjo nenhum e escreveu que estava convencido da impossibilidade, admitindo que não tinha demonstração para oferecer. A afirmação ficou de pé por 118 anos, até um funcionário público francês varrer o problema inteiro à mão.

Com quatro naipes e quatro figuras de baralho o mesmo arranjo fecha na mesa em poucos minutos, e a versão pequena mostra a mecânica inteira, casa por casa.

Continue lendo ↓

I A resposta de ontem

Com quatro naipes, o quadrado fecha

Jacques Ozanam, matemático francês nascido em Sainte Olive em 1640, registrou a versão de baralho do problema no livro Récréations mathématiques et physiques (Recreações matemáticas e físicas), em edições ampliadas do século seguinte. O enunciado dele usa 16 cartas e cabe numa mesa de jantar.

Separe do baralho o ás, o rei, a dama e o valete de cada um dos quatro naipes. Monte com as 16 cartas um quadrado de quatro fileiras por quatro colunas em que nenhuma fileira e nenhuma coluna repita naipe, e nenhuma fileira e nenhuma coluna repita figura. As duas proibições são as do tabuleiro de seis, em escala menor.

O arranjo abaixo resolve. Leia por fileira, com P de paus, O de ouros, C de copas e E de espadas. Primeira fileira: ás de paus, rei de ouros, dama de copas, valete de espadas. Segunda: dama de espadas, valete de copas, ás de ouros, rei de paus. Terceira: valete de ouros, dama de paus, rei de espadas, ás de copas. Quarta: rei de copas, ás de espadas, valete de paus, dama de ouros.

Confira uma coluna antes de seguir. Na primeira aparecem ás, dama, valete e rei, sem figura repetida, e os naipes que acompanham são paus, espadas, ouros e copas, sem naipe repetido. As outras três colunas se comportam do mesmo jeito.

Repare no que os dois alfabetos fazem juntos. Olhando só as figuras, o tabuleiro é um quadrado latino. Olhando só os naipes, é outro quadrado latino. Quando os dois se sobrepõem sem que nenhum par figura mais naipe apareça duas vezes, os matemáticos dizem que eles são ortogonais (encaixados sem colisão), e esse encaixe é o coração do problema.

Cada proibição é fácil sozinha e quase impossível acompanhada. O que trava o tabuleiro grande não é a quantidade de casas, e sim a obrigação de os dois alfabetos combinarem casa a casa sem colidir uma vez sequer.

Onde o teste de mesa trava

O primeiro erro é preencher o tabuleiro figura por figura e deixar os naipes para o fim. As figuras fecham sozinhas com folga, os naipes chegam sem espaço e obrigam a desmontar tudo. Os dois alfabetos entram juntos, casa por casa.

O segundo erro é aceitar uma repetição temporária com a promessa de consertar depois. Uma colisão no meio do tabuleiro contamina as fileiras seguintes, e a correção prometida quase nunca chega.

O terceiro erro é achar que o tamanho manda. O quadrado de quatro fecha, o de cinco fecha, o de sete fecha, e o de seis não fecha de jeito nenhum. O padrão do tamanho não segue a intuição, e o enunciado de hoje vive no degrau que quebra.

II O Enigma do dia

Seis regimentos num tabuleiro que resiste

Seis regimentos, seis patentes, 36 oficiais, um tabuleiro de seis fileiras por seis colunas, e a regra de que nenhuma fileira e nenhuma coluna repita regimento nem patente. Três perguntas, e as três pedem resposta escrita, não palpite. Primeira: existe arranjo que cumpra as duas proibições, e o que serve de prova? Segunda: o total de quadrados latinos de ordem seis passa de 812 milhões, então como alguém conferiu o caso inteiro sem computador? Terceira: Euler estendeu a suspeita a 10, 14 e 18, e a suspeita continua de pé?

As regras valem reler. Cada oficial é um par de regimento com patente, e cada par aparece uma vez só no tabuleiro inteiro. As duas proibições valem para fileiras e para colunas. A resposta pedida traz a conclusão, o nome de quem demonstrou, o ano e o caminho usado.

Onde quase todo mundo trava

O primeiro erro é buscar um arranjo mais esperto. O candidato passa noites redistribuindo patentes e conclui que está perto, quando o problema pede uma prova de inexistência, e essa prova nunca sai de tentativa bem sucedida.

O segundo erro é confundir ausência de exemplo com impossibilidade. Ninguém ter achado não demonstra nada sozinho, e Euler foi honesto ao registrar a própria falta de demonstração. O passo que faltava exigia percorrer o espaço inteiro de tabuleiros possíveis, com método.

O terceiro erro é desistir diante dos 812.851.200 quadrados latinos de ordem seis. O número assusta e some quando se percebe que a maioria desses tabuleiros é cópia disfarçada de outro: renomear regimentos ou reordenar fileiras produz um tabuleiro novo na aparência e idêntico na estrutura.

Problema que pede impossibilidade se resolve cortando o espaço de busca antes de buscar. Agrupe os casos equivalentes, escolha um representante por grupo e confira só os representantes. A prova nasce do agrupamento, não da paciência.

Responda as três com prova. Escreva a conclusão, o nome e o ano de quem fechou a demonstração, e diga o que aconteceu com a suspeita de Euler sobre 10, 14 e 18.

Quem banca a edição de hoje

Replace 16 supplements in one daily drink.

David Beckham. Giannis Antetokounmpo. Aryna Sabalenka. Inter Miami CF. The world's best choose IM8 because performance starts with what you do every day.

Daily Ultimate Essentials and Longevity deliver a complete, clinically formulated system for energy, digestion, sleep, focus and healthy aging. In a 12-week randomized controlled trial, 95% felt a boost in daily energy, 85% felt less bloated with better digestion, 80% reported better sleep and 75% reported sharper focus and mental clarity.

IM8 is NSF Certified for Sport, tested against 280+ banned substances and recommended by 300+ clinicians. With 50 million servings sold across 46 countries, discover the IM8 routine trusted at the highest levels of sport—and built for everyday life. See the clinical results.

Discover David Beckham's Routine

Patrocinadores mantêm a edição gratuita

III Sequência

As 9.408 formas que Tarry teve de varrer

O material é papel quadriculado, um lápis e uma tarde. O procedimento abaixo fechou o caso original e serve para qualquer tabuleiro pequeno em que se queira provar que um arranjo não existe.

1. Fixe uma forma canônica. Escreva a primeira fileira e a primeira coluna em ordem crescente e trabalhe só com tabuleiros assim. Todo tabuleiro fora dessa forma vira um deles por troca de nomes, então nada de verdadeiro se perde no corte.

2. Conte quantos sobram depois do corte. Os 812.851.200 quadrados latinos de ordem seis caem para 9.408 quando se exige a forma canônica, e esse já é um número que uma pessoa organizada percorre com fichas.

3. Agrupe os 9.408 em famílias. Tabuleiros que viram um ao outro por troca de fileiras, de colunas ou de símbolos moram na mesma família, e a família inteira se decide pelo destino de um único representante. As famílias somam 17.

4. Teste cada representante à procura de um parceiro ortogonal. Para cada um dos 17, pergunte se existe outro quadrado latino que se sobreponha a ele sem repetir par nenhum. Se os 17 falharem, nenhum tabuleiro de seis por seis serve, e a impossibilidade fica demonstrada.

"Trinta e seis oficiais entrelaçados de Euler: solução quântica para um problema classicamente impossível."

Rather, Burchardt, Bruzda, Rajchel-Mieldzioć, Lakshminarayan e Życzkowski, título do artigo publicado na Physical Review Letters, 2022.

A resposta das três perguntas vem com todas as letras. Não existe arranjo, e a prova é de Gaston Tarry, francês nascido em 1843, funcionário da administração financeira na Argélia e matemático amador, que publicou a demonstração em 1900 sob o título Le problème des 36 officiers (O problema dos 36 oficiais). Ele conferiu o caso inteiro sem computador porque cortou o espaço de busca antes de buscar, pelos quatro passos acima, e chegou a 17 representantes conferidos à mão. A suspeita de Euler sobre 10, 14 e 18 caiu: em 1959 e 1960, Raj Chandra Bose, Sharadchandra Shankar Shrikhande e Ernest Tilden Parker construíram o arranjo para 10 e depois para todos os tamanhos da série que Euler dava como perdida. As exceções param em 2 e em 6.

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. Placar sem plateia ninguém falsifica.

O tabuleiro de seis ganhou um desfecho inesperado em 2022. Um grupo de físicos mostrou que a versão quântica do enunciado tem solução: quando cada oficial pode ocupar uma superposição de regimentos e patentes, as 36 casas se preenchem, e a impossibilidade clássica de Tarry continua intacta para oficiais de carne e osso. O nome de guerra dos três matemáticos que derrubaram a suspeita maior, em 1959, também pegou: a imprensa da época os apelidou de estraga prazeres de Euler.

Antes de caçar um exemplo, pergunte quantos casos realmente distintos existem. Se a resposta for um número que cabe numa tarde, a busca vira prova. Se você atacar o total bruto, vai varrer cópias disfarçadas até cansar e sem conclusão nenhuma.

"Quantas horas você já gastou procurando um exemplo que não existe, sem parar para contar quantos casos o problema tem de verdade?"

Teste hoje, em dez minutos: separe o ás, o rei, a dama e o valete dos quatro naipes e monte o quadrado de quatro por quatro com as duas proibições valendo. Você fecha em menos de cinco minutos, na primeira ou na segunda tentativa. Depois pegue papel quadriculado, escreva em cada casa um número de 1 a 6 para o regimento e uma letra de A a F para a patente, e tente o tabuleiro de seis por seis: conte quantas fileiras completas você fecha antes da primeira colisão. Você vai parar na quarta ou na quinta, e a fileira seguinte vai pedir um par que já saiu.