luns, 18 de novembro de 2024

Problemas chegados desde Moscú. 3

Esta é a terceira e última entrada adicada a recoller problemas de Boris Kordemsky. As anteriores pódense consultar aquí e aquí.

Imos cun problema moi simple. Con todo moita xente dirá que lle faltan datos.

Un barco diésel e un hidroavión. Un barco diésel parte de viaxe. Cando está a 180 millas da costa envíase un hidroavión co correo que ten unha velocidade dez veces superior á do barco. A que distancia alcanza o barco?

O encantador do seguinte problema é que a pregunta é inesperada

En coche e a cabalo. Un mozo e un home maior saen da vila cara a cidade; un vai a cabalo e outro en coche. Pronto queda claro que se o home maior chegase tres veces máis lonxe de onde está, quedaríalle a metade para viaxar do que lle queda. E se o mozo viaxara a metade do que xa fixo, quedaríanlle tres veces máis para viaxar do que lle queda. Quen vai a cabalo?

Sei que non hai que recorrer á combinatoria para resolver a seguinte cuestión. Con todo, desde que o coñecín coloqueino entre os problemas a resolver cando trato na clase as técnicas de reconto combinatorio.

Novas estacións. Cada estación vende billetes a todas as outras estacións do percorrido. Cando se engaden algunhas estacións hai que imprimir 46 billetes adicionais. Cantas estacións se engadiron? Cantas había antes?

Teño preferencia polos problemas de matemáticas sen referencias externas. Matemáticas para estudar as propias matemáticas. Dentro deste ámbito está o estudo do propio sistema de numeración. Quizais o pouco traballo/reflexión sobre o sistema decimal, quizais a propia abstracción deste tipo de cuestións, o certo é que normalmente vólvenselle moi dificultosas ao alumnado.

Un número de cinco díxitos. Dime un número de cinco díxitos tal que se lle engades un 1 despois do mesmo é tres veces maior que se llo engades antes.

Cando un se enfronta ao seguinte enunciado cómprelle unha gran dose de imaxinación. Temos un avión, unha motocicleta e un cabalo andando dun lado para outro. O curioso é que non nos dan ningunha velocidade.

O motociclista e o xinete. Envían un motociclista desde a oficina de correos a tempo para a chegada dun avión ao aeroporto. O avión chega antes de tempo e o correo é transportado á oficina de correos a cabalo. Despois de media hora o xinete crúzase co motociclista e dálle o correo. A motocicleta volve á oficina de correos 20 minutos antes do esperado. Cantos minutos antes aterrizou o avión?

O tradutor do libro ao inglés, Albert Perry, especialista en ruso da Colgate University, fixo unha curiosa anotación ao seguinte problema:" Non hai árbores de nadal na URRS, oficialmente só os hai de aninovo". En canto ao contido, é un clásico.

Regalos de aninovo. O noso comité executivo do sindicato xestionou unha árbore de aninovo para os nenos. Despois de distribuir caramelos e galletas en paquetes de regalo, comezamos coas laranxas. Pero decatámonos de que se poñemos 10 laranxas por paquete, un paquete só terá 9, se colocamos 9, un paquete só derá 8; se poñemos 8, 7; e así sucesivamente ata dúas laranxas por paquete cun paquete con só 1. Cantas laraxas temos? 

Para entender os comentarios ao seguinte problema cómpre ler antes o enunciado.

Unha suma palindrómica. Este problema aínda non foi resolto. Suma a un enteiro o propio número invertido. Engade á suma o invertido da suma. Continúa ata que a suma sexa un palíndromo (que se le igual de esquerda a dereita que de dereita a esquerda) $$\begin{matrix} 38 & & 139 & & 48017 & & \\ \underline{83} & & \underline{931} & &\underline{71084} & & \\ 121& &1170 & &119101 & & \\ & &\underline{0711} & & \underline{101911 }& & \\ & & 1881 & & 221012 & & \\ & & & & \underline{210122} & & \\ & & & & 431134 & & \\ \end{matrix} $$

Pode que sexan necesarios moitos pasos. (de 89 a 8.813.923 precísanse 24 pasos). Unha hipótese é que calquera enteiro produce, antes ou despois, un palíndromo. Segundo Kordemsky, un traballador industrial de Riga chamado P. R. Mols, decatouse de que o número 196, despois de setenta e cinco pasos, non produce un palíndromo. Kordemsky pídenos que no canto de continuar a partir do número de 36 díxitos da septuaxésima quinta suma, intentemos refutar ou demostrar a conxectura mediante un razoamento.

Martin Gardner comenta que xa se realizaran daquela miles de sumas a partir do 196 e que non se achara ningún palíndromo. Tamén informa que a conxectura foi demostrada falsa para os números binarios. Sospéitase que hai números que non darán lugar a un palíndromo. A eses números chámaselles números de Lychrel. En concreto 196 é un candidato destacado para ser un número de Lychrel. É curioso que este tipo de números teñan nome, aínda que non se sabe se realmente existe algún.

luns, 11 de novembro de 2024

Problemas chegados desde Moscú.2

Unha explicación de Perelman

Hoxe en día cando escoitamos o apelido Perelman pensamos inmediatamente en Grigori Perelman (1966-), o matemático ruso que resolveu a conxectura de Poincairé. No entanto, hai un par de décadas o usual sería asociar ese apelido con Yákov Perelman (1882-1942), un famoso divulgador da ciencia que morrería no asedio a Leningrado durante a II Guerra Mundial. 

Nun dos seus libros, Aritmética recreativa, explícanos o método ruso para facer produtos. Faino cun exemplo. Se quixermos calcular o produto de $32\cdot13$ procederiamos da seguinte maneira. En cada paso dividimos o factor da esquerda por $2$ e multiplicamos o da dereita por $2$. Así o produto non varía.

$$\begin{matrix} 32\cdot 13 \\16\cdot 26 \\8\cdot 52 \\4\cdot 104 \\2\cdot 208 \\1\cdot 416 \end{matrix}$$

