Inclusión/exclusión: ¿Cuántos números naturales < 10.000.000 contienen 168, en orden, consecutivamente?

Question

Por ejemplo, 1.683.718, pero no 1.568.

Necesito utilizar el principio de multiplicación (que producirá sobreconteo) y el principio de inclusión/exclusión para encontrar esto (o una manera mejor, si es posible). ¿Alguna sugerencia? El 168 fijo es lo que me despista de los problemas típicos.

Answer 1

Contamos la unión de cinco conjuntos: las cadenas de la forma 168XXXX, las cadenas de la forma X168XXX, etc. Cada conjunto tiene $10000$ elementos. Por inclusión-exclusión, puede sumar estos recuentos para $50000$ y restar los recuentos de las intersecciones por pares de los conjuntos, que contienen cadenas de la forma 168168X, 168X168 y X168168, de las cuales hay $30$ . Las intersecciones de tres o más conjuntos son todas vacías, por lo que hemos terminado, llegando a $50000-30=49970$ .

Para comprobarlo, podemos obtener la misma respuesta por fuerza bruta:

$ python
>>> sum('168' in str(x) for x in range(10000))
20
>>> sum('168' in str(x) for x in range(100000))
300
>>> sum('168' in str(x) for x in range(1000000))
3999
>>> sum('168' in str(x) for x in range(10000000))
49970