¿Cuántos enteros positivos de seis dígitos tienen la propiedad de que cada dígito es menor que cualquier dígito a su derecha?

Answer 1

Aquí hay un programa de Python para enumerar todos los números deseados (método de fuerza bruta lenta, pero lo hace en unos segundos. Una solución más rápida sigue más adelante) …

# brute force program to enumerate strictly increasing 6 digit numbers def isAscending(num):
num_list = [int(y) for y in str(num)]
for x in range(len(num_list)-1):
if num_list[x] >= num_list[x+1]:
return False
return True ascen_nums = [x for x in range(100000, 1000000) if isAscending(x)] print len(ascen_nums)
print ascen_nums

# brute force program to enumerate strictly increasing 6 digit numbers def isAscending(num):
num_list = [int(y) for y in str(num)]
for x in range(len(num_list)-1):
if num_list[x] >= num_list[x+1]:
return False
return True ascen_nums = [x for x in range(100000, 1000000) if isAscending(x)] print len(ascen_nums)
print ascen_nums

# brute force program to enumerate strictly increasing 6 digit numbers def isAscending(num):
num_list = [int(y) for y in str(num)]
for x in range(len(num_list)-1):
if num_list[x] >= num_list[x+1]:
return False
return True ascen_nums = [x for x in range(100000, 1000000) if isAscending(x)] print len(ascen_nums)
print ascen_nums

# brute force program to enumerate strictly increasing 6 digit numbers def isAscending(num):
num_list = [int(y) for y in str(num)]
for x in range(len(num_list)-1):
if num_list[x] >= num_list[x+1]:
return False
return True ascen_nums = [x for x in range(100000, 1000000) if isAscending(x)] print len(ascen_nums)
print ascen_nums

Y si estaba interesado, aquí está el resultado …

84
[123456, 123457, 123458, 123459, 123467, 123468, 123469, 123478, 123479, 123489, 123567, 123568, 123569, 123578, 123579, 123589, 123678, 123679, 123689, 123789, 124567, 124568, 124569, 124578, 124567, 124568, 124569, 124578 , 124589, 124678, 124679, 124689, 124789, 125678, 125679, 125689, 125789, 126789, 134567, 134568, 134569, 134578, 134579, 134589, 134678, 134679, 134689, 134789, 135678, 135679, 135689, 135789, 135678, 135679, 135689, 135789 , 145678, 145679, 145689, 145789, 146789, 156789, 234567, 234568, 234569, 234578, 234579, 234589, 234678, 234679, 234689, 234789, 235678, 235679, 235689, 235789, 236789, 245678, 24568, 245678, 24568, 245679 , 246789, 256789, 345678, 345679, 345689, 345789, 346789, 356789, 456789]

Lo sé, lo sé … la fuerza bruta es demasiado mala para resolver cualquier problema. Entonces, aquí hay otra solución en python. Espero que ames la recursividad …

def gen_asc_number(start, numdigits):
scale = 10**(numdigits-1)
for x in range(start, 10-numdigits+1):
if numdigits > 1:
for rest in gen_asc_number(x+1, numdigits-1):
yield x*scale + rest
else:
yield x

resultado = lista (gen_asc_number (1, 6))

imprimir len (resultado)
resultado de impresión

Esta solución es asintóticamente la mejor … solo supera los números que se ajustan a los criterios y no otros. Por supuesto, está en Python, por lo que no es difícil superar su tiempo de ejecución. Demonios, una fuerza bruta C podría acercarse para vencer a esta solución recursiva (aunque en realidad no …).

Answer 2

Suponga que tiene ese número, como 234569. Observe que es el único número que se puede hacer con esos dígitos en particular; no podemos intercambiar el orden de ninguno de los dígitos sin violar la restricción.

Basándonos en esa observación, podemos reducir el problema a solo los dígitos a elegir. Hay un par de formas de contar esto.

Una es comenzar con 123456789 (ya en orden). Para obtener un número de 6 dígitos, debemos eliminar tres dígitos, y hay [matemáticas] {9 \ elegir 3} = 84 [/ matemáticas] formas de hacerlo. O, de manera equivalente, dados los 9 dígitos disponibles, debe elegir 6 de ellos para ir en el número.

Answer 3

Está eligiendo 6 dígitos de 9 con un orden específico (es decir, el orden de selección de dígitos no importa). La respuesta es: [matemáticas] \ binom {9} {6} = \ frac {9!} {3! 6!} = 84 [/ matemáticas]

(¿Por qué 9 en lugar de 10? Porque no puedes usar 0.)

Answer 4

Dado que el orden es fijo, simplemente elija seis dígitos entre nueve (ya que normalmente no se permite un cero inicial):

[matemáticas] ^ 9C_6 = \ frac {9 \ veces 8 \ veces 7} {3 \ veces 2 \ veces 1} = 84 [/ matemáticas]

O, si se permite un cero inicial:

[matemáticas] ^ {10} C_6 = \ frac {10 \ veces 9 \ veces 8 \ veces 7} {4 \ veces 3 \ veces 2 \ veces 1} = 210 [/ matemáticas]

Answer 5

Como ya mencionaron los demás, es solo la cantidad de formas en que puede elegir 6 dígitos del conjunto de 9 dígitos [matemática] \ {1, 2, 3, 4, 5, 6, 7,8, 9 \} [/ matemática ] independientemente del orden (después de haberlos elegido, los coloca en el orden correcto). Es decir, si, por ejemplo, primero elige 9, luego 2, luego 1, luego 5, luego 6, luego 3 es lo mismo que primero elige 5, luego 3, luego 9, luego 1, luego 6, luego 2. Solo El resultado de su elección (el conjunto) cuenta.

Esto se mide en la combinatoria por [matemáticas] \ binom {9} {6} = \ frac {9!} {6! \ cdot 3!} = 84 [/ matemáticas].

[matemáticas] 0 [/ matemáticas] no está incluido ya que su número no puede comenzar con [matemáticas] 0 [/ matemáticas]. Si lo hubiera elegido entre los dígitos, habría estado justo después de reordenar.

Answer 6

Puede tratar esto como una especie de diferencia, los prototipos son 012345 o 123456. Luego, distribuye cuatro o tres incrementos adicionales,

Por ejemplo, si el primer incremento es 3, el número se convierte en 124567.

La evaluación se reduce a cuántas formas se pueden hacer 3,

3 = 1 + 1 + 1 6 * 5 * 4/3! = 20
2 + 1 6 * 5 = 30
3 6 = 6

Todos juntos 56 maneras diferentes, terminando en un 9

2 = 1 + 1 = 6 + 5/2!
2 = 6 21 con dos incrementos (terminando en un 8)

6 con 1 incremento que termina en un 7
1 sin incrementos que terminan en 6

Esto da 84.