Velaí que o resultado sería $32\cdot13=1\cdot 416=416$. Claro que, calquera ve enseguida o problema. Neste caso $32$ é unha potencia de $2$ polo que podemos dividilo unha e outra vez pola metade. Pero que pasaría se na columna da esquerda temos un número impar? Yákov Peremal tamén explica como proceder neste caso. Cada vez que teñamos un número negativo, restámoslle $1$; agora podemos dividir por $2$ sen problema. En compensación teremos que sumar todos os números da dereita que teñan un impar á súa esquerda. Para facelo máis sistemático e fácil, tachamos todos os produtos que presenten á esquerda un número par. Poñamos que agora queiramos multiplicar $19\cdot17$:

$$\begin{matrix} 19\cdot 17 \\9\cdot 34 \\4\cdot 68 \\2\cdot 136 \\1\cdot 272 \end{matrix}$$

O resultado será $17+34+272=323$. Por que temos que proceder deste xeito? Perelman tamén nolo explica. Resulta que ao restar $1$ estamos eliminando algúns valores, necesarios para obter o produto final. Todo fica claro cando presentamos as seguintes operacións:

$$\begin{matrix}19\cdot17=\left ( 18+1 \right )\cdot17=18\cdot17+17\\ 9\cdot 34=\left ( 8+1 \right )\cdot 34=8\cdot34+34\end{matrix}$$

Ao restar eses uns estamos subtraendo tamén eses restos, $17$ e $34$; esa é a razón de porque debemos sumalos ao final.

Máis problemas de Kordemsky

Na anterior entrada presentárase unha pequena escolma dos Enigmas de Moscú de Boris Kordemsky. Imos seguir tirando dese fío. Algunha das cuestións presentadas por Perelman teñen un sabor moi semellante ás de Kordemsky. En especial a seguinte, da que, sen que serva de precedente, darei tamén a solución.

O volume dunha botella. Se unha botella parcialmente chea de líquido, ten un cu redondo, cadrado ou rectangular, podes saber o seu volume só cunha regra? Non podes engadir sin sacar líquido.

Está claro que o volume total da botella virá dado pola suma do volume que ocupa o líquido xunto co da parte sen el. Creo que non cómpre dicir nada máis. 

O trato pouco reflexivo cun tópico tan básico como o das porcentaxes dá lugar a interpretacións bárbaras. É habitual escoitar, non xa a rapaces, senón a ilustres licenciados, que se aumentamos unha cantidade nun 20% e despois facemos unha rebaixa do 20%, obtemos o valor inicial.

Podes aforrar o 100%? Un invento aforra o 30% do combustible, outro un 45% e un terceiro un 25%. Se usas todos estes inventos a un tempo, podes aforrar o 100% ? En caso contrario, cal é a porcentaxe de aforro?

Nalgúns casos Kordemsky non só presenta un problema senón que fai unha pequena digresión para chamar a atención sobre algúns procesos propios das matemáticas. Continuamos con porcentaxes.

Falsa analoxía. Os descubrimentos científicos fanse a veces mediante analoxía. A analoxía tamén ten lugar nas matemáticas, pero tamén existe a falsa analoxía.

40 é 8 unidades maior que 32. 40 é un 25% maior que 32.

32 é 8 unidades menor que 40. 32 non é un 25% menor que 40. Cal é a porcentaxe correcta?

a) Supón que os teus ingresos mensuais aumentan un 30%. En canto aumenta o teu poder adquisitivo?

b)Supón que os teus ingresos mensuais non cambian. No entanto, os prezos baixan un 30%. En canto aumenta o teu poder adquisitivo?

c)Cando unha tenda de libros de segunda man fai unha rebaixa do 10% do prezo, obtén unha ganancia do 8% por cada libro vendido. Cal era o beneficio antes da rebaixa?

d)Se un obreiro metalúrxico reduce o seu tempo por peza nun p%. Canto aumenta a súa produtividade?

Un deses enunciados que nunca verás nun libro de texto. Trátase de traballar o volume pero non preguntan polo volume. A última pregunta incide nun dos procesos máis importantes dentro das matemáticas, o da xeneralización.

Que caixa pesa máis?. Unha caixa cúbica contén 27 bólas grandes congruentes; a súa xemelga contén 64 bólas congruentes máis pequenas. Todas as bólas están feitas do mesmo material. Ambas caixas están completamente cheas. En cada caixa, cada capa ten o mesmo número de bólas e as bólas exteriores de cada capa tocan os lados da caixa. Que caixa pesa máis? Intenta con outros números, pero que sexan sempre cubos. Escribe unha conclusión xeral.

O seguinte enunciado ten o atractivo de estar redactado como unha pequena lenda. Trata o tema do pacto co demo, algo que, como todos sabemos, nunca debemos facer. É tamén un deses problemas que convén resolver "ao revés"

O folgazán e o demo. Un folgazán expresa a súa ansia por facerse rico e de súpeto aparéceselle o Diabo quen lle di: "Ben, o traballo que teño para ti é fácil, e serás rico. Ves a ponte? Crúzaa e dobrareiche o diñeiro que tes agora mesmo. De feito, cada vez que a cruces volveri a dobrarche os cartos.

"Non pode ser!" contestou o folgazán

"Só hai unha condición. Xa que son tan xeneroso debes darme 24 € despois de cada cruce".

O folgazán acepta. Cruza a ponte e conta os seus cartos... Miragre! Era o dobre.

Dálle 24 € ao Diabo e volve a cruzar outra vez. Dóbrase o seu diñeiro e paga outros 24€, cruza unha terceira vez. O seu diñeiro volve a duplicarse pero agora só ten 24€ e tan que darllos ao Diabo que desaparace entre gargalladas.

Cando un se enfronta a un enunciado cómpre que o entenda moi ben. Iso significa, entre outros aspectos, que debe ter ben asimilados os conceptos e as relacións que se determinan entre os distintos aspectos en xogo. No seguinte problema xira arredor do cálculo dunha media de velocidades de trancrición dun manuscrito. Debemos ter claro que a velocidade mídese a respecto do tempo, non a respecto do número de páxinas, como enganosamente pretende convencernos Vera.

Vera pasa un manuscrito a máquina. Vera recibe da súa nai o encargo de pasar a máquina un manuscrito. Vera indica que fará unha media de 20 páxinas por día.

A primeira metade fainas con pereza, 10 páxinas diarias. Para recuperar o tempo perdido fai a segunda metade a 30 páxinas por día.

