Що таке найменше ціле число n таке, що n! = m cdot 10 ^ (2016)?

Що таке найменше ціле число n таке, що n! = m cdot 10 ^ (2016)?
Anonim

Відповідь:

# n = 8075 #

Пояснення:

Дозволяє #v_p (k) # бути кратністю # p # як фактор # k #. Це, #v_p (k) # це найбільше ціле число, що # p ^ (v_p (k)) | k #.

Спостереження:

  • Для будь-якого #k у ZZ ^ + # і # p # простого, у нас є #v_p (k!) = sum_ (i = 1) ^ k v_p (i) #

    (Це можна легко довести за допомогою індукції)

  • Для будь-якого цілого числа #k> 1 #, ми маємо # v_2 (k!)> v_5 (k!) #.

    (Це інтуїтивно, як кратні повноважень #2# зустрічаються частіше, ніж кратні еквівалентної потужності #5#і може бути доведено строго, використовуючи аналогічний аргумент

  • Для #j, k у ZZ ^ + #, ми маємо #j | k <=> v_p (j) <= v_p (k) # для будь-якого простого дільника # p # з # j #.

Виходячи, наша мета - знайти найменше ціле число # n # такий, що # 10 ^ 2016 | n! #. Як # 10 ^ 2016 = 2 ^ 2016xx5 ^ 2016 #, потім третім спостереженням нам треба лише підтвердити це # 2016 <= v_2 (n!) # і # 2016 <= v_5 (n!) #. Друге спостереження означає, що останнє передбачає перше. Таким чином, достатньо знайти найменше ціле число # n # такий, що # v_5 (n!) = sum_ (i = 1) ^ nv_5 (i)> = 2016 #.

Знайти # n # ми зробимо спостереження, яке дозволить нам розрахувати # v_5 (5 ^ k!) #.

Між #1# і # 5 ^ k #, там є # 5 ^ k / 5 # кратні #5#, кожен з яких сприяє принаймні #1# до суми #sum_ (i = 1) ^ (5 ^ k) v_5 (i) #. Також є # 5 ^ k / 25 # кратні #25#, кожен з яких вносять додаткові #1# до суми після початкового підрахунку. Ми можемо йти таким чином, доки не досягнумо одного кратного # 5 ^ k # (який # 5 ^ k # сама), яка сприяла # k # разів до суми. Обчислюючи суму таким чином, ми маємо

# v_5 (5 ^ k!) = sum_ (i = 1) ^ (5 ^ k) v_5 (i) = sum_ (i = 1) ^ (k) 5 ^ k / 5 ^ i = sum_ (i = 1) ^ k5 ^ (ki) = sum_ (i = 0) ^ (k-1) 5 ^ i = (5 ^ k-1) / (5-1) #

Таким чином, ми знаходимо це # v_5 (5 ^ k!) = (5 ^ k-1) / 4 #

Нарешті, ми знайдемо # n # такий, що # v_5 (n!) = 2016 #. Якщо розрахувати # v_5 (5 ^ k!) # для декількох значень # k #, ми знайшли

# v_5 (5 ^ 1) = 1 #

# v_5 (5 ^ 2) = 6 #

# v_5 (5 ^ 3) = 31 #

# v_5 (5 ^ 4) = 156 #

# v_5 (5 ^ 5) = 781 #

Як #2016 = 2(781)+2(156)+4(31)+3(6)#, # n # потребує двох "блоків" Росії #5^5#, два з #5^4#, чотири з #5^3#, і три з #5^2#. Таким чином, ми отримуємо

#n = 2 (5 ^ 5) +2 (5 ^ 4) +4 (5 ^ 3) +3 (5 ^ 2) = 8075 #

Комп'ютер може швидко перевірити це #sum_ (i = 1) ^ (8075) v_5 (i) = 2016 #. Таким чином #10^2016 | 8075!#, і як #5|8075!# з кратністю #2016# і #5|8075#Зрозуміло, що не буде достатньо меншої вартості.