Solução para Copa do Mundo com 48 Seleções

A Copa do Mundo de 2026 terá 48 times. A proposta inicial é de haver 16 grupos de 3, sendo que 2 de cada grupo se classificariam para a fase de dezesseis avos de final.

Infelizmente, essa combinação abre a possibilidade de conchavo entre times no último jogo.

Então, resolvi analisar o problema e creio ter encontrado uma solução bastante razoável. As premissas são:

• O número de jogos que o campeão terá que jogar deve, quando muito, subir para 8 (dos atuais 7), mas o ideal é permanecer em 7;
• Não pode haver possibilidade de conchavo entre times;
• O número total de jogos não pode subir muito.

O atual formato resulta em 64 jogos ao todo e os semi-finalistas jogam um total de 7 jogos cada um. Os eliminados na primeira fase jogam apenas 3 jogos.

Então, 8 grupos de 6 não seria uma boa combinação: o número de jogos subiria muito e o torneio seria muito longo. Seriam 120 jogos na primeira fase e mais 16 nas eliminatórias. Os semifinalistas teriam que jogar 9 jogos.

Uma solução simples seria ter 12 grupos e classificar apenas os primeiros colocados e também os 4 melhores segundos colocados. Mas isso pode resultar em muitos jogos sem graça, nos quais ninguém tem mais interesse.

Então, ocorreu-me uma solução que mantem a emoção da primeira fase:

• 16 grupos de 3;
• Os grupos são agrupados em supergrupos, dois a dois (supergrupo A com grupos A1, A2, etc.);
• Classificam-se os primeiros de cada grupo e os 2 melhores seguintes do supergrupo.
• De cada supergrupo classificam-se 4 times (e dois são eliminados);
• A fase eliminatória começa com 32 times, então começaria em dezesseis avos de final;
• O número total de jogos para os semifinalistas permaneceria em 7;
• O número total de jogos subiria para 80.

Esse esquema mantém a emoção do último jogo de cada grupo, porque todos os times estarão ainda disputando uma vaga.

As pontuações possíveis em grupos de 3 são:

  2,2,2
  3,3,3
  4,2,1
  4,3,1
  4,4,0
  6,1,1
  6,3,0

Vamos a um exemplo:

• O grupo A1 tem Brasil (4 pontos), Suíça (4 pontos), e Coreia (0 pontos);
• O grupo A2 tem Uruguai (6 pontos), Bélgica (3 pontos), e Gana (0 pontos);
• Classificariam-se Brasil e Uruguai por serem os primeiros colocados de seus grupos e Suíça e Bélgica por serem os melhores dentre os seguintes.

Nenhum time pode chegar ao último jogo com mais de 3 pontos. E o outro grupo do supergrupo só pode estar com estas pontuações (supondo que o último jogo seria entre B e C):

  A B C
  6,0,0
  2,1,1
  0,3,3
  4,1,0
  4,0,1
  

Uma possibilidade de conluio apareceria se os times B1 e C1 (do grupo A1) chegassem os dois com 3 pontos cada e B2 e C2 (do grupo A2) estivessem com 0 pontos. Neste caso, um empate classificaria ambos com certeza, mas B2 e C2 ainda lutariam por uma vitória, porque um deles se classificaria. Uma ordem cuidadosa dos jogos poderia diminuir a possibilidade de que isso acontecesse (por exemplo, colocando os cabeças de chave no último jogo).

Alternativamente, os supergrupos poderiam ser aumentados para 4 grupos; seriam classificados os primeiros de cada grupo e os 4 melhores seguintes do supergrupo, resultando em 8 classificados por supergrupo.

A solução está dada, deixo os detalhes como exercício ao leitor.

Possíveis Combinações de Pontos nos Grupos da Copa do Mundo

A primeira fase das finais da copa do mundo tem grupos de 4 times; a vitória dá 3 pontos, o empate 1, e a derrota nenhum ponto.

Então, cada jogo tem 3 possibilidades e são 6 jogos entre os times A, B, C, e D:

• AxB
• AxC
• AxD
• BxC
• BxD
• DxC

Então, para contar todas as variações de resultados, contamos em base 3 de 000000 até 222222 (de 0 até 728); cada dígito nos diz se foi uma vitória do primeiro time, um empate, ou uma vitória do segundo time.

