In partnership with

ED 071

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

Duijvestijn achou 21 quadrados num quadrado de 112

Desde 1939 se sabia cortar um quadrado em peças todas diferentes. O menor arranjo só saiu de um computador holandês em 1978.

Quadrado dividido em 21 quadrados menores de tamanhos diferentes.

21 peças, nenhuma medida repetida

▼

Dá para cortar um quadrado em quadrados menores, todos de tamanhos diferentes? Dá, e o menor jeito conhecido usa 21 peças dentro de um quadrado de lado 112.

O desafio parece de caderno escolar. Pegue uma folha quadrada e corte em quadradinhos, com uma regra só: nunca repetir uma medida. Com peças iguais o trabalho termina em segundos, porque quatro quadrados de mesmo lado cobrem qualquer quadrado maior. A proibição de repetir muda o jogo inteiro.

Matemáticos chamam o resultado de quadrado perfeito (um quadrado dividido em quadrados menores de lados inteiros e todos distintos). Durante décadas, gente séria desconfiou dele. O matemático russo Nikolai Lusin chegou a apostar que nenhum existia.

Em 1903, o alemão Max Dehn provou um resultado vizinho: um retângulo só se divide em quadrados se a razão entre os lados for racional (uma fração de dois inteiros). O teorema dizia quando o corte era possível, e nada falava sobre peças sem repetição.

A primeira solução publicada saiu em 1939, assinada pelo alemão Roland Sprague, em Berlim. Funcionava, e era enorme: um quadrado de lado 4.205, recortado em dezenas de peças.

Depois veio a caça ao menor arranjo. Tirar uma peça exigia testar milhões de combinações, tarefa sem fim para lápis e papel. Os candidatos cresciam rápido demais: um arranjo de 25 peças tem muito mais formas possíveis que um de 20, e conferir uma por uma à mão levaria vidas inteiras.

Em 1978, o holandês Adrianus Duijvestijn pôs um computador da Universidade Técnica de Twente para varrer as possibilidades. Saiu a resposta: 21 quadrados, com lados de 2 a 50, encaixados num quadrado de 112. Com menos peças, nenhum arranjo funciona.

O caminho até ele passou por quatro estudantes ingleses e um circuito elétrico. Logo abaixo, a história deles e de Duijvestijn; depois, um retângulo para montar com nove quadrados, e a solução peça por peça.

Continue lendo ↓

Quem banca a edição de hoje

Where Quantitative Thinkers Compete, Learn and Grow

The International Quant Championship (IQC) is one of the world's largest quantitative research competitions, bringing together 156,000+ participants globally.

Participants have the opportunity to develop quantitative research skills, challenge themselves alongside peers from around the world and connect with a global community of quantitative thinkers.

Build skills on WorldQuant BRAIN®

Patrocinadores mantêm a edição gratuita

I A resposta de ontem

O circuito de Cambridge e o computador de Twente

A resposta de ontem

Que fim levou o prêmio de US$ 2 milhões do Eternity II?

Ninguém levou os US$ 2 milhões. O prazo de conferência venceu no último dia de 2010 sem uma solução completa, e a fabricante Tomy pagou US$ 10 mil ao sueco Louis Verhaard pela melhor tentativa, com 467 das 480 bordas casadas. O tabuleiro de 256 peças segue sem solução publicada.

O trabalho que levou ao quadrado de 112 começou em 1936, com quatro alunos do Trinity College, em Cambridge: Leonard Brooks, Cedric Smith, Arthur Stone e William Tutte. Estavam na graduação e se reuniam para atacar problemas fora do currículo.

O primeiro passo deles foi trocar o quadrado por um retângulo. Achar um retângulo perfeito (peças todas distintas, sem a exigência de lados iguais por fora) era mais fácil, e o polonês Zbigniew Moroń já tinha mostrado um em 1925, de 33 por 32, com nove peças.

