Todos os camiños levan a Roma (e 2)

Na entrada anterior propoñíamos un problema sobre grafos. De entre todos os tipos de grafos, podemos concordar en que os máis simples son os denominados grafos camiño ou grafos lineares. O grafo linear de lonxitude $n$ denótase $P_{n}$. Ilustraremos a idea co grafo linear $P_{4}$:

Camiños nun grafo linear. Cantos camiños de lonxitude $k$ hai entre os vértices de $P_{4}$?

Trátase de determinar a matriz dos camiños de lonxitude $k$ de $P_{4}$. Nesa referida entrada xa explicaramos o camiño a seguir para obter a solución. Debemos comezar pola matriz de adxacencia do grafo: $$A=\begin{pmatrix} 0 & 1& 0& 0 \\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 &1 \\ 0 & 0& 1& 0 \end{pmatrix}$$

A solución virá dada polas potencias da matriz de adxacencia. O elemento $(i,j)$ de $A^{k}$ indícanos o número de camiños de lonxitude $k$ entre os nodos $i$ e $j$. 

$A^{2}=\begin{pmatrix} 1 & 0&1 & 0\\ 0& 2 & 0 & 1\\ 1 & 0 & 2 & 0\\ 0 & 1 & 0& 1 \end{pmatrix}$ ; $A^{3}=\begin{pmatrix} 0 & 2& 0 & 1\\ 2& 0& 3 & 0\\ 0& 3& 0& 2\\ 1 & 0 &2 & 0 \end{pmatrix}$  ;   $A^{4}=\begin{pmatrix} 0 & 2 & 3&0 \\ 0& 5& 0&3 \\ 3& 0& 5&0 \\ 0 & 3& 0 & 2 \end{pmatrix}$   ;   $A^{5}=\begin{pmatrix} 0 & 5& 0 &3 \\ 5 & 0 & 8& 0 \\ 0& 8 & 0 & 5 \\ 3& 0& 5 & 0 \end{pmatrix}$

Curiosamente os elementos das matrices son vellos coñecidos. Efectivamente, son números da sucesión de Fibonacci (de aí o título da entrada: "Todos os camiños levan a Roma"; se para os de clásicas o centro do mundo se situa en Roma, os de matematemáticas caemos indefectiblemente na sucesisión argallada por Leonardo de Pisa). Volvamos a lembrar en que consiste a famosa sucesión:

$f_0$	$f_1$	$f_2$	$f_3$	$f_4$	$f_5$	$f_6$	$f_7$	$f_8$	$f_9$	$f_{10}$	$f_{11}$	$f_{12}$	$...$	$f_k$
$0$	$1$	$1$	$2$	$3$	$5$	$8$	$13$	$21$	$34$	$55$	$89$	$144$	$...$	$f_{k-1}+f_{k-2}$

Parece bastante evidente que as potencias pares seguen un patrón distinto das potencias impares. Seguindo a Martin Erickson en Beautiful Mathematics (MAA 2011)  conxecturaremos que:

Se $k$ é par: $A^{k}=\begin{pmatrix} f_{k-1} & 0&f_{k} & 0\\ 0& f_{k+1} & 0 & f_{k}\\ f_{k} & 0 & f_{k+1} & 0\\ 0 & f_{k} & 0& f_{k-1} \end{pmatrix}$

Se $k$ é impar: $A^{k}=\begin{pmatrix} 0 & f_{k}& 0 & f_{k-1}\\ f_{k}& 0& f_{k+1} & 0\\ 0& f_{k+1}& 0& f_{k}\\ f_{k-1} & 0 &f_{k} & 0 \end{pmatrix}$

Demostraremos por indución que este resultado é certo. Xa comprobamos máis arriba que o é para os valores de $k=1$, $k=2$, $k=3$, $k=4$ e $k=5$, algúns deles pares, outros impares. Supoñamos as fórmulas certas para un determinado valor $k$ e comprobaremos que serven para $k+1$.

Se $k$ é par: $A^{k+1}=A^{k}A=\begin{pmatrix} f_{k-1} & 0&f_{k} & 0\\ 0& f_{k+1} & 0 & f_{k}\\ f_{k} & 0 & f_{k+1} & 0\\ 0 & f_{k} & 0& f_{k-1} \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 0 \\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 &1 \\ 0 & 0& 1& 0 \end{pmatrix}=\begin{pmatrix} 0 & f_{k-1}+f_{k}& 0 & f_{k}\\ f_{k+1}& 0& f_{k+1}+f_{k} & 0\\ 0& f_{k}+f_{k+1}& 0& f_{k+1}\\ f_{k-1} & 0 &f_{k}+f_{k-1} & 0 \end{pmatrix}=$ $=\begin{pmatrix} 0 & f_{k+1}& 0 & f_{k}\\ f_{k+1}& 0& f_{k+2} & 0\\ 0& f_{k+2}& 0& f_{k+1}\\ f_{k} & 0 &f_{k+1} & 0 \end{pmatrix}$

Se $k$ é impar:

$A^{k+1}=A^{k}A=\begin{pmatrix} 0 & f_{k}& 0 & f_{k-1}\\ f_{k}& 0& f_{k+1} & 0\\ 0& f_{k+1}& 0& f_{k}\\ f_{k-1} & 0 &f_{k} & 0 \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 0 \\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 &1 \\ 0 & 0& 1& 0 \end{pmatrix}=\begin{pmatrix} f_{k} & 0&f_{k}+f_{k-1} & 0\\ 0& f_{k}+f_{k+1} & 0 & f_{k+1}\\ f_{k+1} & 0 & f_{k+1}+f_{k} & 0\\ 0 & f_{k-1}+f_{k} & 0& f_{k} \end{pmatrix}=$

$=\begin{pmatrix} f_{k} & 0&f_{k+1} & 0\\ 0& f_{k+2} & 0 & f_{k+1}\\ f_{k+1} & 0 & f_{k+2} & 0\\ 0 & f_{k+1} & 0& f_{k} \end{pmatrix}$

Todos os camiños levan a Roma (1)

Non sei se agora se estuda algo de teoría de grafos no grao de Matemáticas. Na miña época non se tocaba ese tema, por iso eu non teño nin idea sobre o asunto. Con todo, como son algo atolondrado, non é esta a primeira entrada do blogue que leva a etiqueta "grafos". Ao meu favor teño que todas esas entradas son moi básicas pois nada hai que saber de teoría de grafos para poder seguilas sen dificultade. Velaquí un novo exemplo no que verificar esta afirmación. 

