Prueba de soluciones para el juego de operaciones "24"

Question

Considera una baraja de cartas con valores del $1$ al $13$, cada uno con multiplicidad $4$, de manera que $$S = \left( \bigcup_{i=1}^{13} \{ i \} \right) \times \{1,2,3,4\}$$

Supuestamente, existe un juego en el que se seleccionan cuatro cartas $(v,m)$ en $S$ (aquí $m$ representa el palo), y los participantes intentan idear una serie de operaciones usando:

• la suma $+$;
• la resta $-$;
• la multiplicación $\times$;
• la división $\div$;
• la exponenciación $\wedge$;
• la factorización $!$; y
• un número cualquier de paréntesis $()$

en los valores $v$ que resulte en $24$. Por ejemplo,

$$(2, 1) \times (10,3) - (2,4) + (3,2)! = 24$$

---

• ¿Existen combinaciones de cartas para las cuales no existe una serie de operaciones que de como resultado $24$?
• ¿Qué procesos matemáticos se podrían usar para analizar otros aspectos de las soluciones, como cuántas soluciones existen?

Este es un juego post-examen que estamos jugando en clase para pasar el tiempo. No tengo la menor idea de cómo abordar cualquier tipo de 'prueba'.

Answer 1

EDITAR: hubo un error en mi código por lo que se perdió algunas soluciones. En realidad sólo hay 48 manos sin solución, no 56.

EDITAR 2: debido a errores de redondeo, mi código pensaba que [9,7,5,5] era solucionable, cuando en realidad no lo es (véase la actualización más abajo).

Yo también he jugado a ese juego, así que cuando vi tu pregunta estaba bastante seguro de que hay algunas manos que no tienen series que lleguen a 24. Como sólo hay $\binom{52}{4} = 270,725$ posibles manos de 4 cartas (incluso menos ya que este juego no cuenta los palos), me imaginé que sería factible hacer una búsqueda por ordenador para encontrar todas estas soluciones (ver abajo mi código).

Mi programa encontró soluciones para todas las manos menos 48 (ignorando los diferentes palos):

[1,1,7,7] [1,1,9,9] [1,1,10,10] [1,1,10,11] [1,7,7,13] [1,9,9,9] [1,9,10,10] [1,10,10,10] [1,10,10,11] [1,10,11,11] [1,11,11,11] [1,13,13,13] [6, 6,6,13] [6,6,7,7] [6,6,7,13] [6,6,13,13] [6,7,7,13] [6,7,13,13] [6,8,8,13] [6,11,11,13] [7,7,7,7] [7,7,7,13] [7,7,10,10] [7,7,10,12] [7,7,11, 11] [7,7,13,13] [7,8,9,9] [7,10,10,13] [7,11,11,13] [7,13,13,13] [8,8,9,9] [8,8,11,11] [8,9,9,10] [8,9,13,13] [9,9,9,9] [9,9,9,11] [9,9,10,10] [9, 9,13,13] [9,10,10,10] [9,10,10,11] [9,10,11,11], [10,10,10,10] [10,10,10,11] [10,10,11,11] [10,10,13,13] [10,11,11,11] [11,11,11,11] [13,13,13,13]

Contando los palos, esto supone 2413 posibilidades de las 270.725 manos totales, o una probabilidad ligeramente inferior al 0,9%.

Como mi programa no utilizó factoriales de ningún número mayor que 13, es posible que algunos de estos 48 tengan realmente soluciones, pero no lo encuentro muy probable. Entre estas combinaciones todas tienen cartas repetidas. Ninguna de las combinaciones tiene un 2, 3, 4 o 5, y sólo una tiene un 12. Sorprendentemente, el número más común en las manos sin solución es el 10 (teniendo en cuenta los palos, aparece en 1109 de las 2413 manos sin solución). Como alguien que ha jugado mucho a este juego, esperaba que el 11 o el 13 fueran los más probables para dar una mano irresoluble, pero sólo aparecieron en 845 y 1073 manos irresolubles, respectivamente.

En cuanto al número de formas de llegar a 24 a partir de una mano dada, mi programa no se fijaba en eso porque intentaba que el programa no ocupara demasiada potencia de cálculo, y era mucho más fácil recordar simplemente un solo booleano que toda una cadena.

---

Actualización de los errores de redondeo:

[9,7,5,5] no es una solución, pero mi código cree que es debido a errores de redondeo. Por ejemplo, no pudo distinguir $9^{5-7!}$ de $0$ y encontré esta "solución": $$ \left(5 - \left(9^{5-7!}\right)!\right)! \approx 24 $$ Si se utiliza la función gamma para interpolar los factoriales, esto sólo se desvía en aproximadamente $5\times 10^{-4804}$ .

La eliminación de la exponenciación de las opciones, aparte de utilizar $1^a = 1$ , muestra que esta es la única solución que se aprovechó de este error numérico en particular. Como nunca tomé un factorial de un número mayor que 13, los factoriales no deberían haber introducido ninguna otra solución falsa.

