sábado, 18 de abril de 2015

Los camiones de Guanajuato

En Guanajuato (y seguramente en muchas otras ciudades) es común que estudiantes y otras personas se pongan a sumar los dígitos de su boleto en el camión urbano en búsqueda de un 21. Cuenta la leyenda que cualquier boletito que sume 21 (que se conocen simplemente como "veintiunos") puede ser cambiado por un beso con la persona de tu preferencia. Para ser honestos, en los ocho años que viví en Guanajuato nunca vi que esto funcionara en realidad, pero es sabiduría que se pasa de generación en generación. 

Naturalmente, surge la pregunta: ¿cuántos veintiunos hay? 

Los boletos de camión tienen un folio de 6 o 7 dígitos (algunos más o menos, no es realmente importante). Vamos a calcular cuántos hay con 6 dígitos. La diferencia entre un folio de 6 dígitos y un número de 6 dígitos es que el folio sí puede empezar con 0; por ejemplo, 001239 es un folio válido de 6 dígitos pero no es un número válido de seis dígitos. 

Para resolverlo, vamos a usar dos herramientas muy bonitas: separadores y el principio de Inclusión/Exclusión. Hemos preparado videos explicando ambas herramientas; si no estás seguro de cómo se usan esas herramientas, para que puedas entender lo que vamos a hacer, es buena idea que les des una repasada a los videos. 


Separadores es la herramienta que vendría a la mente de casi cualquiera cuando intenta resolver un problema similar: separadores nos ayuda a repartir objetos indistinguibles en categorías distinguibles u ordenadas; es decir, podríamos repartir 50 pelotas en 10 cajas donde todas las pelotas son iguales y, aunque las cajas también son iguales, las podemos reconocer diciendo que alguna es "la primera caja", "la segunda caja", etcétera. 

El problema es que separadores reparte sin condiciones y en algunos casos -como en éste- los problemas tienen condiciones explícitas. Un tipo sencillo de condición que podemos resolver sin mucho problema es una del tipo "la caja X tiene al menos Y pelotas". Por ejemplo: si quisiéramos repartir las 50 pelotas en 10 cajas y queremos asegurar que todas las cajas tienen al menos 3 pelotas, lo que haríamos -incluso de manera intuitiva en una repartición real- sería darle a cada caja 3 pelotas y luego ver cómo le hacemos para repartir las demás; es decir 30 de las pelotas ya están repartidas y nuestro problema se traduce ahora en repartir 20 pelotas en 10 cajas, que se resuelve fácil usando separadores. 

Nuestro problema de los boletos se traduce en un problema de repartir 21 unos, es decir, 21 unidades, en seis posiciones. Podemos entender que queremos repartir 21 pelotas en 6 cajas. Una manera de hacerlo sería:

1 1 / 1 1 1 1 1 / / 1 1 1 1 1 1 1 / 1 1 1 / 1 1 1 1

que se traduce en el número 250734. Como estamos repartiendo 21 pelotas, nos aseguramos que la cantidad total de pelotas, es decir, la suma de los dígitos del número, sea siempre 21. Lo que no podemos asegurar es que en cada caja haya menos de 10 pelotas, lo que nos generaría folios inválidos.

Así, la manera de salir de este apuro sería hacer muchísimos casos: cuando hay un nueve, cuando hay dos nueves, cuando hay un ocho, cuando hay un nueve y un ocho, cuando hay un siete...


Incluso sabiendo que la mezcla entre separadores y el principio de Inclusión/Exclusión son los que ayudan a resolver este problema, quizás no sea inmediato la manera de hacerlo. Hay que agregar a la mezcla una idea adicional: la de contar por complemento. 

Mencionamos que es sencillo contar, usando separadores, condiciones del tipo "la caja X tiene al menos Y pelotas". En este problema, no tenemos realmente una condición para cota inferior, pues nuestras cajas -los dígitos- pueden estar vacías -ser cero-. Las condiciones que tenemos ahora, y la que más nos preocupa, es asegurar que sean dígitos, es decir, que ninguna caja tenga más de 10 pelotas.

Aquí es donde entra la idea de contar por complemento es la siguiente: cuando tenemos más de una condición, contar todos los que números que cumplen la primera condición y restar los números que cumplen la primera pero no cumplen la segunda. Esta resta nos deja únicamente con los números que cumplen ambas condiciones.

Por ejemplo: ¿cuántos números de 5 cifras tienen al menos un dígito par?

Contar de manera directa nos arroja muchos casos: cuando hay un dígito par, cuando hay dos, cuando hay tres, cuando hay cuatro y cuando hay cinco. Sin embargo, es mucho más sencillo saber cuántos números de 5 cifras hay y a éstos restarle la cantidad de números que no tienen dígitos pares, es decir, cuyos dígitos son todos impares, que es algo mucho más sencillo de contar.

Naturalmente, la idea de contar por complemento se usa cuando contar "directo" parece tarea más complicada. Esta es la idea que vamos a usar: vamos a convertir las condiciones de "la caja X tiene a lo más Y pelotas" en condiciones de la forma "la caja X tiene al menos Y+1 pelotas", que no cumplen la condición, y luego simplemente restarlas. 

Hemos preparado otro video para explicar todo lo que aquí hemos dicho: 


Por supuesto, la idea no es que esta herramienta se quede en maneras de contar boletos de camión con cierta propiedad romántica, sino que la puedas utilizar para resolver muchos problemas. 

Te proponemos uno: imagina que tienes los 7 libros de Harry Potter y los deseas ordenar en tu librero. Sabemos que esto se puede hacer de 7! = 5040 maneras distintas. ¿En cuántas de estas maneras están todos los libros en desorden? Con desorden queremos decir que el libro 1 no está primero, el libro 2 no está segundo, etcétera.