Vou poñer como referencia un texto de divulgación, En busca del grafo perdido (Ariel, 2021), escrito por Clara Grima. Nun dos seus capítulos, para explicar o que é a matriz de adxacencia dun grafo, recolle unha escena da película do 1997 O indomable Will Hunting (Good Will Hunting) na que un profesor do mítico MIT (Massachusetts Institute of Technology) propón o seguinte problema:

A matriz de adxacencia deste grafo será: $$ A=\begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix} $$

Onde cada elemento $a_{ij}$ indica o número de arestas que conectan o vértice $i$ co vértice $j$. A propia matriz describe o número de camiño de lonxitude $1$ entre os vértices. Que pasa cos camiños de lonxitude $2$, isto é, os formados por dúas arestas?

O vértice $1$ pode conectarse consigo mesmo por medio de dúas arestas de dúas formas: $(1,2,1)$ e $(1,4,1)$. 

Ese mesmo vértice pode conectarse co vértice $2$ mediante un único camiño de lonxitude $2$: $(1,4,2)$. 

O vértice $1$ pode conectarse mediante dous camiños de lonxitude $2$ co vértice $3$: $(1,2,3)$ seguindo a aresta superior, e outro seguindo a aresta inferior.

Finalmente o vértice $1$ pode conectarse co vértice $4$ mediante un único camiño de dúas arestas, o camiño $(1,2,4)$

Resumindo, o número de camiños cos que o vértice $1$ pode conectarse con todos os vértices do grafo virá dado polos elementos da  fila $\begin{pmatrix} 2 & 1 & 2 &1 \end{pmatrix}$. Se fixeramos o mesmo co resto dos vértices obteriamos a seguinte matriz:$$A^{2}=\begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix} =\begin{pmatrix} 2 & 1& 2& 1\\ 1& 6 &0 & 1 \\ 2 &0 & 4 & 2 \\ 1& 1& 2 & 2 \end{pmatrix} $$  

Efectivamente, os camiños de lonxitude $2$ virán indicados polos coeficientes da matriz $A^{2}$. En xeral os coeficientes de $A^{n}$ resolven o problema de determinar a cantidade de camiños de lonxitude $n$. Daquela, a solución da segunda pregunta do problema da película obtense así:

$$A^{3}=A^{2}A=\begin{pmatrix} 2 & 1& 2& 1\\ 1& 6 &0 & 1 \\ 2 &0 & 4 & 2 \\ 1& 1& 2 & 2 \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix}=\begin{pmatrix} 2 & 7& 2& 3\\ 7& 2 &12 & 7 \\ 2 &12 & 0 & 2 \\ 3& 7& 2 & 2 \end{pmatrix}$$

Ben, ata aquí temos todos os vimbios para propoñer, e resolver, un problemiña.

Un problema simple

De entre todos os tipos de grafos, podemos concordar en que os máis simples son os denominados grafos camiño ou grafos lineares. O grafo linear de lonxitude $n$ denótase $P_{n}$. Ilustraremos a idea co grafo linear $P_{4}$:

Camiños nun grafo linear. Cantos camiños de lonxitude $k$ hai entre os vértices de $P_{4}$?

Trátase de determinar a matriz dos camiños de lonxitude $k$ de $P_{4}$. Para saborear o problema podemos abordar primeiro algúns casos máis simples. Poderiamos comezar estudando os camiños de $P_{2}$:

A matriz de adxacencia deste grafo será $A=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$; como $A^{2}=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}=I$ teremos que :

$A^{k}=\begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}=A$ se $k$ é impar e $A^{k}=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}=I$ se $k$ é par.

Que sucede no caso de $P_{3}$? Mirando o grafo

Vemos que a súa matriz de adxacencia é $A=\begin{pmatrix} 0 &1 & 0 \\ 1&0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$  polo que $A^{2}=\begin{pmatrix} 1 &0 & 1 \\ 0&2 & 0 \\ 1 & 0 & 1 \end{pmatrix}$ ; $A^{3}=\begin{pmatrix} 0 &2 & 0 \\ 2&0 & 2 \\ 0 & 2 & 0 \end{pmatrix}=2\begin{pmatrix} 0 &1 & 0 \\ 1&0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$;         $A^{4}=\begin{pmatrix} 2 &0 & 2 \\ 0&2 & 0 \\ 2& 0 & 2 \end{pmatrix}=2\begin{pmatrix} 1 &0 & 1 \\ 0&2 & 0 \\ 1 & 0 & 1 \end{pmatrix}$ ; $A^{5}=\begin{pmatrix} 0 &4 & 0 \\ 4&0 & 4 \\ 0 & 4 & 0 \end{pmatrix}=4\begin{pmatrix} 0 &1 & 0 \\ 1&0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$;         $A^{6}=\begin{pmatrix} 4 &0 & 4 \\ 0&8 & 0 \\ 4& 0 & 4 \end{pmatrix}=4\begin{pmatrix} 1 &0 & 1 \\ 0&2 & 0 \\ 1 & 0 & 1 \end{pmatrix}$  

Xa se ve como vai continuar.

Agora é o momento de abordar o problema orixinal, o dos camiños de $P_{4}$. É o teu turno. Prométoche que ten premio. Nunha próxima entrada, darei a solución.

Teorema de Hall. Aplicacións.

 Xa levamos varias entradas dándolle voltas ao seguinte resultado.

Teorema do matrimonio de Hall. Dado un grafo bipartito $G=(X,Y)$, unha condición necesaria e suficiente para que $X$ teña un emparellamento perfecto (condición de Hall) é que  $\forall A\subset X$ se verifique que $ \left| A \right|\le \left| N\left( A \right) \right|$

Xa vimos como se podía aplicar ao establecemento de trucos de maxia ou á resolución do problema do matrimonio. Agora toca aplicalo a novos problemas.

Unha carta de cada valor. Colocamos as 40 cartas dunha baralla española en 10 columnas de 4 cartas. Poderemos sempre, escollendo unha carta de cada columna, obter todos os valores (do as ao rei)?

Na seguinte imaxe temos un exemplo. Podes comprobar que neste caso si que podemos escoller unha carta de cada columna.

No exemplo da imaxe podemos coller de dereita a esquerda 1, 2, 3, 4, 5, 6, 7, Sota, Rei e Cabalo. A cuestión, claro, é se sempre é posible. 