---

Algunas manos de ejemplo interesantes: Entre las manos que tienen soluciones, he decidido destacar algunas especialmente interesantes:

[13,11,10,6], [13,6,1,1], [13,12,10,8], [11,11,5,5], [11,11,5,1], [9,7,7,7], y [5,1,1]

Si quieres desafiarte a ti mismo, comprueba si puedes resolverlos antes de mirar las soluciones.

[13,11,10,6]

Esta es la única mano que requiere un factorial de un número mayor que 10: $$24 = \left(\frac{13 + \frac{11!}{10!}}{6}\right)!$$

[13,6,1,1]

Esta y [9,8,1,1] son las únicas que requieren el uso de la exponenciación: \begin{eqnarray} 24&=&\left(\frac8{1+1^9}\right)!\\24&=&\left(6 - 1^{13} - 1\right)! \end{eqnarray}

[9,7,7,7]

Esta mano sólo tiene una solución posible, y es un ejemplo interesante de una que requiere factoriales pero no utiliza $4!=24$ . $$24 = \frac{9!}{7!+7!+7!}$$

Si no se permiten los factoriales, hay 430 manos irresolubles (sin contar los palos). Algunas de mis soluciones favoritas sin factoriales son [11,11,1,5], [13,12,10,8], [11,11,5,5] y [5,1,1,1], que tienen lo siguiente único soluciones no factoriales:

[13,12,10,8]

$$24=\frac{10\cdot 12}{13-8}$$

[11,11,5,5]

$$24=5\cdot5-\frac{11}{11}$$

[11,11,5,1]

$$24=\frac{11\cdot 11 - 1}{5}$$

[5,1,1,1]

$$5^{1+1} - 1$$

---

A continuación, mi programa Haskell. La programación no es mi punto fuerte, así que disculpa el desorden.

unsolvable = p 4
-- all hands that have no way to reach 24.

-- derivation:

-- returns True if an input four card hand is solvable.
check :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => \[a\] -> Bool
check \[a,b,c,d\] = firstCheck a b c d
check \_ = False

--check as a four-argument function
firstCheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> a -> a -> Bool
firstCheck a b c d = or \[fCheck a b c d, fCheck b c d a, fCheck c d a b, fCheck d a b c, fCheck d b a c, fCheck a c b d\]

fCheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> a -> a -> Bool
fCheck a b c d = or $ map (secondCheck a b) $ op c d