Após filtrar todas as pontuações repetidas, chegamos a 40 possibilidades:

   3,3,3,3   4,4,4,3   4,4,4,4   5,3,3,2
   5,4,3,2   5,4,4,2   5,4,4,3   5,5,2,2
   5,5,3,1   5,5,3,2   5,5,4,1   5,5,5,0
   6,4,4,2   6,4,4,3   6,5,2,2   6,5,4,1
   6,6,3,3   6,6,4,1   6,6,6,0   7,3,2,2
   7,4,2,2   7,4,3,1   7,4,3,2   7,4,3,3
   7,4,4,1   7,5,2,1   7,5,3,1   7,5,4,0
   7,6,2,1   7,6,3,1   7,6,4,0   7,7,1,1
   7,7,3,0   9,2,2,2   9,3,3,3   9,4,2,1
   9,4,3,1   9,4,4,0   9,6,1,1   9,6,3,0

Algumas constatações interessantes:

• A menor pontuação que sempre garante a classificação é 7;
• A menor pontuação que admite classificação é 2;
• É possível ser primeiro do grupo com qualquer pontuação a partir de 3;
• É possível o primeiro e o últimos terem a mesma pontução, se todos tiverem 3 ou 4 pontos.

Dado que um time tem de 2 a 6 pontos (as pontuações que não garantem classificação), as probabilidades de classificar são:

• 2 - 1/20;
• 3 - 5/27;
• 4 - 14/31;
• 5 - 19/20;
• 6 - 15/16.

Parece estranho, mas com 5 pontos é ligeiramente mais provável classificar-se que com 6. Nos dois casos em que o terceiro tem 5 ou 6 pontos, os dois primeiros têm a mesma pontuação.

Como Calcular o Tamanho de um Diretório no Linux

Começamos com o mais óbvio:

du -h 

Mas não quero ver todo o caminho até o último diretório, então só mostro os primeiros:

du -h --max-depth=1

Mas o diretório é um share de uma máquina Windows e o du não retorna os tamanhos corretos das coisas:

find . -type f -exec stat -c "%s" {} \;  \
  | awk '{ sum += $1 } END { print sum }'
  

E se quero apenas somar os arquivos de um determinado tipo (ou excluir alguns), posso tentar:

find . -name "*.pdf" -exec stat -c "%s" {} \; \
  | awk '{ sum += $1 } END { print sum }'

Teorema Chinês dos Restos (com SQL)

Lendo vários textos sobre o Teorema Chinês dos Restos, cheguei à conclusão que todas as explicações estão de ponta-cabeça. Então, resolvi atacar de uma maneira que eu pudesse entender.

Se pegarmos dois números p e q, primos entre si, sabemos que eles só vão se encontrar em p*q. Por exemplo, 5 e 8 só são ao mesmo tempo fatores de 40; 3, 4, e 5 só são ao mesmo tempo fatores de 3*4*5=60

Se eu montar uma tabela dos restos de cada número até 6 em relação a 2 e 3, terei algo assim:

N	mod 2	mod 3
0	0	0
1	1	1
2	0	2
3	1	0
4	0	1
5	1	2
6	0	0

As combinações dos restos de 2 e 3 são a chave primária para o N (exceto quando N for 0 ou 6).

Já que misturei Álgebra Relacional no assunto, vamos escrever um pouco de SQL para resolver problemas com 3, 4, e 5 (60). A minha solução para o problema com x mod 2=2, x mod 4=2 e x mod 5=1 é:

select * from (
  select rownum, 
         mod(rownum,3) as mod3, 
         mod(rownum,4) as mod4, 
         mod(rownum,5) as mod5
  from all_tables where rownum<60
) where mod3=2 and mod4=2 and mod5=1
                                  

O resultado é 26. Se eu brincar com as cláusulas uma a uma, descubro que com mod3=2 surge uma progressão aritmética que começa em 2 (lembre que x = 2 mod 3) com diferença de 3: 2, 5, 8, 11, etc. Com mod4=2 tenho uma progressão aritmética que começa em 2 e que pula de 4 em 4: 2, 6, 10, 14, etc. Com mod5=1 tenho uma progressão aritmética que começa em 1 e pula de 5 em 5: 1, 6, 11, 16, 21, 26, etc.