Para iso establecemos un grafo bipartito. Por unha banda temos os 10 vértices que nos representan os 10 valores das cartas: 1, 2, 3, ,4 5, 6, 7, S, C, R. Por outra os 10 vértices que representan os 10 montóns $m_{1},m_{2},...,m_{10}$. Conectamos cada montón con todos os valores que conteña. Dado un subconxunto $A$ calquera de $k$ valores teremos  a súa veciñanza $ N\left( A \right) $  isto é, o conxunto de vértices (montóns) que están conectados con algún dos vértices de $A$. Supoñamos que $\left| N\left( A \right) \right|\lt k$. Isto significa que hai como moito $k-1$ montóns que conteñen as $4k$ cartas representadas por $A$. Pero en $k-1$ montóns só hai $4k-4$ cartas! De aí que a suposición que fixemos debe ser falsa. A conclusión é que se verifica a condición de Hall para calquera colección de valores: $\left| A \right|\le \left| N\left( A \right) \right|$. De aí que sempre poidamos establecer un emparellamento perfecto entre valores e montóns. Ademais este razoamento é completamente xeral polo que tamén é valido no caso de que quixeramos escoller os 13 valores distintos dunha baralla francesa distribuídos nunha matriz $4 \times 13$. Quizais sobra dicilo, pero tamén é factible escoller sempre unha carta de cada pau collendo unha carta de cada fila. Claro que esta posibilidade preséntase como menos espectacular.

Sempre gañadores

O seguinte problema ten certo empaque. Apareceu na competición Putnam do ano 2012. 

Sempre gañadores. $2n$ equipos xogan un torneo de todos contra todos. Durante $2n-1$ días cada equipo xoga exactamente contra un adversario distinto. Non hai empates.

Demostra que podemos escoller un equipo gañador diario sen que repitamos ningún equipo dúas veces.

O razoamento terá moitas concomitancias co anterior. Realizarémolo por redución ao absurdo. Comezamos establecendo un grafo bipartito con $2n-1$ vértices representando a cada un dos dos días do torneo e  outros $2n$ vértices identificando cada un dos equipos participantes. As arestas unen cada equipo cos días nos que gaña.

Razoaremos por redución ao absurdo. Supoñamos que non hai un emparellamento perfecto. Daquela non se verificará a condición de Hall e existirá un subconxunto $A$ de $k$ días tal que $\left| N\left( A \right) \right|\lt k$: neses días hai menos de $k$ gañadores. Velaí que haberá un xogador que perdeu todos os partidos durante eses $k$ días. Pero isto asegura que debe haber $k$ equipos gañadores diferentes nese período. Xa obtivemos a contradición.

Agochado no enunciado hai outro problema, o de establecer un calendario para unha liga na que $2n$ equipos xoguen todos contra todos. Pódese facer? Como? A pouco que un o pense decatarase de que é posible realizala, e de moitas maneiras distintas. No libro de Oystein Ore, Graphs and their uses (MAA 1990) ofrécese unha solución para o caso xeral.

Teorema de Hall: o teorema dos matrimonios

 Na entrada anterior presentaramos o seguinte resultado

Teorema do matrimonio de Hall. Dado un grafo bipartito $G=(X,Y)$, unha condición necesaria e suficiente para que $X$ teña un emparellamento perfecto (condición de Hall) é que  $\forall A\subset X$ se verifique que $ \left| A \right|\le \left| N\left( A \right) \right|$

Segundo a Wikipedia o teorema de Hall recibe o nome de teorema do matrimonio debido a un artigo do ano 1950 no que Halmos e Vaugan se refiren ao teorema para tratar a seguinte cuestión:

"Supoñamos que un grupo de mozos [...] coñece un conxunto finito de mozas. Baixo que condicións é posible que cada un deles se case cunha das súas coñecidas?"

Desde un punto de vista da sociedade actual o enunciado do problema fica algo desfasado. Con todo, o problema pode levarnos a unha ampliación do noso punto de vista matemático. Para iso seguiremos o libro de Gilbert Strang, Introduction to applied mathematics (Wellesley-Cambidge Press 1986).

Dadas $n$ señoritas , que por seren de xénero feminino identificaremos por $f_{1}, f_{2},..., f_{n}$ e outros tantos cabaleiros $c_{1}, c_{2},..., c_{n}$ estableceremos unha matriz $A=\left( a_{ij} \right)$ onde $a_{ij}=1$ se $f_{i}$ e $c_{j}$ están dispostos a casar. No caso contrario escribiremos $a_{ij}=0$. Se for posible establecer $n$ matrimonios significa que hai un emparellamento perfecto no grafo asociado. Vexamos un exemplo no que puidemos establecer $4$ matrimonios que son os que aparecen marcados nun recadro.

Porén no seguinte caso non é posible celebrar máis que tres bodas: $\left( f_{1},c_{3} \right), \left( f_{2},c_{4} \right)$ e $\left( f_{3},c_{2} \right)$:

Esta matriz dá lugar ao seguinte grafo no que resaltamos con arestas grosas os tres matrimonios:

Se escollo as tres últimas filas $\left\{ f_{2},f_{3},f_{4} \right\}$ comprobo inmediatamente que a súa veciñanza está formada por só dúas columnas $\left\{ c_{2},c_{4} \right\}$. Isto significa que non se verifica a condición de Hall. De aí que non poidan establecerse $4$ matrimonios.

Voulle chamar liña a unha fila ou columna. Comprobarás que marcando as tres liñas rodeadas en azul teño cubertos todos os $1s$ da matriz $A'$. Isto vén a conto do seguinte teorema que é equivalente ao de Hall:

Terorema de Köning-Egerváry. Nunha matriz de $0s$ e $1s$ o máxino número de matrimonios é igual ao mínimo número de liñas que cubren todos os $1s$

Todo isto podémolo relacionar con outras cousas coñecidas. Consideremos a matriz $A$ como un taboleiro de xadrez de dimensións $n\times n$ onde cada elemento é un escaque. Propoñemos o reto de colocar o maior número posible de torres sen que se ameacen entre sí coa restrición de que só está permitido colocalas nos escaques marcados con $1$. Evidentemente o xogo é esencialmente o mesmo problema que o do matrimonio.

