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. 

Criptografía e maxia no Losada

Algún día tería que relatar as miñas desventuras no CAP (Curso de Adaptación Pedagóxiga), un curso que xogaba aproximadamente o mesmo papel que o Máster de Profesorado actual. Só comentarei que, cando me faltaba só unha sesión para rematalo, abandoneino, farto.  Efectivamente, estaba farto de ver como quen presumiblemente tiña que dar directrices sobre orientacións didácticas actuaba como un terrorista pedagóxico. Recordo unha materia levada por dous profesores, un home gordo e unha muller fraca. Impartían clase xuntos. Pasaban todo o tempo discutindo. Iso podería estar ben se fose algo pensado e preparado. Non era o caso.  Nunha ocasión pasaran toda a sesión dándolle voltas a como tratar aos rapaces zurdos. Se conviña, ou non, forzalos a escribir coa man dereita. Non era esta un tema que houbese que tratar no CAP, só foi unha ocorrencia máis desa parella infame de profesores. Desde aquela quedoume a impresión que unha clase levada en parella tiña que ser necesariamente un fracaso. Non é así. Isto demostráronolo Nicanor Alonso e Miguel Mirás o pasado venres 16/05/2025 na charla que viñeron impartir ao IES Antón Losada Diéguez ao alumnado de 1º de Bacharelato. O segredo do éxito dunha clase en tándem? O mesmo que o dunha clase impartida por unha persoa soa: traballo e preparación. 

O título da charla era "Historias e segredos da criptografía". Trataron temas como o da escritura xeroglífica, a reixa de Cardano, os acrósticos, a escítala espartana, o cifrado César ou o máis sofisticado de Vigenére,  sempre solicitando a participación e complidade do alumnado. Nicanor e Miguel repartiron unha roda como a da imaxe, que nos permitiu encriptar unha mensaxe seguindo as directrices dos dous últimos sistemas de cifrado. 

Examinaron moitos máis tópicos e sempre dunha forma clara e coordinada. Claro que, no canto de ser explicados en parella, tal e como o fixeron eles, case todos podían ter sido tratados por un só conferenciante. Comento isto porque un dos capítulos necesitaba de dúas persoas para poder desenvolvelo. A min foi o que máis me sorprendeu e agradou. Trátase do truco das 5 cartas de Cheney, asunto do que, por certo, xa se ocupara no seu día Jota nesta entrada, O mellor truco de cartas. O enunciado promete. Vexamos como se desenvolveu.

As cinco cartas de Cheney

Un dos dous conferenciantes marchou da sala; chamémoslle  mago. O outro, chamémoslle axudante,  pediu a un voluntario que escollera cinco cartas dunha baralla francesa completa (52 cartas, 13 de cada un dos paus, a saber: corazóns ♡ , diamantes ♢, picas ♠ e trevos ♣). Entón o axudante colocou catro desas cartas sobre unha mesa e deixou a quinta ao final, virada cara abaixo.

Cando volveu o mago e veu esas cartas sobre a mesa, concentrouse un momento e adiviñou cal era a carta que estaba boca abaixo.

Estaba claro que elaboraran un código para identificar as cartas pois diso trataba a conferencia. Pero teñamos presente que non poden saber previamente cales son as cartas que se van escoller polo que o código debería estar montado sobre a ordenación das cartas. Está claro que podemos establecer unha orde entre todas elas. En primeiro lugar, os números (do 1 ao 13) axudan moito. E que pasa se dúas cartas teñen o mesmo valor numérico? Daquela basta con que o mago e o seu axudante establezan unha orde dos paus. Podería ser, por exemplo, a orde do abecedario pola primeira letra: corazóns ♡ < diamantes ♢< picas ♠ < trevos ♣. Con todo, hai un problema, as $4$ cartas que quedan visibles só poden ordenarse de $4!=24$ formas distintas. 

Para salvar esta dificultade hai que aproveitar todas as vantaxes que nos dá o desenvolvemento do truco. Teñamos presente que é o axudante quen escolle a carta que se coloca boca abaixo. Polo principio do pombal, dadas $5$ cartas, é seguro que vai haber polo menos dúas do mesmo pau. Isto permite que o axudante escolla dúas cartas do mesmo pau e coloque unha cara abaixo e a outra pode colocala na primeira posición. No noso exemplo a primeira carta era o rei de trevos, velaí que a carta a adiviñar será tamén un trevo. Agora quédannos outras tres cartas visibles que nos deben permitir identificar o número da carta oculta. Outra vez, se ordenamos esas tres cartas termos un total de só $3!=6$ posibilidades e nós necesitamos 13. Aquí é onde entra en xogo a aritmética modular. 

