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