A brincadeira com SQL é boa para entender o problema, mas não é nada prática para a vida real, uma vez que o objetivo é trabalhar com números realmente grandes a partir de uma lista de números menores. Desenrolar todas as combinações de, digamos, os primeiros 100 primos exigiria uma quantidade absurda de disco ou de memória.

Então, meu próximo passo é entender os algoritmos usados para resolver o problema sem enumerar todas as combinações

Regexp com Lookaround no Grep

Muitas vezes encontrei-me concatenando greps para progressivamente encontrar dados e remover as partes redundantes. Algo assim:

  grep -Po "\(\d+\)" arquivo.log | grep -Po "\d+"
  

O primeiro grep extrai números cercados por parênteses e o segundo extrai os parênteses e deixa apenas os dígitos.

Para evitar essa repetição, podemos lançar mão dos operadores de lookaround (lookahead e lookbehind).

  grep -Po "(?<=\()\d+(?=\))" arquivo.log
  

O primeiro, um lookbehind, verifica se a expressão inicia com um parêntese "(?<=\()". O segundo, um lookahead, verifica se a expressão termina com um parêntese "(?=\))".

Esses operadores não consomem o que encontram, então o resultado não aparece na saída do grep. Isso explica também por que o lookbehind precisa ser diferente do lookahead; ele entra em ação quando a expressão regular já passou da posição dele.

Uma funcionalidade interessante seria permitir ao grep produzir uma expressão arbitrária com base nos grupos da expressão regular:

  grep -Po "\((\d+)\)" -out "$1" arquivo.log
  

Equanto isso não acontece, eu posso usar os operadores de lookaround para extrair valores e depois calcular a média usando awk, como no exemplo abaixo.

   grep -Po "(?<=\()\d+(?=\))" arquivo.log \
     | awk '{ sum += $1 } END { if (NR > 0) print sum / NR }'
     

Podemos chamar isso de CLI/BI.

Fatoração de Fermat

A soma dos números ímpares gera quadrados perfeitos: 1=1*1, 1+3=2*2, 1+3+5=3*3, 1+3+5+9=4*4, e assim por diante.

Além disso, todo número ímpar pode ser representado como a diferença entre dois quadrados (embora nem todas as diferenças de quadrados resultem num número ímpar).

Então, 16-1=15 ou 9-4=5, ou 25-16=9.

Fermat usou essa propriedade para fatorar inteiros. Dado um inteiro N ímpar, começamos pela raíz quadrada (a) e vamos procurando um valor b tal que a*a-N=b*b.

Dado que a soma da sequência de inteiros ímpares produz um quadrado perfeito, podemos usar isso para encontrar b.

Então, com 15, fazemos assim: 15+1=16. Essa é fácil: 16 é quadrado e 1 também. Isso nos dá que 15=(4-1)(4+1).

Vamos usar 39 como um exemplo mais difícil. 39+1+3+5+7+9=64 e (8-5)(8+5)=3*13=39.

Então encontramos soluções do tipo (b-c)(b+c) e c é o número de ímpares na sequência que somamos ao número que estamos tentando fatorar. No caso do número 39, acabamos passando por 49 e isso serviu para demonstrar como é mais fácil fatorar um número quando a solução está perto da raíz quadrada. Quanto mais longe (isto é, quanto mais distantes estiverem os fatores), mais difícil vai ser encontrar a solução.

Resíduos Quadráticos

O resto da divisão de um quadrado por 100 só pode ter um de 22 valores distintos:

 {00,01,04,09,16,25,36,49,64,81,21,24,29,41,44,56,61,69,76,84,89,96} 

Isto acelera os testes feitos manualmente. Mas a base 100 só é realmente melhor para os humanos.

Uma verificação rápida das bases até 256, revela que algumas têm porcentagens menores de resíduos quadráticos:

80=>12 (15%)
96=>14 (14%)
112=>16 (14%)
120=>18 (15%)
144=>16 (11%)
160=>21 (13%)
168=>24 (14%)
176=>24 (13%)
180=>24 (13%)
192=>24 (12%)
208=>28 (13%)
216=>33 (15%)
224=>28 (12%)
240=>24 (10%)
252=>32 (12%)

256 tem apenas 44 (17%). Não é a melhor, mas simplifica bastante o teste: basta conferir o último byte.

