theorems-and-results.txt

Sprague Grundy:
En un juego imparcial normal, definimos SG como:
SG(x) = mex({SG(y) | x -> y es válido})
x es una posición perdedora <=> SG(x) = 0
Si sumamos dos juegos independientes, entonces:
SG(xy) = SG(x) ^ SG(y)

Hall's marriage:
Existe un matching perfecto <=> para cada subconjunto X de L |X| <= |N(X)|


Flujos:
Min cut = Max flow
(en bipartitas)
Min vertex cover = Max matching = Max Flow
Max indipendent set = N - Max Flow
(En dag)
(construyendo la bipartita L[i]->R[j] <=> Existe una arista de i a j)
Min path cover = N - Max Flow
(construyendo la bipartita L[i]->R[j] <=> Existe un path de i a j)
Max antichain = Min chain descomposition = N - Max Flow

Cosas varias:
Todo entero positivo es suma de cuatro cuadrados.
Todo entero positivo es suma de tres números triangulares.
Todo entero positivo es suma de nueve cubos.
Todo entero positivo es suma de diecinueve cuartas potencias.
Todo impar mayor que 5 es suma de tres primos.
Todo par mayor que 2 es suma de dos primos.
Todo entero positivo es suma de tres capicúas en cualquier base
Para los fibonacci Fi mcm(Fa,Fb)==F{mcm(a,b)}.