Imos dar algo máis de terminoloxía para ampliar a perspectiva deste resultado. Unha cobertura $K$ dun grafo é un conxunto de vértices do grafo tal que todas as arestas do grafo teñen polo menos un vértice en $K$. Sempre será interesante obter unha cobertura mínima, isto é, aquela que teña o menor número de vértices posible. A seguinte figura pode aclararnos a situación. Nela están marcados en negro os vértices que forman a cobertura.

Os emparellamentos podemos consideralos como coberturas. Ademais dado calquera emparellamento $M$ e calquera cobertura $K$, verificarase claramente que $\left| M \right|\lt \left| K \right|$. Con estes vimbios podemos reescribir o

Teorema de Köning-Egerváry. Nun grafo bipartito o número de arestas dun emparellamento máximo é igual ao número de vértices dunha cobertura mínima.

Tamén podemos afrontar o problema desde un punto de vista alxébrico. Volvendo ás matrices, do que se trata é de obter o seu rango. Se hai unha fémina á que non lle guste ningún cabaleiro teremos unha fila só con $0s$. Neste caso xa sabemos que o determinante da matriz será nulo. Como todos os valores son $1s$ e $0s$ o teorema de Hall establece que para que poidan celebrarse $n$ matrimonios, ou o que é o mesmo, que a matriz dos matrimonios sexa regular,  vai ter que verificarse calquera das tres seguintes condicións equivalentes

• Non existe unha submatriz de $0s$ de dimensión $r\times s$ con $r+s\gt n$
• A cada subconxunto de $1 \le r\le n$ mozas lles gustan polo menos $r$ mozos
• A cada subconxunto de $1 \le s\le n$ mozos lles gustan polo  menos $s$ mozas

Na seguinte entrada veremos máis aplicación do teorema de Hall.

O teorema de Hall. O caso dos trucos de maxia de Cheney

Na entrada "Criptografía e maxia no Losada", onde relataba algúns aspectos da charla que viñeron impartir á Estrada Nicanor Alonso e Miguel Mirás, expliquei o truco de maxia das 5 cartas de Cheney. Este truco xa fora tratado por Martin Gardner pois todo o interesante xa foi tratado antes por Martin Gardner. Efectivamente unha versión do truco aparece no libro  El ahorcamiento inesperado y otros entretenimientos matemáticos (Alianza Editorial, 1991). Neste caso o mérito é aínda maior porque esta versión foi presentada nun congreso de magos, isto é, diante dunha audiencia incómoda para quen realiza o truco pois esa audiencia non estaba disposta a deixarse enganar.

O (mate)mago que presentaba o xogo era Victor Eigen. Un espectador, que non era outro que Martin Gardner, ofreceu a súa propia baralla para que o mago non tivese posibilidade de marcar as cartas. O espectador escolleu 5 cartas e (isto é unha diferenza importante coa versión relatada aquí) escolleu tamén cal desas 5 cartas se debía adiviñar. O único que podía facer o mago era ordenar as outras $4$ cartas. Nesa orde leváronllas á muller de Eigen, que se hospedaba nunha habitación do hotel que albergaba o congreso. E a muller acertou a carta escollida! Como podía ser?  $4$ cartas só podemos ordenalas de $24$ formas distintas. Parecía imposible que Eigen e a súa muller poidesen elaborar un código para as 52 cartas.

A resposta é a seguinte. En primeiro lugar, como á señora Eigen lle entregaban $4$ cartas xa non tiña que buscar a carta escollida entre as $52$ da baralla. Quedábanlle $52-4=48$ pero os Eigen só podían elaborar un código para a metade deste montón, $24$. A trampa era que o matrimonio reservara dúas habitacións contiguas e Victor non desvelou o número da habitación ata que Gardner escolleu a carta que debía adiviñar a señora Eigen. Cando Gardner petou nunha das portas para entregar as $4$ cartas, a muller de Victor puido descartar $24$

O truco orixinal

Volvamos ao truco orixinal, que apareceu nun artigo do ano 1950 na revista Math Miracles e no que lle atribuían a invención a Fitch Cheney. Lembremos as condicións. O mago marcha da habitación. Un espectador escolle $5$ cartas e o axudante do mago dálle a volta a unha desas $5$ cartas e colócaa á dereita das outras $4$ que fican cara arriba. Como é o axudante quen escolle a carta a adiviñar, podemos usar este feito para dar máis información ao mago-vidente. Na experiencia que relatamos da adiviñación no IES Antón Losada o axudante escollía unha carta do mesmo pau que a oculta. Isto reduce as posibilidades nun factor $4$ pero pode facerse mellor e as $P_{4}=4!=24$ posibilidades de ordenación das cartas poden chegar a multiplicarse por un factor $5$ á hora codificar toda a información. Ademais, ao estaren á vista $4$ cartas o mago sabe que a oculta non pode ser ningunha desas. De aí que o truco das $5$ cartas permitiría realizar a adiviñación nun mazo de $5\cdot 4!+4= 5!+4=124$ cartas. Neste artigo, Using a card trick to teach discrete mathematics,  Shai Simonson e Thara S. Holm mostran como facelo. Daquela podemos considerar en xeneralizar o truco para un mazo de $m$ cartas do que extraemos $n$ e despois, de entre estas $n$ o axudante escolle unha para que sexa a carta oculta. Así o mazo podería ter $m=n\cdot (n-1)!+n-1=n!+n-1$ cartas [1]. Na seguinte táboa mostramos os primeiros valores.

$n$	$m=n!+n-1$
$1$	$1$
$2$	$3$
$3$	$8$
$4$	$27$
$5$	$124$
$6$	$725$

Claro que o valor de $m$ podería ser menor. Se podemos establecer unha codificación para os valores de $m$ dados na táboa anterior, é evidente que tamén se poderá facer se o tamaño do mazo é inferior a $m$. Por exemplo, no caso relatado cando presentamos o truco de Cheney, o mazo era normal, tiña $m=52$ cartas, cando para $n=5$, tal e como queda establecido nesta táboa, poderiamos facer o truco para un total de $m=124$ cartas. 

Coa finalidade de afacernos ao problema, estudaremos os primeiros casos.  Para $n=2$ e $m=3$ a codificación é trivial.

12	13	23
1	3	2

As cartas ocultas son as que aparecen en branco con fondo negro. Así, se o espectador escolle o par $1,2$, o axudante dálle a volta á carta $2$ e o mago ao ver cara arriba a carta $1$ xa sabe que está oculto o $2$ 