A virada veio da física. Qualquer retângulo dividido em quadrados vira um circuito elétrico: toda linha horizontal onde peças se tocam é um ponto do circuito, todo quadrado é um fio com a mesma resistência, e a corrente que atravessa o fio mede o lado do quadrado.

Com o circuito desenhado, as leis de Kirchhoff (as regras que dizem como a corrente se divide numa rede de fios) entregavam o tamanho de todas as peças. Desenhar redes era muito mais rápido que recortar papel.

Em 1940, o quarteto publicou o método no Duke Mathematical Journal, com o título The dissection of rectangles into squares (A dissecção de retângulos em quadrados). O artigo mostrava como gerar quadrados perfeitos em série a partir dos circuitos.

William Tutte seguiu outra trilha logo depois. Na Segunda Guerra, em Bletchley Park, quebrou a cifra Lorenz, usada nas mensagens do alto comando alemão, e mais tarde virou referência mundial em teoria dos grafos (o estudo de pontos ligados por linhas).

O quadrado sem repetição saiu de um diagrama de fios: o lado de cada peça é a corrente que passa por ela.

A caça ao menor

Em 1948, o inglês Theophilus Willcocks achou um arranjo de 24 peças. Era composto: dentro dele havia um retângulo menor, também feito de quadrados, que se podia isolar. O quadrado sem esse sub-retângulo escondido se chama simples, e o recorde dos simples seguia bem maior.

Duijvestijn atacou os simples. O programa dele gerava circuitos de vários tamanhos, calculava as correntes de todos os fios e descartava a rede sempre que duas peças saíam com a mesma medida.

Em 22 de março de 1978, a máquina entregou o quadrado de lado 112 com 21 peças. Duijvestijn publicou o achado no Journal of Combinatorial Theory, e a busca provou mais: nenhum quadrado perfeito usa menos de 21 peças, e o de 21 tem uma forma só.

As 21 medidas, da maior para a menor: 50, 42, 37, 35, 33, 29, 27, 25, 24, 19, 18, 17, 16, 15, 11, 9, 8, 7, 6, 4 e 2. A soma das áreas dá 12.544, exatamente 112 vezes 112.

A peça de lado 50 ocupa um canto, e a de lado 2 fica presa entre vizinhas muito maiores. Sem o circuito, ninguém adivinharia aquele encaixe a olho.

II O Enigma do dia

Nove quadrados num retângulo de 33 por 32

Você tem nove quadrados de lados 1, 4, 7, 8, 9, 10, 14, 15 e 18, todos diferentes. Monte com eles um retângulo de 33 de largura por 32 de altura, sem sobrepor e sem deixar buraco. Onde fica cada peça?

O enigma é o retângulo perfeito de Zbigniew Moroń, publicado em 1925, o mesmo que os estudantes de Cambridge usaram como ponto de partida. Ele cabe numa folha de papel quadriculado, e cada quadradinho da folha vale uma unidade.

Antes das pistas, as regras:

• Os nove quadrados entram todos, sem girar em ângulo torto.

• Nenhuma peça sai do retângulo de 33 por 32.

• Duas peças nunca ocupam o mesmo quadradinho.

Primeiro confira a área. Os quadrados das nove medidas somam 1, 16, 49, 64, 81, 100, 196, 225 e 324, ou 1.056 ao todo, e 33 vezes 32 dá os mesmos 1.056. A área bate, e a área sozinha não diz onde cada peça entra.

A primeira pista: as duas maiores peças, de lado 18 e 15, somam 33. Elas cabem juntas ao longo da largura.

A segunda pista: abaixo da peça de 18 sobra uma faixa de altura 14, porque 32 menos 18 dá 14. Uma das peças tem exatamente esse lado.

A terceira pista: debaixo da peça de 15, procure duas peças cujos lados somem 15.

A quarta pista: a peça de lado 1 é a última. Ela tapa um buraco de um quadradinho que as vizinhas deixam.