"Ves?, fixen unha media de 20 páxinas por día". Conclúe Vera. "A media de 10 e 30 é 20"

"Non, non é certo" di a súa nai.

Quen ten a razón?

Dicimos que estes problemas chegaron de Moscú porque alí os publicou Kordemsky. En realidade son universais. O seguinte problema con pequenas variantes aparece nalgún libro de Adrián Paenza. 

Que tal vas de enxeño?. Unha lancha sae da beira A ao tempo que outra sae da beira B; móvense polo lago a unha velocidade constante. Encóntrase por vez primeira a 500 metros de A. Continúan o seu camiño, dando a volta na beira oposta. Encóntranse por segunda vez a 300 m. de B. Cal é a lonxitude do lago e cal é a relación entre as velocidades das lanchas? 

Na seguinte entrada remataremos esta serie de problemas de Boris Kordemsky.

luns, 4 de novembro de 2024

Problemas chegados desde Moscú.1

O descoñecemento doutras culturas ou doutras linguas empequenece o noso mundo. Hai factores que nos afastan de realidades distintas á nosa. Un deles pode ser o alfabeto. Unha portada dun libro como o da figura 1 pode significa unha barreira insalvable. Hai outros muros aínda máis infranqueables. Durante a Guerra Fría houbo un bloqueo total a todo o que se elaborase alén do telón de aceiro. Así, un libro de matemática recreativa editado no 1954 cun enorme éxito na URSS non foi coñecido no occidente ata 1972, que foi traducido ao inglés e publicado cunha introdución de Martin Gardner. O título orixinal, Математическая смекалка pasou a ser The Moscow Puzzles. 359 Mathematical Recreations. O autor Boris Kordemsky (1907-1999), un profesor de matemáticas moscovita, editaría máis libros do mesmo estilo. Tamén hai unha versión en español; neste caso a editorial Gedisa cortou o texto en dúas partes: Los enigmas de Moscú e Un elefante y un mosquito.

Vou compartir algúns dos problemas de Kordemsky. 

O libro Mate-glifos (Xerais, 2018) dos profesores da Universidade de Vigo Nicanor Alonso e Miguel MIrás, está elaborado arredor dos símbolos matemáticos. Os símbolos son importantes, incluso poden ser o cerne dun problema.

Distintas operacións, mesmo resultado. Dados un par de 2, o símbolo "+" pode cambiarse por "x" sen cambiar o resultado: $ 2+2=2\times 2$. A solución con tres números tamén é sinxela: $ 1+2+3=1\times 2\times 3$. Pídese a resposta para catro números. E para cinco?

A central eléctria de Tsimilyansk está situada no río Don. Rematada no 1954 considérase como un dos grandes proxectos de construción da época comunista.  A imaxe reflicte a súa icona oficial. Esta central aparece como identificador próximo ao posible lector do seguinte enunciado que presenta dunha forma pouco habitual un problema sobre a media.


Para a central eléctrica de Tsimilyansk. Unha fábria de equipos de medición ten un encargo urxente da célebre central eléctrica de Tsimlyansk. A fábrica conta cunha brigada de dez excelentes traballadores: o capataz (un home maior con experiencia) e 9 xoves diplomados de formación profesional.

Cada un dos 9 xoves traballadores produce 15 pezas de medición ao día mentres que o seu xefe fai 9 máis que a media dos dez traballadores. Cantos instrumentos de medición produce a brigada diariamente?

A primeira vez que lin o problema, fíxeno a todo correr e, en consecuencia lino mal. Unha vez visto o primeiro parágrafo pensei que preguntaría cal é a suma dos primeiros mil millóns de números. Non é esa a pregunta.

De 1 a 1.000.000.000. Cando o acreditado matemático alemán Karl Friederich Gauss(1777-1855) tiña nove anos, pedíronlle que sumara todos os números enteiros do 1 a 100. Sumou rapidamente o 1 co 100, o 2 co 99, e así sucesivamente ata un total de 50 pares de números, todos eles de suma 101. A resposta foi $50\times 101=5050$.

Agora acha a suma de todos os díxitos dos números enteiros de 1 a 1.000.000.000. Isto quere dicir todos os díxitos en todos os números, non a suma de todos os números por si mesmos.

Eu teño unha certa aversións aos deportes e especialmente, polo que representa, ao fútbol. Velaí que, nun principio, non sería do meu gusto un problema enmarcado neste tema. O que si me pareceu moi curiosa foi a forma de presentar o problema, é realmente estraña, mediante unha conversión kafkiana. No libro non vén a imaxe, nin  tampouco se aclara que o que se debe establecer é a relación que debe haber entre os raios das dúas pelotas.

O pesadelo dun afeccionado ao fútbol. A un afeccionado ao fútbol, triste pola derrota do seu equipo, cústalle durmir. No soño, un porteiro practica nunha gran habitación amoblada, lanzando unha pelota contra a parede e despois atrapándoa coas mans. Pero o porteiro cada vez faise máis pequeno e despois transfórmase nunha pelota de pimpón mentres que a pelota de fútbol se incha ata converterse nunha gran bóla de ferro forxado. A bóla de ferro xira violentamente intentando aplastar a pelota de pimpón que se move por todas partes desesperadamente. Pode a pelota de pimpón encontrar un lugar seguro sen separarse do chan?

Dúas pelotas

O seguinte é un problema simple e curioso. Todo un reto para un alumno de 1º da ESO. Un exemplo de como as matemáticas en si mesmas son interesantes. Non precisamos buscar enunciados trapalleiros que introduzan a vida cotiá con calzador e sen xeito.

Fraccións interesantes. Se ao numerador e ao denominador da fracción $1/3$ lles sumamos o seu denominador, $3$, a fracción duplícase.

Acha unha fracción que sexa o triplo cando o seu denominador se sume ao seu numerador e ao seu denominador; acha outra que sexa o cuádruplo.

De seguido unha desas cuestións aritméticas sobre velocidades que dan moito xogo. Claro que non se trata do típico problema de que un tren parte de A a 90 km/h....

Aforraríase tempo? Ostap volve a casa desde Kiiv. Fixo en bici a metade do camiño quince veces máis rápido que a pé. A segunda metade montou nun carro de bois. Camiñando pode ir o dobre de rápido. Aforraríase tempo se fixera todo o camiño a pé? Canto tempo?