Para o seguinte valor, $n=3$, $m=8$ as cousas xa se complican bastante. O espectador terá $C_{8,3}=\binom{8}{3}=56$ formas posibles de escoller 3 cartas. Agora o axudante debe deixar dúas delas cara arriba nunha determinada orde. Hai un total de $A_{8,2}=56$ arranxos, isto é, formas de escoller $2$ cartas ordenadas no mazo de $8$. Os valores coinciden, pero será posible establecer un código para cada caso? Teñamos presente que o código está formado por dúas cartas ordenadas, pero esas dúas cartas teñen que escollerse entre as $3$ determinadas polo  espectador. Neste caso pódese facer tal e como vemos na seguinte táboa. Se o espectador colleu as cartas $123$ o axudante tapa a última e deixa as outras na orde indicada na segunda fila $1,2$. Se a orde fose $2,1$ o mago sabería que a carta oculta tería que ser un $4$.

123	124	134	135	145	146	125	156
1,2	2,1	1,3	3,1	1,4	4,1	1,5	5.1
126	136	127	137	128	138	234	235
1,6	6,1	1,7	7,1	1,8	8,1	2,3	3,2
245	246	256	257	236	267	237	247
2,4	4,2	2,5	5,2	2,6	6,2	2,7	7,2
238	248	345	346	356	357	367	368
2,8	8,2	3,4	4.3	3,5	5,3	3,6	6,3
347	378	348	358	456	457	467	468
3,7	7,3	3,8	8,3	4,5	5,4	4,6	6,4
147	478	148	458	567	568	157	578
4,7	7,4	4,8	8,4	5,6	6,5	5,7	7,5
158	258	167	678	168	268	178	278
5,8	8,5	6,7	7,6	6,8	8,6	7,8	8,7

Poderemos establecer sempre un código? Ao escoller o código $(1,2)$ para 123 estamos imposibilitando que este código nos identifique os casos 124, 125,... 128 polo que todas estas escollas deben ser codificadas con outros pares ordenados de números que poderían ser $(1,4)$, $(1,5)$,..., $(1,8)$ pero estas novas escollas permitirán establecer un código distinto para as posibilidades que faltan? Haberá algunhas asignacións que nos impidan colocar as últimas identificacións. 

O seguinte caso, o de $n=4$ e $m=27$ xa daría lugar a unha táboa codificadora de $C_{27,4}=\binom{27}{4}=A_{17,3}=17550$ elementos.

En xeral o código poderá crearse se hai unha relación biunívoca entre todas as posibles escollas do espectador que suman un total de $C_{m,n}=\binom{m}{n}$ posibilidades, e as ordenación de $n-1$ cartas que faga o axudante. Este último valor contabilízase mediante os arranxos $A_{m,n-1}=m\cdot (m-1)\cdot ... \cdot (m-n+2)$. Se igualamos estas expresións:

$$C_{m,n}=\binom{m}{n}=\frac{m!}{n!(m-n)!}=A_{m,n-1}=\frac{m!}{(m-n+1)!}$$

Igualando denominadores e operando:

$$(m-n+1)!=n!(m-n)!$$ $$\frac{(m-n+1)!}{(m-n)!}=n!$$ $$m-n+1=n!$$ $$m=n!+n-1$$

Velaí que os dous conxuntos teñen o mesmo cardinal cando a cantidade de cartas do mazo é a que determinaramos previamente en [1]. A cuestión sería entón se se poderá establecer unha codificación da información dada polo protocolo do xogo para poder levalo a cabo en todos os casos. Unha opción sería a de elaborar un algoritmo que cree unha codificación para calquera caso. Esta sería a resposta escollida por un informático. Pero hai un achegamento máis bonito, o derivado do punto de vista matemático. Non nos dá a solución, pero hai un teorema da teoría de grafos que nos permite asegurar a existencia da codificación. O teorema é o seguinte.

Teorema de Hall. Dado un grafo bipartito $G=(X,Y)$, unha condición necesaria e suficiente para que $X$ teña un emparellamento perfecto (condición de Hall) é que  $\forall A\subset X$ se verifique que $ \left| A \right|\le \left| N\left( A \right) \right|$

Cómpre aclarar notación e conceptos para entendermos o teorema. Un grafo $G$ dise bipartito se pode descompoñerse na unión disxunta de dous conxuntos de vértices $X$ e $Y$ tales que os vértices de $X$ só se conectan con vértices de $Y$ (e viceversa). $N\left( A \right)$ fai referencia á veciñanza de $A$, isto é, o conxunto de vértices que están conectados con algún elemento de $A$. As barras verticais indican o cardinal. Un emparellamento $M$ dun grafo $G$ é unha colección de arestas que non teñen ningún vértice en común. Dise que un emparellamento SMS é perfecto se todos os vértices do grafo son extremo dalgunha aresta de $M$.

Consideremos o caso xeral. Temos $m=n!+n-1$ cartas distintas, o espectador escolle $n$ e o axudante dálle a volta a unha delas e ordena as restantes. Imos ver que poderemos establecer unha relación biunívoca (ou emparellamento perfecto) entre as $C_{m,n}$ escollas e as $A_{m,n-1}$ codificacións. Para iso consideramos o grafo bipartito $G=(X,Y)$ onde os vértices de $X$ serán cada unha das posibles combinacións e os de $Y$ cada un dos posibles arranxos. As arestas conectan cada combinación de $n$ elementos de $X$ con todas as posibles ordenacións de $n-1$ elementos desa combinación. Por exemplo na codificación anteriormente estudada para $n=3$ e $m=8$, a combinación 1-2-3 estaría conectada coas permutacións de dous elementos escollidos en {1,2,3}:  (1,2), (2,1), (1,3), (3,1), (2,3) e (3,2). Son un total de $n!=3!=6$ elementos. Da mesma maneira se consideramos un arranxo calquera, como (1,2) veremos que estará conectado coas  6 combinacións 1-2-3, 1-2-4, 1-2-5, 1-2-6, 1-2-7 e  1-2-8. Todos os vértices do grafo terán o mesmo grao, $6$. No caso xeral todos os vértices terán grao $n|$. Este tipo de grafos, nos que todos os vértices teñen o mesmo grao, chámanse grafos regulares. Vexamos que este grafo verifica a condición de Hall.