Onde o raciocínio escorrega

A primeira armadilha é começar pelas peças pequenas. Elas se encaixam em qualquer canto e não revelam nada sobre a estrutura.

A segunda é alinhar tudo em fileiras retas. Num retângulo perfeito, as bordas das peças quase nunca se alinham por muito tempo: elas formam degraus.

A terceira é desistir quando sobra um vão minúsculo. O vão de 1 por 1 faz parte do desenho.

Num arranjo sem repetição, as peças grandes decidem a forma e as pequenas só tapam os degraus que sobram.

Responda por escrito: diga a posição das nove peças, começando pelo canto de cima à esquerda.

Quem banca a edição de hoje

Build Your First GTM Agent Workflow

Logging. Enrichment. Routing. It’s the GTM work that eats a startup’s week. Agents can own it so your team gets back to selling.

On October 28, HubSpot and Dust run Build, Buy, or Hire? live. No panel. We build your first automated workflow in HubSpot and Dust, including a post-call automation and a Slack account ownership layer, and you take the build home.

Join the Live Build

Patrocinadores mantêm a edição gratuita

III Sequência

A peça de lado 1 tapa o último degrau

O retângulo fecha. Com o canto de cima à esquerda como ponto zero, a largura contada para a direita e a altura contada para baixo, a montagem sai em nove passos:

1. A peça de 18 ocupa o canto de cima à esquerda.

2. A peça de 15 ocupa o canto de cima à direita, completando a largura de 33.

3. A peça de 14 vai para o canto de baixo à esquerda, na faixa que sobra sob a de 18.

4. A peça de 7 entra logo abaixo da de 15, encostada na borda direita da de 18.

5. A peça de 8 completa a faixa sob a de 15, contra a borda direita do retângulo.

6. A peça de 4 tapa o degrau entre a de 18, a de 14 e a de 7.

7. A peça de 10 senta no fundo, à direita da de 14.

8. A peça de 9 ocupa o canto de baixo à direita, sob a de 8.

9. A peça de 1 tapa o vão entre a de 7, a de 10, a de 8 e a de 9.

Confira as alturas pela borda direita: 15 mais 8 mais 9 dá 32. Pela esquerda, 18 mais 14 dá os mesmos 32. No fundo, 14 mais 10 mais 9 dá 33, a largura inteira.

A peça de 7 e a de 8 deixam um degrau de altura 1 debaixo delas, porque uma desce até a altura 22 e a outra até 23. Esse degrau some exatamente com o quadradinho de lado 1.

No circuito de Cambridge, o mesmo retângulo vira uma rede com cinco linhas horizontais de contato. A corrente que sai do topo se divide em 18 e 15, e a soma das correntes que chegam ao fundo dá de novo 33, a largura.

Duijvestijn usou a mesma lógica numa escala maior. O quadrado de 112 é um retângulo perfeito com a exigência extra de lados iguais por fora, e a busca por circuitos dessa forma rara levou o computador a varrer milhares de redes.

Uma peça de lado 1 é o que separa um retângulo perfeito de um retângulo com buraco.

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.

“Quais duas peças, somadas, dão a altura de 32 pela borda esquerda?”

Teste hoje: em papel quadriculado, desenhe o retângulo de 33 por 32, recorte os nove quadrados e marque no relógio quanto tempo leva para montar sem olhar os passos. O esperado é fechar em menos de dez minutos começando pelas peças de 18 e 15, e passar de meia hora começando pelas pequenas. Sprague chegou ao primeiro quadrado perfeito em 1939, com lado 4.205.

Fica a pergunta · até amanhã

Quantos quadrados tinha o primeiro quadrado perfeito, o de Roland Sprague?

★ RARO

🔒

EDIÇÃO SELADA

Quem leu até aqui tem mais um achado desta edição atrás do lacre.

Abrir o selado →