Un enunciado distinto ao anterior, pero os fundamentos son os mesmos:

O sarxento propón un problema. O sarxento Semochkin propón o seguinte problema aos soldados exploradores. Digamos que dous de vós cubrides a mesma distancia. O primeiro corre a metade do tempo e camiña a outra. O segundo corre a metade do percorrido e camiña o resto. Ningún dos dous camiña ou corre máis rápido que o outro. Se primeiro camiñan e despois corren, quen chega primeiro?

Na seguinte entrada continuaremos con algunha outra achega deste moscovita.

martes, 15 de outubro de 2024

Paridade e equilibrio

Paridade e equilibrio son conceptos semellantes pero non intercambiables. Para xustificar a imposición do decreto 79/2010, o de redución e prohibición de uso do galego no ensino, apelouse a un discurso no que a idea de equilibrio xogaba un papel importante. O alegato consistía en reivindicar que no ensino non había un equilibrio porque o decreto anterior primaba, tal e como recomendaba o PXNL, o uso do galego. Sería máis dificultoso facer o mesmo empregando a idea de paridade. Por que? Inmediatamente todos pensamos que o contrario de equilibrio é desequilibrio, unha situación non desexable. Paridade non ten un antónimo tan evidente. Aínda diría máis, o que procuraba o decreto 79/2010 era xustamente ese antónimo: a desigualdade. Evidentemente, reivindicar a desigualdade das linguas non parecía un discurso con expectativas mercadotécnicas. En efecto, o decreto 79/2010 non se sustenta en ningún criterio sociolingüístico; todos os seus criterios son de merchandising tóxico.

No eido das matemáticas sempre esperamos movernos por vías claras e sen ambigüidades. Imre Lakatos facía reconstrucións racionais da historia das matemáticas nas que o motor era a expurgación desas ambigüidades. Isto non significa que as matemáticas estean exentas de sorpresas e, ao contrario do que sucede na sociolingüística, as sorpresas nas matemáticas son sempre agradables. Comezaremos cunha cuestión que, nun principio, non ten nada que ver coa paridade.

Paridade

Os libros do matemático canadiano Ross Honsberger (1929-2016) son unha colección de xemas preciosas. Como exemplo, collamos Ingenuity in Mathematics (MAA 1970), do que hai unha edición en castelán, El ingenio en las matemáticas (La Tortuga de Aquiles 1994). Serviríanos calquera bocado deste libro. Nesta ocasión escollemos unha das cinco curiosidades aritméticas que presenta no capítulo 10. Tratábase dunha proposta da década dos anos 30 do século XX que se lle atrirbuía Enrico Ducci (1864-1940), un profesor de secundaria italiano que tamén exerceu a docencia no Colexio Militar de Nápoles. 

Pensemos en catro números naturais, por exemplo $(15,10,20,24)$ agora calculemos a diferenza, en valor absoluto, de cada par de números consecutivos considerando que o último número e o primeiro tamén son consecutivos. Repitamos o proceso unha e outra vez:

$$ \left ( 15,10,20,24 \right )$$ $$ \left ( 5,10,4,9 \right )$$ $$ \left ( 5,6,5,4 \right )$$ $$ \left ( 1,1,1,1 \right )$$ $$ \left ( 0,0,0,0 \right )$$
Honsberger presentaba o procedemento dunha forma máis agradable á vista. Pedíanos que colocásemos os catro primeiros valores arredor dunha circunferencia e que despois obtivésemos o resto das cuaternas cíclicas sobre circunferencias cada vez maiores tal e como se mostra no seguinte diagrama:

Este proceso é tan simple que se pode presentar nunha aula de primaria, basta con saber restar. Ademais ten a vantaxe de que podemos experimentar con el. Se xogamos un pouco con distintas cuaternas iniciais entenderemos por que Ducci se preguntou se sempre se acabaría na cuaterna $(0,0,0,0)$. Efectivamente, non importa cal sexa a cuaterna inicial, sempre acabaremos nunha cuaterna de ceros. Honsberger ofrece unha explicación demostrando que en catro pasos o maior dos catro valores vai reducirse. Isto implicará que nun número finito de pasos o maior valor será cero, polo tanto todos o serán. Se temos unha configuración sen ningún cero fica claro que o maior dos catro valores se verá reducido no seguinte paso. Entón Honsberger pasa a estudar os casos nos que haxa un, dou ou tres ceros e demostra esa redución en cada un dos casos. 
O mesmo problema xa aparecía nun libro do autor ruso Boris Kordemsky (1907-1999). O libro, editado no 1954, tiña por título Математическая смекалка. Foi un best-seller do que se venderon centos de miles de exemplares. A iniciativa de Martin Gardner foi traducido ao inglés no ano 1972 baixo o título de The Moscow Puzzles. Tamén hai unha versión en español; neste caso a editorial Gedisa cortou o texto en dúas partes: Los enigmas de Moscú e Un elefante y un mosquito. A demostración que ofrece Kordemsky da conxectura de Ducci é marabillosa. Imos debullala. 
Figura 2
En primeiro lugar pensemos na equivalencia entre distintas cuaternas polo feito de seren cíclicas. Observemos a figura 2; seguindo o sentido de xiro das agullas dun reloxo decatarémonos de que as seguintes cuaternas son equivalentes:
$ \left ( a,b,c,d \right )\equiv \left ( b,c,d,a \right )\equiv \left ( c,d, a, b \right )\equiv \left ( d,a,b,c\right )$ 
Se consideramos o sentido de xiro contrario, aínda teremos outras tantas equivalentes ás anteriores:
$ \left ( d.c,b,a\right )\equiv\left ( c,b,a,d \right )\equiv \left ( b,a,d,c \right )\equiv \left ( a,d,c,b\right )$
Agora faremos unha análise un tanto inesperada. Fixarémonos se os números son pares ou impares (p/i). Hai un total de $2^4=16$ formas de construír unha cuaterna utilizando dous elementos ($p/i$) pero moitas delas son equivalentes polo que só hai 6 cuaternas esencialmente distintas:
$v_{1}=\left ( p,p,p,p\right )$
$v_{2}=\left ( p,p,p,i\right )\equiv \left ( i,p,p,p\right )\equiv\left  ( p,i,p,p\right )\equiv\left ( p,p,i,p\right ) $
$v_{3}=\left ( p,p,i,i\right )\equiv \left ( i,p,p,i\right )\equiv \left ( i,i,p,p\right )\equiv \left (p, i,i,p\right )$
$v_{4}=\left ( p,i,p,i\right )\equiv\left ( i,p,i,p\right )$
$v_{5}=\left ( p,i,i,i\right )\equiv\left ( i,p,i,i\right )\equiv\left ( i,i,p,i\right )\equiv\left (i,i,i, p,\right )$
$v_{6}=\left ( i,i,i,i\right )$
E xan van alá as 16 posibilidades. Agora comprobaremos que, en como moito 4 pasos, obteremos unha cuaterna de pares. Chamémoslle $A_{0}$ á configuración inicial e apliquémoslle as regras de xogo para obter unha sucesión de cuaternas cíclicas. Que pasa se comezamos por $v_{2}$?
$A_{0}=\left ( p,p,p,i\right )=v_{2}$
$A_{1}=\left ( p,p,i,i\right )=v_{3}$
$A_{2}=\left ( p,i,p,i\right )=v_{4}$
$A_{3}=\left ( i,i,i,i\right )=v_{6}$
$A_{4}=\left ( p,p,p,p\right )=v_{1}$
Non só observamos que en 4 pasos pasamos de $v_{2}$ a $v_{1}=\left ( p,p,p,p\right )$, senón que tamén desde $v_{3}$, $v_{4}$ e $v_{6}$ chegamos a $v_{1}$ incluso en menos pasos. Que pasa con $v_{5}$?. Vexámolo:
$A_{0}=\left ( p,i,i,i\right )=v_{5}$
$A_{1}=\left ( i,p,p,i\right )=v_{3}$
$A_{2}=\left ( i,p,i,p\right )=v_{4}$
$A_{3}=\left ( i,i,i,i\right )=v_{6}$
$A_{4}=\left ( p,p,p,p\right )=v_{1}$
Efectivamente, en 4 pasos tamén pasamos de $v_{5}$ a $v_{1}=\left ( p,p,p,p\right )$
Eses catro números pares de $A_{4}$ poden ser disintos. Renomémolos: $A_{4}=\left ( p_{1},p_{2},p_{3},p_{4}\right )$ e consideremos a cuaterna das súas metades $B_{4}=\left ( \frac{p_{1}}{2}, \frac{p_{2}}{2}, \frac{p_{3}}{2}, \frac{p_{4}}{2}\right )$. Fagamos agora un paso máis; pensemos como serán $A_{5}$ e $B_{5}$.
O primeiro elemento de $A_{5}$ será $\left|p_{1}-p_{2}\right| $ e o primeiro elemento de $B_{5}$ será $\left|\frac{p_{1}}{2} -\frac{p_{2}}{2}\right|=\frac{\left|p_{1} -p_{2}\right|}{2}$. Velaí que os elementos de $B_{n}$ serán sempre a metade dos elementos de $A_{n}$.  $B_{8}$ será unha cuaterna de pares que ademais serán as metades dos elementos da cuaterna $A_{8}$. Entón podemos asegurar que $A_{8}$ estará conformado por múltiplos de $4$. Repetindo o proceso teremos que a cuaterna $A_{12}$ estará conformada por múltiplos de $8$. En xeral os elementos de $A_{4n}$ serán múltiplos de $2^{n}$.
Sexa $x$ o maior número de $A_{0}$. En ningunha fila pode haber un número maior que el. Pero, dado $x$ haberá algún enteiro $n$ tal que $x<2^{n}$. Sabemos que todos os elementos da cuaterna $A_{4n}$ son múltiplos de $2^{n}$. Velaí que non quede outra que $A_{4n}=\left ( 0,0,0,0\right )$
É natural cuestionarse que é o que sucede se no canto de grupos de 4 números aplicamos o mesmo proceso de Ducci a n-tuplas. En cada paso os valores de cada fila son sempre menores ou iguais á anterior. Ademais, dada unha n-tupla inicial só hai un número finito de n-tuplas que o xogo de Ducci pode producir. En consecuencia o proceso ou ben remata cunha n-tupla de ceros, ou ben acaba xerando un bucle. 
O caso $n=2$ é trivial, calquera configuración inicial chega en dous pasos a $\left ( 0,0\right )$. 
Cando $n=3$ caeremos en repeticións do tipo $\left ( 0,1,1 \right )\rightarrow \left ( 1,0,1 \right )\rightarrow \left ( 1,1,0 \right )\rightarrow \left ( 0,1,1 \right )$. 
A 5-tupla $\left ( 0,0,0,3,3 \right )$ repítese despois de 15 pasos. 
A 6-tupla $\left ( 1,2,1,2,1,0 \right )$ pronto se anula: $\left ( 1,2,1,2,1,0 \right )\rightarrow \left ( 1,1,1,1,1 \right )\rightarrow\left ( 0,0,0,0,0,0 \right )$
As n-tuplas de lonxitude $n=2^m$ acaban anulándose. Como vimos, as doutras lonxitudes teñen comportamentos variables.

Equilibrio
No anterior razoamento acabamos de traballar con restras binarias como $\left ( i,p,p,i\right )$ e ben sabemos que tanto ten escribir $p/i$ como $0/1$ ou $+/-$.
No ano 1963 o matemático polaco Hugo Steinhaus (1887-1972), no libro One Hundred Problems in Elementary Mathematics (Basic Books, 1964) propón varios problemas dos que non se coñecía a solución. Un deles, "signos máis e menos" ten unha apariencia inocua. A primeira versión do enunciado era aproximadamente a seguinte:

Triángulo de Steinhaus. Construímos un triángulo de signos $+$ e $-$ colocando unha primeira fila con $n=7$ elementos. As seguintes foron elaboradas de forma que debaixo de cada par de signos iguais aparece un $+$ e debaixo de cada par de signos distintos aparece un $-$. Observamos que no triángulo hai 14 signos $+$ e 14 signos $-$, polo que diremos que este é un triángulo equilibrado. Será posible elaborar un triángulo equilibrado cunha primeira fila de $12$ signos?  E de $n$ signos?