Efectivamente. Supoñamos que non a verifica, isto é, que existe un subconxunto $A\subset X$ de $k$ vértices que está conectado cun subconxunto de arranxos que ten menos de $k$ vértices. Como o grao de cada elemento é $n!$ a este subconxunto de arranxos, $N\left( A \right)$, deben chegar $n!\cdot k$ arestas. Velaí que polo principio do pombal ten que haber un arranxo ao que cheguen polo menos $n!+1$ arestas, o que entra en contradición con que todos os vértices tiñan grao $n!$.

Conviña decatarse de que non só demostramos a existencia de codificación para calquera truco estilo Cheney senón que acabamos de dar a proba do seguinte resultado:

Corolario. Sexa $G=(X,Y)$ un grafo bipartito regular. Daquela $G$ ten un emparellamento perfecto.

De querermos establecer un código completo para o truco de Cheney orixinal deberiamos cubrir unha táboa con $\binom{53}{5}=2.869.685$ celas!. Xa comprobáramos que para esta viaxe non cómpren tales alforxas. Con todo, como para unha escolla de $5$ cartas por parte do espectador temos asegurada a existencia dun código incluso cando o mazo ten $124$ cartas, a cantidade de emparellamentos codificadores para este valor tan baixo ($5$) xa subiría ata un total de $\binom{124}{5}=225.150.024$. Pode parecer sorprendente, pero neste pequeno traballo de Michael Kebler establécese un atallo para evitar tremenda tarefa.

O teorema de Hall recibe tamén o nome do teorema do matrimonio.  Na seguinte entrada centrarémonos neste aspecto, na súa relación co problema dos matrimonios. O resultado foi  demostrado polo matemático inglés Philip Hall (1904-1982), gran impulsor da teoría de grupos. Foi un dos participantes en Blettchley  Park no traballo de descodificación de mensaxes durante a II Guerra Mundial. 

Un eodermdrome galego

Foi o artigo do blogue Xogos de lingua, Non apto para sesquipedalofóbicos, o que prendeu a chispa para que elaborase esta entrada. Xogos de lingua, tal como indica o seu nome, é un blogue adicado á ludolingüística. Como tal, ten algunha entrada na que fai referencia ao gran divulgador das matemáticas, Martin Gardner, coñecido por utilizar os xogos como punto de partida de moitos dos seus artigos. Velaquí o punto de encontro entre a lingua e as matemáticas: o xogo. No libro Rosquillas anudadas (Labor, 1987), Martin Gardner fai referencia a un famoso reto de Henry Dudeney, aparecido no libro Amusements in Mathematics: auga, gas e electricidade consistente en unir co lapis as casas A, B e C cos subministros de auga (W), gas (G) e electricidade (E) de forma que as liñas de subministro non se corten. Tal e como o propio Dudeney adianta, é imposible realizar o que se pide no reto:

Figura 1:Amusements in Mathematics

Este problema entra dentro do campo da teoría de grafos. Os matemáticos chámanlle grafo a unha colección de vértices con arestas entre os mesmos. Cada aresta conecta dous vértices. Velaquí un par de exemplos.

Figura 2. Dous grafos simples

Nota: aquí debuxei as arestas mediante segmentos rectos, pero non hai porque facelo así. O importante dunha aresta consiste nos vértices que conecta.

Figura 3:Grafo K₅

Cómpre avisar que os únicos vértices do grafo son os marcados en cor. Neste grafo denominado K₅  hai 5 vértices e 10 arestas.  O grafo completo de grao n, denotado K_n é o un grafo de n vértices na que todo vértice está conectado con todos os demais vértices. Aquí presentamos o grafo completo de 5 vértices. Algunhas das arestas deste grafo crúzanse, o mesmo lle sucede ao grafo que representa o problema de Dudeney (cada unha das arestas superiores representa unha compañía subministradora e as inferiores representan as casas)

Figura 4: grafo K_3,3

Na Figura 1 podemos ver como este grafo podería representarse con só un cruce, pero sería imposible facelo sen cruce ningún, niso consiste a imposibilidade da resolución do problema das tres casas. Os grafos que poden representarse sen cruces, como os da figura 2, chámanse grafos planares. Hai que ter en conta que nun grafo só nos interesa a forma en que están conectados os vértices, non esta ou aqueloutra representación particular. Para un grafo dado, sempre poderemos buscar a representación que teña o menor número posible de cruces. Na seguinte figura vemos como o grafo que está representado (á esquerda) con cruces, pode representarse (á dereita) sen cruces. Trátase, polo tanto, dun grafo planar.

Figura 5: Grafo planar

Hai unha forma de saber se un grafo é planar ou non grazas ao teorema de Kuratowski: se o grafo non contén ningún subgrafo K₅ nin K_3,3 será planar. Grafos de palabras Podemos combinar os grafos coas palabras conectando cada letra con aquelas ás que é adxacente. Se unha letra aparece repetida e consecutiva, non debuxamos aresta ningunha xa que consideramos a letra conectada consigo mesma. Por exemplo, as palabras touporroutou e nacionalismo terían os seguintes grafos asociados:

Figura 6

Figura 7

A pouco que un remexa nos grafos de palabras, decatarase de que prácticamente todos son planares. As palabras que dan lugar a grafos non planares chámanse eodermdromes. Por suposto, propia palabra eodermdrome é un eodermdrome (ver a figura 7). A. Ross Eckler elaborou no ano 1980 un dicionario de eodermdromes para a lingua inglesa. Martin Gardner cualificaba esta publicación como unha aplicación extravagante do estudo do número de cruces dun grafo fronte á indubidablemente interesante aplicación ao deseño de microcircuítos. Temos unha lista de eodermdromes en inglés pero, haberá algún en galego? As candidatas deben ter unha cantidade considerable de letras, canto máis longas, máis arestas terá o seu grafo e máis posibilidades haberá de que teña un cruce inevitable. Por iso, cando na  entrada de Xogos de lingua vin que se referenciaban as palabras máis longas do noso vocabulario, púxenme a comprobar se entre elas había algún eodermdrome.  O grafo correspondente á palabra máis longa, esternocleidomastoideo, é o seguinte:

Figura 8

Como podemos observar, esternocleidomastoideo é planar. Tamén o son preterintencionalidade, contrarrevolucionario, electroencefalografía ou incluso hipopotomonstrosesquipedaliofobia. Pero a outra palabra, extraterritorialidade contén un subrafo K_3,3,, o que establece todas as arestas entre os dous conxuntos de vértices {t,r,d} e {i,a,e}. Por fin, aquí temos un eodermdrome da nosa lingua:

Figura 9