Facemos unha identificación do valor da carta cos números das congruencias de $\mathbb{Z}_{13}$. A diferenza entre dous destes valores nunca é maior que $6$. As cartas que escolleu o axudante eran a $J$ e o $2$ de trevos. A súa diferenza é de $4$ unidades. Ocultando o $2$ só lle ten que dicir ao seu compañeiro que debe sumarlle $4$ unidades á $J$. En aritmética modular $11+4\equiv 2 (mód 13)$. O código utilizado para indicar o número a sumar é o que explicamos de seguido. Vou identificar o $1$ co valor máis baixo das tres cartas, o $2$ co intermedio e o $3$ co maior. Daquela establezo a seguinte relación entre as $6$ ordenacións e o $6$ números que debo sumar (módulo 13) ao valor da primeira carta:

$$\begin{pmatrix} 1,2,3 & \longrightarrow 1 \\ 1,3,2 &\longrightarrow 2 \\ 2,1,3& \longrightarrow 3 \\ 2,3,1 & \longrightarrow 4 \\ 3,1,2& \longrightarrow 5 \\ 3,2,1 & \longrightarrow 6 \\ \end{pmatrix}$$

Como as tres cartas centrais son: $J$♢, $3$♠, $5$♠ vemos que a orde das cartas é: maior,  menor, intermedia que identificamos coa permutación $3,2,1$, de aí que o número a sumar é o $4$. Polo tanto o mago adiviña a carta oculta:

Principio do pombal, combinatoria e aritmética modular, todo dentro dun truco de maxia. 

Charlas científico-divulgativas

A Universidade de Vigo ofrece cada ano charlas científico-divulgativas. No seu folleto divulgativo acharemos epígrafes como os de "Ciencias da natureza", "Física e Química" ou "Economía". Aparentemente non se oferta ningunha charla de "Matemáticas". Eu aconsellaría aos centros de ensino de Secundaria buscar nese folleto os nomes de Nicanor Alonso e Miguel A. Mirás e concertar con eles unha actividade.

Matemaxia ou o decreto de plurilingüismo en evidencia

A banda de Möbius, a numeración binaria, as propiedades das mesturas por arrastre...Calquera profesor de matemáticas pode explicar sen dificultade calquera dos trucos que o mago Paco presenta neste excelente vídeo que gravaron no CEIP do Carballal (Marín). Está claro que a actividade resultou gorentosa para a rapazada que tivo a sorte de participar nela. Aprenderon matemáticas e, a un tempo, asistiron a espectáculo de maxia. 

A cara escura desta actividade non está na actividade en si, senón en que, para os absurdos parámetros da Xunta de Galicia, esta é unha actividade ilegal. Efectivamente, trátase dunha clase de matemáticas en galego, prohibida polo funesto decreto do plurilingüismo. O monstruoso do asunto sería que ésta fose a única clase en galego que este alumnado de 5º de primaria tivese en toda a súa vida escolar. Vendo un exemplo concreto do que prohíbe a Xunta é máis evidente de ata onde chega o nivel de odio á lingua galega dos gobernantes que padecemos. 

Unha vez máis, parabéns ao profesorado do CEIP do Carballal por achegaren ao alumnado unha actividade lúdica e formativa. Parabéns que fago extensivos ao mago Paco, por botar man das matemáticas nun dos seus espectáculos, ofrecendo unha nova perspectiva para o achegamento desta materia ás aulas.

O crebacabezas de Freer

Winston Freer (1910-1981) foi un mago norteamericano que argallou famosos xogos de maxia. Un deles é este que se presenta neste vídeo. Para ver a explicación do truco, que o hai, pois noutro vídeo.

Matemáticas máxicas: é un nó ou non?

Sempre gustei dos trucos de maxia. Teñen un algo transgesor moi atraínte.
Por iso sempre me causa algo de aversión a explicación dun truco... ou case sempre.
Velaquí o sorprendente truco do nó, xunto coa súa explicación. O bo do caso é que que ao final adícalle un capítulo á relación do xogo de maxia coa teoría topolóxica (matemática) de nós, e incluso fai referencia a que este aparente xogo non é unha inutilidade máis das matemáticas, pois indica que estes coñecementos poden axudarnos no estudo ao combate das bacterias, tal e como viña desenvolvido neste bonito artigo sobre a topoloxía publicado na revista Sigma.
Pero a cousa non remata aquí.

O vídeo ten relación cun libro de maxia e matemáticas no que se utilizan propiedades matemáticas para argallar os trucos, cunha explicación moi completa. Só lle botei un ollo polo aire, pero parece moi recomendable.
No libro temos un truco para obter unha suma de dez números usando unha propiedade da sucesión de Fibonacci. Noutro usa o sistema de numeración en base 3 para adiviñar dun paquete de 27 cartas, cal é a carta escollida,... e ademais podemos facer aparecer a carta no lugar/ordinal que nos indiquen.
Gorentoso, non?
Máis información: The manual of mathematical magic, illusioneering.org