Ampliando a busca para 2 bytes, aparecem alguns valores supreendentes cujos resíduos quadráticos cobrem apenas 2% das possibilidades.

Por exemplo, o mais próximo de 65.536 é 65.520=>1.344 (2%).

Se, por outro lado, contarmos os resíduos quadráticos das bases impares, encontramos 50% quando a base é um número primo, o que constitui uma forma diferente de identificar primos.

Sobre Bases e Quadrados Perfeitos

O teste de divisibilidade por 3 ou 9 consiste em somar os dígitos e verificar se o resultado é múltiplo de 3 ou 9.

Por exemplo, 25 não é divisível por 3 ou 9, porque 2+5=7. Mas 3627 é, porque 3+6+2+7=18.

O interessante deste teste é que ele pode ser generalizado para outras bases. Ele funciona em base 10, porque 9 é 10-1 (e 3 divide 9). Em base 3, ele seria o teste do 2; em base 8, seria o teste do 7.

Vejamos os seguintes múltiplos de 7 em base 8:

• 14 => 16₈
• 21 => 25₈
• 28 => 34₈
• 49 => 61₈

Outro jogo interessante com bases é que o quadrado de n tem sempre a forma [n-1,1] na base n+1:

1*1=1 (base 2)
2*2=11 (base 3)
3*3=21 (base 4)
4*4=31 (base 5)
5*5=41 (base 6)
6*6=51 (base 7)
7*7=61 (base 8)
8*8=71 (base 9)
9*9=81 (base 10)
10*10=91 (base 11)
11*11=A1 (base 12)
12*12=B1 (base 13)
13*13=C1 (base 14)
14*14=D1 (base 15)
15*15=E1 (base 16)
16*16=F1 (base 17)
17*17=G1 (base 18)
18*18=H1 (base 19)
19*19=I1 (base 20)
20*20=J1 (base 21)

Não chega a surpreender, dado que n*n=(n+1)(n-1)+1.

Wordle

Wordle é a sensção do momento e com razão: o jogo é cativante. Ele surgiu em Outubro de 2021 e já existem inúmeras versões para todas as plataformas. Até mesmo os micros de 8 bits já têm suas versões.

Após jogar compulsivamente por alguns dias e chegar a uma tática bastante exitosa (iniciar sempre com as palavras AMBER e THUDS), resolvi analisar as palavras de 5 letras para entender melhor o problema.

Inicialmente, filtrei um dicionário para deixar apenas as palavras de 5 letras:

grep -Po "^[A-Za-z]{5}$" words.txt  | tr '[:upper:]' '[:lower:]'  > fives.txt

Depois analisei as frequências das letras:

fold -w 1 fives.txt  | sort | uniq -c | sort -nr
  12336 a
  10908 e
   8280 s
   7253 i
   7166 o
   7107 r
   6108 l
   5988 n
   5384 t
   4380 u
   3893 d
   3621 c
   3455 m
   3451 y
   3182 h
   2943 b
   2891 p
   2593 g
   2462 k
   1614 f
   1485 w
   1247 v
    760 z
    630 j
    459 x
    164 q
    
 

Então, filtrei as palavras com as 10 letras mais comuns:

grep -Po "^[aesiorlntu]+$" fives.txt  | wc -l
2089

São muitas, então filtrei as que não repetem letras:

grep -Po "^[aesiorlntu]+$" fives.txt  | grep -Ev '(.).*\1' | wc -l
888

Desta lista reduzida, podemos tirar algumas palavras interessantes. O desafio é selecionar duas palavras que juntas tenham as 10 letras mais frequentes.

join -j 2 best.txt best.txt \
 | grep a \
 | grep e \
 | grep s \
 | grep i \
 | grep o \
 | grep r \
 | grep l \
 | grep n \
 | grep t \
 | grep u \
 | sort | uniq | wc -l
2934

Tem muitas combinações de duas palavras com as 10 letras mais comuns em palavras de 5 letras, basta selecionar uma combinação. Por exemplo, "latin euros". O dicionário que escolhi talvez seja completo demais: ele inclui nomes próprios. Vasculhando um pouco, encontrei a dupla "nails route". Doravante, iniciarei as partidas com essa dupla.

Latin Euros vou guardar para o nome de meu grupo de Deep House Salsa.