Haberá outros? Existirá algún que conteña un subrafo K₅? As arestas destes grafos representan un par de letras adxacentes. Cales serán as arestas máis frecuentes en galego?, e noutras linguas? Poderán determinarse a lingua en que vén redactado un texto estudando o tipo de arestas máis frecuentes do mesmo? Todo un extravagante campo de traballo  para a lingüística informática.

Grafos e divisores.2

Nunha entrada anterior chegamos á idea de grafo de divisores de forma natural, como ferramenta para abordaxe do estudo da lonxitude dos camiños nun xogo de múltiplos e divisores que recolliamos da páxina Nrich. Así, dado o conxunto S dos n primeiros números naturais construiamos un grafo de tal xeito que se $$i,j\in S\quad \quad \quad ij\quad é\quad unha\quad aresta\quad \Longleftrightarrow \quad i|j\quad ou\quad j|i$$
O concepto de grafo de divisores pódese ampliar tomando S como calquer subconxunto finito de números enteiros. Con esta nova definición resulta que temos moitos grafos que son grafos de divisores. Por exemplo todos os posibles grafos con 5 vértices ou menos, agás un, son grafos de divisores. Non é nada complicado debuxalos todos asignándolle os números correspondentes aos vértices para comprobar que realmente son grafos de divisores. Velaquí uns poucos de exemplos (a comprobación da totalidade deles pode ser un exercicio divertido)

Unha actividade entretida para os que teñan algo de gosto pola astronomía podía ser o de indagar se as constelacións son grafos de divisores. Velaquí, por exemplo que o Setestrelo sí que o é:Se temos n vértices, o maior número de arestas que podemos establecer entre eles é un deses problemas que se resolven nas primeiras clases de combinatoria:

 son $$\left( \begin{matrix} n \\ 2 \end{matrix} \right) $$.
Tendo isto presente, verifícase o seguinte teorema:
$$Dados\quad dous\quad números\quad naturais,\quad n\quad e\quad m,\quad con\quad 0\le m\le \left( \begin{matrix} n \\ 2 \end{matrix} \right) ,\quad \\ hai\quad polo\quad menos\quad un\quad grafo\quad divisor\quad con\quad n\quad vértices\quad e\quad m\quad arestas$$

Este resultado asegura certa abundancia de grafos divisores. Tamén se sabe que todos os grafos completos K_n , K_m,n ,  as árbores e todos os grafos bipartitos son grafos de divisores. Pero tamén hai moitos outros grafos que non son divisores. O grafo cíclico C₅ non é un grafo divisor, incluso máis, ningún grafo divisor pode conter a C₅. A razón de que isto sexa así vén da transitividade da relación "ser divisor de". Así, todo grafo divisor ten asociado un grafo dirixido no que se u|v podemos establecer un arco (u,v). Se C₅ fose un grafo divisor, tería que haber tres vértices x, y, z, tales que x|y e y|z. Polo tanto x|z e debería haber unha aresta máis que as que ten C₅. De feito, ningún grafo cíclico impar de 5 ou máis vértices, pode ser un grafo divisor.

Pola contra é moi doado establecer un algoritmo que asigne valores numéricos aos vértices co fin de converter en grafos divisores todos os cíclicos pares.  Para comprobarmos que por exemplo C₆ é un grafo de divisores basta ir etiquetando, poñamos por caso, no sentido das agullas dun reloxo, un vértice si e outro non, cos primeiros primos: 2, 3, 5,.... Os vértices intermedios serán o produto dos dous adxacentes. Está claro que a paridade é o que determina que poidamos realizar esta etiquetaxe nun grafo cíclico.
Xa sabemos que C₅ non é grafo de divisores. Podemos dar referencia de moitos máis. Velaquí un par de exemplos:

Entón xurde a cuestión de caracterizar os grafos divisores. Xa sabemos que a todo grafo de divisores vaille asociado un grafo dirixido. Basta escoller os arcos a partir da relación "u divide a v". Daquela temos o seguinte resultado:

Que un grafo sexa un grafo de divisores é equivalente a que exista unha orientación que verifique a propiedade transitva [isto é, se (u,v) e (v,w) son arcos, entón (u,w) tamén o será]

Xeneralizando
Pódese ampliar novamente o concepto de grafo divisor. No canto de considerar o conxunto dos números enteiros podemos tomar un anel conmutativo calquera.
Neste contexto vai unha cuestión. Sexa K₅ o grafo completo de 5 vértices. Será un grafo de divisores? Para abordar a pregunta pensei que se podería resolver se tiñamos un anel con 5 unidades.
Sexa
$$\xi ={ e }^{ \frac { 2\pi i }{ 5 }  }=cos\frac { 2\pi  }{ 5 } +i\cdot sen\frac { 2\pi  }{ 5 }  $$ a raíz quinta da unidade. Resulta que o anel ciclotómico $$Z\left[ \xi  \right] $$ ten como unidades $$1,\xi ,{ \xi  }^{ 2 },{ \xi  }^{ 3 },{ \xi  }^{ 4 }$$ polo que o grafo divisor asociado ao conxunto destes cinco elementos é o grafo completo K₅.
Despois de pegar este chimpo vin que se podía chegar ao mesmo resultado cun grafo en Z, tomando o conxunto de vértices $$S=\left\{ 2,{ 2 }^{ 2 },{ 2 }^{ 3 },{ 2 }^{ 4 },{ 2 }^{ 5 } \right\} $$
Está claro que todos os grafos completos son divisores. A cuestión que me asaltou é se hai algún anel que dea acubillo a algún grafo divisor que non poidamos atopar en Z.

Máis?
Un concepto asociado ao dos grafos divisores é o dos grafos coprimos. Considerando o conxunto de vértices entre os enteiros, as arestas (u,v) estableceranse entre aqueles números que sexan coprimos.
Dada un grafo G calquera, seguindo o seguinte procedemento, obteremos un grafo coprimo isomorfo a G:

• Consideremos o grafo complementario G cos mesmos vértices e cuxas arestas son xusto as que non aparecen en G
• En G etiquetamos todos os vértices aillados con números primos (distintos)
• Se temos unha aresta aillada en G escolleremos outro primo p e etiquetaremos os dous vértices como p e p²
• Se temos unha compoñente de orde 3 ou más en G, asociaremos primos distintos a cada unha das súas arestas. Entón cada vértice etiquétase co produto das arestas que inciden nel.

