¿Cómo organizar estos 10 dígitos para hacer una ecuación correcta?

Question

Mi hija trajo a casa el "problema de la" semana de la noche anterior y me fue explicado como este:

Dados los siguientes dígitos: $$1\ \ 1\ \ 2\ \ 3\ \ 3\ \ 4\ \ 5\ \ 6\ \ 6\ \ 7$$

Organizar en esta ecuación para realizar una correcta respuesta: $$\_\ \_\ \_\ \times \_\ \_ = \_\ \_\ \_\ \_\ \_$$

Me hizo encontrar a las 4 posibles soluciones, y los pondré en la parte inferior de este post, no se ven si quieres probar a ti mismo primero. Mi pregunta es más sobre el método para resolver esto, no es la respuesta.

Así que hice un poco de trabajo, y encontró que hay alrededor de 3,6 millones de maneras de organizar de 10 caracteres ($10!$). Sin embargo, desde el $1$, $3$, y $6$ se repiten los golpes hacia abajo a una mucho más manejable ~$470,000$ posibilidades.

Aquí el maestro le dijo que sólo había una respuesta correcta.

Traté de usar sólo un poco de sentido común para reducir la posibilidades de abajo, pero todavía parecía no eran demasiado numerosas permutaciones a tratar.

Así que me decidí a fuerza bruta con un programa en Java. Después de pasar algún tiempo trabajando en un par de ajustes de rendimiento, puedo intentar todos ~$470,000$ combinaciones en unos 2 segundos en mi mac. Me encontré con que el maestro era incorrecto y hay 4 posibles permutaciones que son correctos.

¿Cómo un niño de 11 años de edad, estudiante sin experiencia en programación de resolver este problema? Hay algunas de las "nuevas matemáticas" ;) que yo no entiendo?

EDIT: he portado mi programa Java a Javascript, por lo que usted puede jugar con esto. No se mucho de validación de entrada o de control de error, pero aquí vamos: Problema de la semana

Mis Soluciones:

$$617 \times 43 = 26531$$ $$667 \times 23 = 15341$$ $$653 \times 37 = 24161$$ $$637 \times 23 = 14651$$

Answer 1

Esto no es particularmente elegante respuesta, pero creo que es posible reducir el número de posibilidades a alrededor de 100, por un lado, en un par de horas. La incorporación de un paso adicional se reduce a sólo un par de docenas que se puede comprobar multiplicando. La estrategia es principalmente algorítmica, sino que también incorpora algunas observaciones que nos permiten descartar una serie de posibilidades sobre la marcha.

Escribimos la ecuación en la forma siguiente, donde cada letra representa un dígito: $$ abc \times de = fghij.$$

El primer paso es buscar en todos los admisible dígitos para el triple $(c,e,j)$. No es difícil comprobar que existen 14 triples. El segundo paso es utilizar estas tripletas para determinar admisible dígitos para el triple $(b,d,i)$. Nos encontramos con que hay alrededor de 10 triples que trabajo para cada una de las $(c,e,j)$. Por último, podemos hacer varias observaciones a descartar rápidamente un número de estas posibilidades. Por ejemplo, es imposible (salvo algunos casos especiales) a ha $d=1$, ya que esto generalmente resulta en un producto de bajo $12000$. Es igualmente fácil de descartar que en muchos casos $d=2$ o $a=1$. En general, estas observaciones se puede resumir: en el paso 3 se compruebe la mayor dígitos $a$, $d$ y $f$ a descartar los casos donde el producto $ad$ no concuerdan con el resto de las opciones para $f$.

Aquí es un ejemplo. Considerar el total admisible de triple $(c,e,j) = (7,6,2)$. En este caso, el triple de $(b,d,i)$ debe satisfacer la ecuación de $6b+4+7d \equiv i$ (mod $10$). La comprobación a través de los dígitos restantes $1,1,3,3,4,5,6$ da seis posibilidades para $(b,d,i)$: $(1,3,1)$, $(3,6,4)$, $(4,1,5)$, $(4,5,3)$, $(5,1,1)$, $(6,3,1)$. Basado en las observaciones anteriores, podemos descartar $(4,1,5)$$(5,1,1)$, ya que el $d=1$. Por el triple $(1,3,1)$, ahora hemos agotado tanto $1$s y $2$, lo que significa que debe tener $f \geq 3$, sin embargo, no hay opción de $a$ da esta $f$. Similares consideraciones de $a$ $f$ pueden descartar las tres últimas opciones.

En total, hice el cálculo anterior para $5$ de la $14$ admisible triples $(c,e,j)$, y para cada una de las $5$, he encontrado entre $6$ $16$ admisible triples $(b,d,i)$ (he encontrado $6$, $6$, $9$, $15$, y $16$ para los cinco triples que probé). Once de estos $52$ puede ser descartado por consideraciones elementales (por ejemplo,$d \neq 1$) y muchas más ligeramente extra de la computación (comparación de posibilidades para$a$$f$).