Un triángulo de lonxitude $n$ terá $N=\frac{n\left ( n+1 \right )}{2}$ signos. Para podermos falar de triángulos equilibrados $N$ terá que ser par, pois debe haber $\frac{N}{2}$ signos de cada tipo. Polo tanto $n\left ( n+1 \right )$ debe ser divisible por $4$. Pero isto só é posible se $n$ ou $n+1$ tamén o son. De aí que o problema de Steinhaus se reduza a establecer se é posible elaborar un triángulo de Steinhaus equilibrado cando $n\equiv 0, 3 (mód 4)$. A cuestión tardou en ser resolta 9 anos. Heiko Harborth estudou en profundidade estas estruturas. Entre outras cousas demostrou que un triángulo de Steinhaus non só se pode ler "de arriba abaixo", senón que visto desde cada un dos outros dous lados tamén é un triángulo de Steinhaus. Ademais, agás simetría, podemos ler cada lado en dous sentidos, de aí que se achamos un triángulo equilibrado, inmediatamente podemos dar outras 5 solucións. No 1972 Harborth demostrou que habería triángulos equilibrados para todas as lonxitudes posibles.

venres, 4 de outubro de 2024

O teorema de Svéd-Vázsonyi

Novo artigo de Andrés Ventas

O principio do Pombal

O principio do Pombal di que se temos $n$ buratos nun pombal e $n+1$ pombas daquela nalgún burato hai máis dunha pomba. Nunca souben para que podía servir algo tan obvio, ultimamente quixen profundar algo máis e deime conta que a sustanza deste principio reside en como podemos enfocar os problemas para poder usalo e así transformamos problemas nada evidentes en problemas cunha demostración moito simple. Un caso que me fascina é o teorema que se atribúe a Marta Svéd e Andrew Vázsonyi. Trata sobre secuencias aleatorias e divisivilidade.

Teorema de Sved-Vázsonyi

Sexan os enteiros $a_1, a_2, \cdots, a_n$, que poden mesmo estar repetidos. Daquela hai un subconxunto de elementos consecutivos desa secuencia $a_k, a_{k+1}, \cdots, a_l$ tal que a suma $a_k + a_{k+1} + \cdots, a_l$ é un múltiplo de $n$.

Exemplo

Mais como pode ser tal cousa? Se eu apaño $n$ números e os sumo poden ser múltiplos de calquera cousa, eu que sei, sumarán un múltiplo de $17$ ou de $3015$ ou de $2$, como que haberá unha desas sumas que sexa división exacta por $n$? non o vexo. A ver: $\{3, 7, 1, 4, 1, 1\}$ temos $n=6$ e imos probrar o máis simple, sumas consecutivas desde o primeiro: $\{0, 3, 10, 11, 15, 16, 17\}$, mmm... ningunha é divisíbel por $6$, desde o segundo $\{0, 7, 8, 12, \cdots \}$ cazado !! $7 + 1 + 4$ é múltiplo de $6$.

Demostración

Sexa $S=\{0, 1, \cdots, n\}$ e $R=\{0, 1, \cdots, n-1\}$ e consideremos o mapa $f: S \rightarrow R$ determinado polo residuo de $f(m)=a_1 + \cdots + a_m$ módulo $n$. Polo principio do pombal temos $f(k)=f(l)$ para algún $k \lt l$ en $S$ e por tanto

$$ \begin{equation} \sum_{i=k+1}^{l} a_i = \sum_{i=1}^{l} a_i - \sum_{i=1}^{k} a_i \end{equation} $$ faise cero módulo $n$. O subconxunto $a_k, a_{k+1}, \cdots a_l$ ten a propiedade procurada, a súa suma é múltiplo de $n$.

Exemplo aplicando a demostración

Seguindo a demostración agora é moito simple obter o subconxunto de elementos consecutivos cuxa suma é divisíbel polo número total de elementos. Para $\{3, 7, 1, 4, 1, 1\}$ con sumas parciais $\{0, 3, 10, 11, 15, 16, 17\}$ os residuos entre $6$ son $\{0, 3, 4, 5, 3, 4, 5\}$, vemos que hai dous residuos $3$ e dous $4$ e dous $5$, polo principio do pombal debe haber alomenos $2$ pombas no mesmo burato, pero pode haber máis (se hai outros buratos baleiros). Así temos:
  1. entre os dous $3$: $7+1+4 = 12$.
  2. entre os dous $4$: $1+4+1 = 6$.
  3. entre os dous $5$: $4+1+1 = 6$.

Vexamos outro exemplo ao chou.

Para $n=9$ con $\{2, 8, 4, 1, 19, 17, 2, 3, 12\}$.

Sumas consecutivas $\{0, 2, 10, 14, 15, 34, 51, 53, 56, 68\}$.

Residuos módulo $9$, $\{0, 2, 1, 5, 6, 7, 6, 8, 2, 5\}$.

E seguindo a demostración:

  1. de residuo 2 a 2 temos $56 - 2 = 54 = 9 \cdot 6$.
  2. de 6 a 6 temos $19 + 17 = 36 = 9 \cdot 4$.
  3. de 5 a 5 temos $68 - 14 = 54 = 9 \cdot 6$.

Fascinante!

Bibliografia

  1. Vincent Gélinas, The Pigeon-Hole Principle and Double Counting,

mércores, 18 de setembro de 2024

Acurtar o cálculo do inverso multiplicativo modular

Presentamos un novo artigo de Andrés Ventas.

Inverso multiplicativo modular

Resolver o inverso multiplicativo módulo $b$ é unha tarefa común na teoría de números. Aparece a miúdo na solución de sistemas de congruencias.

A forma estándar de atopar un inverso multiplicativo módulo $b$ é usar o algoritmo de Euclides estendido. Nun artigo de 1999, Glasby compara os dous métodos máis usados actualmente para o algoritmo euclidiano estendido: recorrencia cara atrás e recorrencia cara adiante. O método aquí presentado é máis curto en ambos os casos.

O problema que temos que resolver é atopar o $x$ da ecuación $ a x \equiv{1} \pmod{b}, \ a \lt b$. Se temos $a \gt b$ o xeito máis sinxelo é substituír $a$ por $a \bmod b$. O noso algoritmo usa as propiedades das fraccións continuas mixtas, que traducido ao algoritmo de Euclides sería usar a función teito ou a función chan dependendo do menor residuo.