{--finalCheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> Bool
finalCheck a b = (24 \`elem\` s) 
    where s = op a b --}

--check if 3 numbers can make 24
sCheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> a -> Bool
sCheck a b c = or $ map (finalCheck a) $ op b c

secondCheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> a -> Bool
secondCheck a b c = (sCheck a b c) || (sCheck b a c) || (sCheck c a b)

-- checks if 2 numbers can combine to 24 or 4! = 24
finalCheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> Bool
finalCheck a b = (24 \`elem\` s) || (4 \`elem\` s)
    where s = op a b

--all operations except factorial, with the assumption that a a -> a -> \[a\]
opp 0 b = \[0,1,b,-b, 1+b, b-1, 1-b\]
opp 1 b = \[1+b,b,1/b,1-b,b-1,1\]
opp a b = \[a+b,a\*b,a/b,a-b,b-a,b/a,a\*\*b,b\*\*a\]

-- op includes operations from opp as well as manually including factorials up to 13!
op ::  (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a) => a -> a -> \[a\]
op 3 b = opp (min 3 b) (max 3 b) ++ op b 6 ++ op 6 b
op 4 b = opp (min 4 b) (max 4 b) ++ op b 24
op 5 b = opp (min 5 b) (max 5 b) ++ op b 120 
op 6 b = opp (min 6 b) (max 6 b) ++ op b 720
op 7 b = opp (min 7 b) (max 7 b) ++ op b 5040 
op 8 b = opp (min 8 b) (max 8 b) ++ op b 40320 
op 9 b = opp (min 9 b) (max 9 b) ++ op b 362880 
op 10 b = opp (min 10 b) (max 10 b) ++ op b 3628800 
op 11 b = opp (min 11 b) (max 11 b) ++ op b 39916800
op 12 b = opp (min 12 b) (max 12 b) ++ op b 479001600
op 13 b = opp (min 13 b) (max 13 b) ++ op b 6227020800
op a b = opp (min a b) (max a b) 

lcheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a,Enum a) => \[a\] -> \[Bool\]
lcheck \[a,b,c,d\] = \[check \[a,b,c,d\]\]
lcheck s = map (and . lcheck . (\\n -> n:s)) \[(head s)..13\] 
-- s must be in order from largest to smallest.
-- (lcheck s !! i) is True whenever there is a solvable hand sorted 
-- from largest to smallest that ends with (head s + i):s

ccheck :: (Num a, Fractional a, Eq a, Ord a, Floating a, Enum a,Enum a) => \[a\] -> Bool
ccheck = and . lcheck
-- returns True if a sorted hand ending with s is solvable

p1 = filter (not . (\\k -> (ccheck \[k\])) . fromIntegral) \[1..13\]
-- possible smallest cards for an unsolvable hand

pf :: (Integral a) => \[a\] -> \[\[a\]\]
pf x = map (\\s -> s:x) $ filter (not . (\\k -> (ccheck $ map fromIntegral (k:x))) . fromIntegral) \[(head x)..13\] 
-- if x is n cards, pf x lists possibilities of length n+1 endings for sorted hands that end in x

p :: Int -> \[\[Integer\]\]
p 1 = map (\\x -> \[x\]) p1
p n = foldr (++) \[\] $ map pf $ p (n-1)
-- lists possible last n cards of a sorted unsolvable hand.

Answer 2

Dark Malthorp demostró que hay combinaciones de cartas que no pueden dar 24 a partir de las operaciones que especificaste. Intentaré responder a tu otra pregunta sobre qué estrategia podría usar alguien. Dado el número/tipos de operaciones permitidas, creo que esta estrategia no es viable, pero es solo para mostrar lo que podríamos hacer si el juego fuera menos complejo (sin ^, números más pequeños, etc.). EDITAR: Ver comentarios sobre por qué $!$ no se puede quitar.

Cada fórmula construida a partir de $v_1, v_2, v_3$ y $v_4$, utilizando las operaciones $+, -, \cdot, /, ^$ y $!$, es de las siguientes cinco formas:

1. $(((v_1!_n*v_2!_n)!_n*v_3!_n)!_n*v_4!_n)!_n$
2. $((v_1!_n*(v_2!_n*v_3!_n)!_n)!_n*v_4!_n)!_n$
3. $(v_1!_n*((v_2!_n*v_3!_n)!_n*v_4!_n)!_n)!_n$
4. $(v_1!_n*(v_2!_n*(v_3!_n*v_4!_n)!_n)!_n)!_n$
5. $((v_1!_n*v_2!_n)!_n*(v_3!_n*v_4!_n)!_n)!_n$

donde $*$ es una operación binaria $+, -, \cdot, /$ o ^, y $!_n$ es una cantidad de factoriales $!$. Se ve realmente feo porque un $!_n$ puede aparecer después de cada $v_n$ y paréntesis.

Tuve la sensación de que $v_1 = v_2 = v_3 = v_4 = 13$ funcionaría. Informalmente, hacer que todos los números sean iguales "limita" lo que las operaciones pueden hacer en cierto sentido, y Dark confirmó que 13,13,13,13 es una de las combinaciones que no pueden dar 24.
Así que intentemos hacer una prueba por contradicción. Esto no es de ninguna manera una prueba ya que no he verificado cada caso.

Supongamos que $v_1 = v_2 = v_3 = v_4 = 13$, y que cada forma da como resultado 24. Entonces, en cada forma, $n$ en el $!_n$ más externo es cero.* (* significa que no está completamente justificado sin verificar muchos casos). Primero, tenemos que $m!=24$ si y solo si $m=4$. Supongamos $n=2$, entonces la misma fórmula con el $!_{n-1}$ más externo en lugar de $!_n$ debe dar como resultado 4 (ya que $4!=24$). En este caso, requerimos que $\phi!_1=4$, donde $\phi$ representa la fórmula sin el $!_{n-1}=!_1$ más externo. Pero no hay ningún número $m$ tal que $m!=4$, contradicción, por lo que $n\neq2$. Repetimos este argumento para $n>2$. Bueno, ahora es la parte donde usamos $v_1 = v_2 = v_3 = v_4 = 13$, y donde no verifiqué los casos. Supongamos que $n=1$, entonces requerimos que $\phi!_0=\phi=4$, lo cual no creo que sea posible, por lo tanto $n=0$.* (Para verificar esto realmente se requeriría mucho cálculo). Entonces $\ldots$

Como puedes ver, esto se convierte en UN MONTÓN de verificación de casos. Eventualmente tendríamos que verificar los $!_n$ en $\phi$ y las subfórmulas subsiguientes son $!_0$.* Creo que esto es así informalmente, regresar $13!$ a un número menor requiere división por al menos $13!$, ocupando un espacio de operación. Quizás esto no sea cierto para números más pequeños; esta es otra razón por la cual elegí 13,13,13,13 y no otra cuádruple de números iguales, además de que no parece que puedas obtener los factores de 24 fácilmente a partir de 13.

De todos modos, al fijar TODOS los $!_n$ con una cantidad finita de $n$ y notando que solo hay una cantidad finita de combinaciones de operaciones binarias, tendrías una cantidad finita de casos que revisar.

Espero que esto te ayude en tus problemas futuros.