No pretendo que un $11$ años podría reducir las posibilidades tan rápidamente, pero es posible reducirlo a alrededor de 100 posibles $6$-tuplas $(c,e,j,b,d,i)$ en menos de un par de horas. Si se añade el paso final de la comprobación de la adecuada $a$$f$, yo creo que con ganas matemático podría utilizar este algoritmo para encontrar todas las soluciones a mano.

Answer 2

Se puede reducir a $6570$ posibilidades, ya que sólo necesita para elegir los dígitos en el lado izquierdo y que únicamente determina el lado derecho.
Esto se puede reducir más, tal vez incluso hasta el punto en que podía hacerlo, más bien tediosa, por un lado, si usted elige el de menor orden de los dígitos primero y desterrar los casos en los que esto implica imposible dígitos a la derecha.

Así, supongamos que supongo que la de menor orden dígito del primer número es $2$. A continuación, las únicas posibilidades para la de menor orden de los dígitos de los segundos son $3$ ($2 \times 3 = 6$) y $7$ ($2 \times 7$ termina en $4$). Si es $3$, entonces la eliminación de un $2$, $3$ y $6$ deja $1,1,3,4,5,6,7$ a partir de la cual elegimos la segunda más baja de los dígitos de la izquierda...

Answer 3

Incluso si nos restringimos a legales combinaciones de dígitos de orden inferior, que sería extremadamente tedioso escribir las posibles formas de colocar los dígitos en el lado izquierdo de la ecuación. Esta codificación en Python ejecuta en menos de 0,1 segundo y da posibilidades de 2304. (Tenga en cuenta la sobrecarga de ocultar en la lista de repetidas copias, lista y establezca manipulación, conversión a caracteres, clasificación...)

# Compute products of the form ABC x DE, choosing digits from:
all_digits = [1, 1, 2, 3, 3, 4, 5, 6, 6, 7]

# Possible values for C, and corresponding choices for E:
c_list = [1, 2, 3, 4, 6, 7]
e_map = { 1:[3,6], 2:[3,7], 3:[1,2,4,7], 4:[3], 6:[1,7], 7:[2,3,6] }

ntry = 0
for c in c_list:
#for c in set(all_digits):
    remain1 = all_digits[:]
    remain1.remove(c)
    for e in e_map[c]:
    #for e in set(remain1):
        remain2 = remain1[:]
        remain2.remove(e)
        for a in set(remain2):
            remain3 = remain2[:]
            remain3.remove(a)
            for b in set(remain3):
                remain4 = remain3[:]
                remain4.remove(b)
                for d in set(remain4):
                    ntry += 1
                    remain5 = remain4[:]
                    remain5.remove(d)
                    n1 = 100*a + 10*b + c
                    n2 = 10*d + e
                    prod = n1 * n2
                    # Test if prod uses up the remaining digits:
                    if sorted(list(str(prod))) == sorted([str(x) for x in remain5]):
                        print "%d x %d = %d" % (n1, n2, prod)

print "Total %d tries" % ntry

Answer 4

Yo puede determinar de inmediato que el 4, 5, y 7 no puede ser el del dígito de la derecha debido a sus factores no existente para la izquierda. También puedo ver que 5 es ilegal número para el lado izquierdo. Básicamente asume que el problema comienza con tres números de un dígito. Entonces, tener un solo dígito el número de veces que un número de dos dígitos (un dígito posibilidades serán los posibles lugares) y, a continuación, y así sucesivamente. De lo que puedo decir, existen las siguientes combinaciones posibles de un dígito multiplicaciones:

1 * 3 = 3

1 * 6 = 6

2 * 3 = 6

2 * 7 = 14

3 * 4 = 12

3 * 7 = 21

6 * 7 = 42

Algunos de estos han de llevar a hacer malabares, pero en general, esto reduce sus posibilidades.

También hay otro enfoque que se basa en un principio de un polinomio que muchos no se captura. Los polinomios son en realidad los números en base X. Esto es importante ya que podemos usar para reescribir la multiplicación.

(100a + 10b + c)(10d + e) = (10000f + 1000g + 100h + 10j + k)

Así:

1000ad + 100ae + 100bd + 10be + ce = 10000f 1000g + 10j + k

Creo que con algo semejante a un método para el cálculo de la fracción parcial de la descomposición se puede resolver el álgebra mediante la comparación específica dígitos. Al menos esto le ayudará a estar permitiendo llenar en dígitos como ir y ver lo que todavía es posible. Después de todo:

ce % 10 = k Donde: % significa que el resto de una vez dividido por b.

Answer 5

Esto es interesante. Aquí es un trazador de líneas de dos R que encuentra las cuatro soluciones:

library(combinat)
for (x in unique(permn(c(1,1,2,3,3,4,5,6,6,7)))) if ((100*x[1]+10*x[2]+x[3]) * (10*x[4]+x[5]) == (10000*x[6]+1000*x[7]+100*x[8]+10*x[9]+x[10])) print(x)

Salida:

[1] 6 1 7 4 3 2 6 5 3 1
[1] 6 6 7 2 3 1 5 3 4 1
[1] 6 3 7 2 3 1 4 6 5 1
[1] 6 5 3 3 7 2 4 1 6 1