Necesitamos que os dous números implicados sexan coprimos, e aquí podemos ver un exempliño que se saca a ollo:

Dado que $\gcd(3, 10) = 1$, a congruencia linear $3x \equiv{1} \pmod{10} $ terá solucións, é dicir, existirán inversos multiplicativos modulares de $3$ módulo $10$. De feito, o $7$ satisfai esta congruencia (é dicir, $21 - 1 =20$). Por tanto $7$ é un inverso modular de $3$ módulo $10$.

Outros números enteiros tamén satisfán a congruencia, por exemplo $17$ e $-3$ (é dicir, $3(17) - 1 = 50$ e $3(-3) - 1 = -10$). En particular, cada número enteiro en $\overline{7}$ satisfará a congruencia xa que estes enteiros teñen a forma $7 + 10r$ para algún enteiro $r$ e

$$3(7 + 10 r) - 1 = 21 + 30 r -1 = 20 + 30 r = 10(2 + 3r), $$

é divisíbel por $10$.

Exemplo máis elaborado: Inverso multiplicativo modular

$91 x \equiv{1} \pmod{254}$ $\textbf{Mediante o algoritmo de Euclides estendido.}$

índice

i

Cociente

$q_{i+1}$

$\lfloor r_{i}/r_{i+1} \rfloor$

resto

$r_i$

$s_i$ $t_i$
0$254$10
1$91$01
227212
311913
4315411
514514
6331953
71124 x=67
83091254

Os $s_i$ e os $t_i$ obtéñense coa mesma recorrencia que nas fraccións continuas, isto é $s_{i+1} = q_{i+1}s_{i}+s_{i-1}$ e $t_{i+1} = q_{i+1}t_{i}+t_{i-1}$, $s_i$ comezando por $(1, 0)$ e $t_i$ por $(0, 1)$. Maxicamente o inverso multiplicativo modular aparece na columna das $t_i$.

Efectivamente $x=67$ e temos $91 \cdot 67 = 6097 \equiv{1} \pmod{254}$ pois $254 \cdot 24 = 6096$.

Completamente máxico non o é, pois existen varias probas e está tamén relacionado coa identidade de Bézout.

Algoritmo mixto para obter o inverso multiplicativo modular

Sexa $a x \equiv{1} \pmod{b}, \quad a \lt b$, a congruencia para a que procuramos o inverso multiplicativo.

1. Bucle principal.

$\quad$ 1.1.Comezando con $a_0=a, \ b_0=b$, aplicamos $\Big\lceil \dfrac{b_i}{a_i} \Big\rfloor =(k_i, \pm) $ ata obtermos $b_n = k_n a_n \pm 1$. Isto quere dicir que en cada división ficamos co divisor $k_i$ que teña menor resto ao aplicar a función chan ou a función teito e no caso de ser chan anotamos ese coeficiente cun signo $\textbf{"+"}$ e se a función usada foi a teito marcamos o coeficiente cun signo $\textbf{"-"}$.

$\quad$ 1.2. Ao mesmo tempo, obtemos $a^{-1} \pmod{b}$. $x_{-1}=1, \ x_{0}=k_0; \ x_i: k_i \cdot x_{i-1} \pm x_{i-2}$.

(Note que o signo da recurrencia $i$ é o signo da operación previa $\lceil k_{i-i} \rfloor, \pm$).

2. Paso final.

Se o número das operacións de truncado (función chan, símbolo $+$) é par daquela $a^{-1} \pmod{b} =x_n$ noutro caso $a^{-1} \pmod{b} = b - x_n$.

Exemplos co algoritmo mixto

Nunha notación compacta podemos escribir tres filas. A fila superior contén os coeficientes da división enteira mixta, a segunda fila contén os residuos da operación e a terceira a recorrencia coa que obtemos a inversa multiplicativa modular. A recorrencia no algoritmo mixto pode ser sumando $t_{i+1} = q_{i+1}t_{i}+t_{i-1}$ ou restando $t_{i+1} = q_{i+1}t_{i}-t_{i-1}$ dependendo de se o coeficiente anterior se obtivo con función chan (+) ou teito (-).

$61 x \equiv{1} \pmod{2114}$.

$q_i$ $35^{-}$$3^{-}$$10^{+}$
$r_{i-1}$ 2114$61$$21$$2$$1$
$t_{i}$ 1$35$$104$ $1005$ $x=2114-1005=1109$

Comprobamos $x=1109$, temos $61 \cdot 1109 = 67649 \equiv{1} \pmod{2114}$ pois $32 \cdot 2114 = 67648$.

Nota: no exemplo de enriba non chegamos a utilizar a recorrencia positiva pois só temos función chan no último coeficiente que non chegamos a usar pois o signo da recorrencia vai dependendo do coeficiente anterior.

$91 x \equiv{1} \pmod{254}$. Este é o mesmo exemplo que fixemos enriba.

$q_i$ $3^{-}$$5^{-}$$5^{-}$
$r_{i-1}$ 254911941
$t_{i}$ 1314 67 $x=67$

E efectivamente temos outra vez $91 \cdot 67 = 6097 $ e $254 \cdot 24 = 6096$, só con 3 divisións en vez de 6.

Bibliografia

  1. S. P. Glasby, Extended Euclid’s algorithm via backward recurrence relations, Mathematics Magazine, 72(3)(1999), 228–230.
  2. Galipedia, Algoritmo de Euclides estendido
  3. Galipedia, Inverso multiplicativo modular
  4. Cálculos online do inverso multiplicativo modular
  5. Galipedia, Identidade de Bézout

mércores, 11 de setembro de 2024

Os conceptos na aula de matemáticas

Os profesores de matemáticas vémonos de cote fronte ao reto de introducir na aula novos conceptos. Algúns do gremio consideran fundamental establecer desde o primeiro momento unha definición precisa dos conceptos a traballar. Recordo o caso dun compañeiro que aos alumnos de 15 anos lles introducía os vectores libres como unha relación de equivalencia no conxunto de vectores fixos; despois aínda lles demostraba, entre outras cousas, que as operacións con esas clases de equivalencia non dependían do representante elixido. Algúns dos seus alumnos acudiran a min, desesperados, para que lles explicara algo diso. Despois dalgúns intentos só puiden certificar que era imposible que eses rapaces chegaran a entender outra cousa que as matemáticas eran incomprensibles. Tiñan moi claro que esta materia era  unha fonte de angustias e un obstáculo para o desenvolvemento dos seus estudos.