Deste xeito podemos construir un grafo coprimo isomorfo a calquera outro dado: todos os grafos son grafos coprimos. Velaquí, como exemplo, temos o proceso de etiquetaxe de C₅.

Algunhas lecturas
Whic graphs are divisor graphs?
Bipartite divisor graphs
Divisor graph have arbitrary order and size
On the logest simple paht in a divisor graph
Further new properties of divisor graphs

Grafos e divisores.1

Do portal NRICH

Remexendo pola arañeira batín con este entretido xogo do web NRICH (enriching mathematics).   Participan dous xogadores alternativamente escollendo da grella de números da esquerda que, como se ve, contén os 100 primeiros naturais. As regras son moi sinxelas:
Regra 1.O primeiro xogador pode escoller calquera número menor que 50 (no exemplo puxen o 45).
Regra 2. O seguinte número debe ser sempre un múltiplo ou un divisor do anterior.
Finalización. Perde aquel que non poida coller ningún número máis.
O xogo pode propoñérse en calquera aula dos primeiros cursos da ESO xa que permite desenvolver o cálculo e a familiarización cos conceptos de múltiplo, divisor, número primo, número composto, coprimos,...
NRICH suxire dar novos enfoques ao xogo, como o de presentalo sen a restricción dada pola primeira regra para logo poñer en evidencia a súa necesidade se non queremos ter un xogo trivial. Tamén podemos investigar se hai algunha estratexia gañadora, ou se hai números que nos convén evitar. Claro que as posibilidades non rematan aquí. De ser moi complicada a abordaxe deste xogo, podería restrinxirse a outras versións que tiveran unha menor cantidade de números: 15, 20, 30, 50,... ou, se cadra, somos quen de aventurar que é o que sucede cando partimos de 101 números, ou 200, ..., 1000,...n,...
Tamén está a cuestión de cal é a maior cadea de números que podemos formar na grella da dereita. Por exemplo, na imaxe anterior tiñamos unha cadea de 11 números susceptible de ser ampliada. Para estudar o problema podemos ver que é o que pasa cos primeiros casos.
O problema parece que pode abordarse botando man dos grafos. Partimos dun conxunto de vértices numerados polos n primeiros números
$$S=\left\{ { v }_{ 1 },{ v }_{ 2 },{ v }_{ 3 },...{ v }_{ n } \right\}$$
Para establecermos as arestas usaremos a seguinte definición
$${ \forall i\neq j\quad v }_{ i }\quad e\quad { v }_{ j\quad  }\quad forman\quad unha\quad aresta\quad \Longleftrightarrow \quad i|j\quad ou\quad _{ \quad  }j|i$$
A un grafo así determinado podémoslle chamar grafo de divisores. No grafo de divisores dado polos cinco primeiros números está claro que a cadea máis longa que podemos formar ten unha lonxitude de 4 vértices: 3, 1, 2, 4.
Pero a pouco que pasemos dos primeiros casos, como era de esperar, o grafo vaise complicando. Para o grafo de divisores dos 13 primeiros números naturais teremos polo menos unha cadea de lonxitude 10 a seguinte: 9, 3, 6, 12, 4, 8, 1, 5, 10, 2 (ou 11, 1, 5, 10, 2, 8, 4, 12, 3, 9) que parece difícil de superar

Se lle chamamos f(n) ao valor da lonxitude da máxima cadea que podemos formar nun destes grafos de n números, acabamos de ver que f(4)=f(5)=4 e que f(13)=10. Podemos intentar obter unha táboa que nos ofreza pistas para intentar aventurar o resto dos valores de f(n). Pero a cuestión non é nada simple.
Parece ser que P. Erdös, R. Freud e N. Hegyvári estableceron que para valores de n o suficientemente grandes (nas fórmulas log indica o logaritmo neperiano):
$$f(n)\le (1-log2)n$$
Se quixeramos unha limitación inferior teriamos esta de A. D. Pollington:
$$\forall c>0\quad \exists N/n\ge N\Longrightarrow f(n)\ge n\cdot { e }^{ -(2+c)\sqrt { logn\cdot log(logn) }  }$$
O artigo de Erdös e cia. non falaba de grafos senón de permutacións a₁, a₂ ,a₃, ..., a_{n ,} dos primeiros enteiros 1,2,3,....,n. Ou máis suxerententemente, trataba das permutacións a₁, a₂,a₃, ..., a_i ,....de todos os números naturais. Concretamente dábanse resultados sobre o mínimo común múltiplo  e o máximo común divisor de dous elementos consecutivos nesas permutacións. Un dos teoremas cualificábano os propios autores de pobre resultado. Di o seguinte:
Dada unha permutación de todos os naturais a₁, a₂,a₃, ..., a_i ,....:
$$\bar { \underset { i }{ lim }  } \frac { \left[ { a }_{ i },{ a }_{ i+1 } \right]  }{ i } \ge \frac { 1 }{ 1-log2 } \simeq 3,26$$
Certamente é difícil imaxinar unha permutación  na que este límite fique dentro do ámbito da finitude.

Linguas na arañeira de internet

A arañeira web é un enleado mundo que nos ofrece retratos de como tecemos tamén as nosas redes lingüísticas. Segundo o estudo presentado no Research Blog a maior parte das páxinas ligan con outras do mesmo web. En todo caso, o resto das ligazóns van a outros webs da mesma lingua. No entanto hai un pequeno pero significativo número de ligazóns que van a webs doutras linguas. Este último tipo de vectores son os estudados e representados nestes gráficos construídos a modo de grafos orientados.

Os grafos non son outra cousa que unha colección de puntos (chamados vértices), conectados ou non, mediante liñas (os matemáticos chámanlle arestas). Chámanselle grafos orientados ou dirixidos a aqueles nos que as arestas teñen unha dirección que vai dun nodo de saída a outro de chegada. No que temos aquí arriba  aparecen representadas todas as linguas que teñen polo menos 100.000 webs , entre elas, a galega que pode apreciarse máis claramente nesta ampliación. O ano estudado é o 2008 e neste gráfico non aparece a lingua hexemónica na rede, o inglés. Nese momento vemos como o 3% das páxinas galegas que ofrecen direccións cara portais noutras linguas conectan con webs en portugués mentres que un 27% se dirixen cara outros en español. Os portais vascos ou cataláns amosan porcentaxes similares pero algo inferiores. Con respecto ás ligazóns cara ao inglés, o galego cun 17% sitúase no entorno dos valores medios Vía cousas d' o paco