Hai profesores que, polo contrario, consideran que na clase de matemáticas é superfluo tratar os conceptos. O fundamental é traballar os procedementos. Unha vez aprendidos estes, o resto non importa. Así as clases consisten en practicar unha cadea interminable de algoritmos, moitas veces sen razón ningunha. 

Fronte a estas dúas posturas teño un fermoso recordo como alumno. O profesor pedíranos que pensáramos no concepto máis fundamental, no máis simple das matemáticas.

- Sumar - dixo alguén

- Non hai nada máis simple que facer sumas? - interveu o profesor

- Non. Multiplicar, ou restar, é máis difícil -respondeulle o rapaz

- Pero antes de saber sumar, non tes que saber nada? Que necesitas para saber sumar?

- Os números!

- Ben, estamos buscando o máis fundamental. Cales son os números máis simples, aqueles a partir dos que podemos ir construíndo todos os demais?

- O 1, o 2, o 3,... e así. Os números naturais, os positivos.

- E non hai nada máis fundamental aínda que os números?

- Non -foi a nosa resposta.

- Ben. Imaxinade que imos moi atrás no tempo, que pertencemos a unha sociedade moi primitiva, que apenas ten coñecementos pero xa son agricultores e gandeiros. Por suposto, non hai escolas e non coñecen os números pero teñen un rabaño de ovellas que sacan a pastar. Ao cabo do día interésalles saber se deixaron algunha perdida no monte. Como o poden saber?

Despois de algúns intentos e varios silecios, o profesor tivo que continuar.

- Se por cada ovella que sacan da corte colocan unha pedra e van facendo así un montón, cando volvan, poden ilas retirando e, se queda unha, por exemplo, saberán que terán que ir buscar unha ovella perdida no monte. 

- Pero iso é contar

- Non, non contan. Non din, 1, 2, 3,... senón que amontoan unha pedra por cada ovella.A cada ovella asígnanlle unha pedra, nada máis. Acabamos de ver un exemplo de algo máis fundamental que os números. Que son as pedras ou as ovellas? 

Por que poñería isto aquí?

Cómpre contextualizar a escena. Isto sucedeu hai 40 anos, de aí que os alumnos que estabamos nesa aula éramos alumnos da época das chamadas "matemáticas modernas". Todos oíramos falar unha e mil veces dos conxuntos.

- Efectivamente, o rabaño de ovellas forma un conxunto e o montón de pedras forma outro conxunto. Podédesme dar outros exemplos de conxuntos?

Non o lembro ben, pero é seguro que apareceron moitos exemplos tales como o conxunto de alumnos dese grupo, o subconxunto dos que tiñan gafas, o de todos os do insituto,o dos habitantes da vila, o dos coches dos profesores,...

- Todos os conxuntos son finitos, ou pode habelos con infinitos elementos?

- O conxunto dos números 1, 2, 3,.... é infinito. O dos primos, o dos decimais, - interviron varios alumnos

- Entón, para formar un conxunto, todos os elementos que o forman teñen que ter algo en común? Non podo formar un conxunto que teña como elementos un canguro, un triángulo e o planeta Marte?

Parecía haber consenso en que un conxunto podía estar formado por eses elementos, aínda que non tiveran relación entre si. 

- Os conxuntos son máis fundamentais que os números. Sen saber nada de números podemos traballar con conxuntos, tal e como fixemos co conxunto das pedras e o das ovellas. Entón estaría ben saber que é un conxunto, alguén o sabe?

Houbo moitas respostas: "un conxunto de cousas" (que obviamente non serve), "un grupo de cousas" (cando falamos de grupo entendemos que nos estamos a referir a cousas con algunha caracterísica común, e acabamos de ver que podemos formar conxuntos con elementos que non teñan nada en común), "unha colección de cousas" (aquí a obxección é a mesma que no caso anterior, falamos, por exemplo de coleccións de moedas ou de selos, que son todos elementos das mesmas características) "unha agrupación ..." (agrupación é o mesmo que grupo), "consiste en coller as cousas que queiramos..." (pero isto non é unha definición, é unha acción, é coma se dicimos que un cabalo serve para montar e non explicamos que é un animal),.... e así, unha tras outra todas as definicións tiveron algunha obxección por parte do profesor. Chegou un momento en que estaba claro que era o seu turno, el debía darnos a definición de "conxunto" e foi marabilloso: confesounos que tampouco era quen de explicar o que é un "conxunto". Quizais algúns se sentiron decepcionados ou enganados, pero pode ser que alguén sentira que, por primeira vez, estaba facendo matemáticas, pensando seriamente nas matemáticas.

- Os "conxuntos" son obxectos moi abstractos, é moi difícil definilos. Con todo, polos exemplos que foron aparecendo durante a clase vexo que temos unha idea intuitiva do que é un "conxunto" e iso chegaranos. O importante é que, cando traballemos cun conxunto, saibamos en todo momento se un elemento pertence ou non a ese conxunto. Aínda que ningunha das que apareceron é a definición ideal, moitas delas poden servirnos para traballar sen problemas coa teoría de conxuntos. É importante que recoñezamos esa eiva, quizais co tempo cheguedes a saber o porqué. De todas maneiras, insisto, non teremos ningunha dificultade porque vexo que todos temos unha boa idea do que son os conxuntos. Así, podemos copiar o seguinte na libreta:

Un conxunto X é unha colección de cousas ás que chamaremos elementos. Diremos que un elemento x pertence a X se forma parte do conxunto X. Isto escríbese $ x\in X$. Se un elemento y está no conxunto X diremos que a non pertence a X. Escríbese $ y\notin X$. Os conxuntos representarémolos sempre con letras maíusculas e os elementos con minúsculas.

Por exemplo, describiremos así o conxunto das letras vogais:$V=\left\{ a,e,i,o,u\right\}=\left\{vogais \right\} $