Зростаючий порядок цифр

Задача. Зростаючий порядок цифр у натуральному числі

Скільки існує  n-цифрових чисел,  усі цифри яких записані в строго зростаючому порядку, якщо вважати правильними n-цифрові  записи чисел:  000..01 =1, 00..0012=12, 000…000123=123 і так далі

Розв'язання. Зрозуміло, що треба розглядати випадок, коли  n<11.

Спочатку знайдемо кількість  10-цифрових чисел,  у яких усі цифри різні і розташовані у довільному порядку.

 В розряд одиниць такого 10-цифрового числа   можна записати 10-ма способами будь-яку цифру, бо різних цифр 10: {0;1;2;3;4;5;6;7;8;9}.

В розряд десятків такого 10-цифрового числа   можна записати  9 способами деяку цифру,  бо 10-1=9 цифр, так як одна цифра уже стоїть в розряді одиниць, тобто використана.

В розряд сотень такого 10-цифрового числа   можна записати 8 способами деяку цифру, бо 10-2=8 цифр, так як дві цифри уже стоять в розряді одиниць та десятків, тобто використані.

Аналогічно міркуємо  до    розряду одиниць мільярдів, в який можна буде записати лише одним способом  цифру.  Скористаємося правилом добутку, отримаємо, що  існує 10!=1*2*3*4*5*6*7*8*9*10=3628800 чисел,  у яких усі цифри різні і розташовані у довільному порядку.

Порахуємо кількість десятицифрових чисел, усі цифри яких записані в строго зростаючому порядку.

З десяти різних цифр можна утворити  3628800 10-цифрових чисел, у яких цифри не повторюються і розташовані в довільному порядку, серед  яких  лише в одному випадку цифри розташовані в зростаючому порядку. Тому шукані числа становитимуть  1/3628800 всіх 10-цифрових чисел з різними цифрами.

Тепер  знайдемо кількість  9-цифрових чисел,  у яких усі цифри різні і розташовані у довільному порядку.

 В розряд одиниць такого 9-цифрового числа   можна записати 10-ма способами будь-яку цифру, бо різних

одна цифра уже стоїть в розряді одиниць, тобто використана.

В розряд сотень такого 9-цифрового числа   можна записати 8 способами деяку цифру, бо 10-2=8 цифр, так як дві цифри уже стоять в розряді одиниць та десятків, тобто використані.

Аналогічно міркуємо  до    розряду сотень мільйонів, в який можна буде записати лише одним способом  цифру, бо різних  цифр 10: {0;1;2;3;4;5;6;7;8;9}.

В розряд десятків такого 9-цифрового числа   можна записати  9 способами деяку цифру,  бо 10-1=9 цифр, так як.  Скористаємося правилом добутку, отримаємо, що  існує 2*3*4*5*6*7*8*9*10=3628800 чисел,  у яких усі цифри різні і розташовані у довільному порядку.

Порахуємо кількість дев'ятицифрових чисел, усі цифри яких записані в строго зростаючому порядку.

З десяти різних цифр можна утворити  3628800 9-цифрових чисел, у яких цифри не повторюються і розташовані в довільному порядку.  З дев'яти різних цифр утворюємо різні перестановки, серед  яких  лише в одному випадку цифри розташовані в зростаючому порядку. Тому шукані числа становитимуть  1/9! всіх 9-цифрових чисел з різними цифрами.  3628800/9!=10 чисел, що мають 9 різних цифр і розташовані в зростаючому порядку.

Тепер  знайдемо кількість  8-цифрових чисел,  у яких усі цифри різні і розташовані у довільному порядку.

 В розряд одиниць такого 8-цифрового числа   можна записати 10-ма способами будь-яку цифру, бо різних  10 цифр.

В розряд десятків такого 9-цифрового числа   можна записати  9 способами деяку цифру,  бо 10-1=9 цифр, так як одна цифра уже стоїть в розряді одиниць, тобто використана.

В розряд сотень такого 8-цифрового числа   можна записати 8 способами деяку цифру, бо 10-2=8 цифр, так як дві цифри уже стоять в розряді одиниць та десятків, тобто використані.

Аналогічно міркуємо  до    розряду десятків  мільйонів, в який можна буде записати лише одним способом  цифру, бо різних цифр 10: {0;1;2;3;4;5;6;7;8;9}.

Скористаємося правилом добутку, отримаємо, що  існує 3*4*5*6*7*8*9*10=1814400 чисел,  у яких усі цифри різні і розташовані у довільному порядку.

Порахуємо кількість 8-цифрових чисел, усі цифри яких записані в строго зростаючому порядку.

З десяти різних цифр можна утворити  1814400 8-цифрових чисел, у яких цифри не повторюються і розташовані в довільному порядку.  З восьми  різних цифр утворюємо різні перестановки, серед  яких  лише в одному випадку цифри розташовані в зростаючому порядку. Тому шукані числа становитимуть  1/8! всіх 9-цифрових чисел з різними цифрами.  1814400/8!=45 чисел, що мають 8 різних цифр і розташовані в зростаючому порядку.

Тепер  знайдемо кількість  7-цифрових чисел,  у яких усі цифри різні і розташовані у довільному порядку.

 В розряд одиниць такого 7-цифрового числа   можна записати 10-ма способами будь-яку цифру, бо 10 різних цифр.

В розряд десятків такого 7-цифрового числа   можна записати  9 способами деяку цифру,  бо 10-1=9 цифр.  

В розряд сотень такого 7-цифрового числа   можна записати 8 способами деяку цифру, бо 10-2=8 цифр, так як дві цифри уже стоять в розряді одиниць та десятків, тобто використані.

Аналогічно міркуємо  до    розряду одиниць  мільйонів, в який можна буде записати лише одним способом  цифру, із різних цифр 10: {0;1;2;3;4;5;6;7;8;9}.

Скористаємося правилом добутку, отримаємо, що  існує 4*5*6*7*8*9*10=604800 чисел,  у яких усі цифри різні і розташовані у довільному порядку.

Порахуємо кількість 7-цифрових чисел, усі цифри яких записані в строго зростаючому порядку.

З десяти різних цифр можна утворити  604800 7-цифрових чисел, у яких цифри не повторюються і розташовані в довільному порядку.  З 7  різних цифр утворюємо різні перестановки, серед  яких  лише в одному випадку цифри розташовані в зростаючому порядку. Тому шукані числа становитимуть  1/7! всіх 9-цифрових чисел з різними цифрами.  604800/7!=120 чисел, що мають 8 різних цифр і розташовані в зростаючому порядку.

І так далі.

Для 6-цифровиих отримаємо: 151200/6!=210 чисел, у яких цифри розташовані у зростаючому порядку.

Для 5-цифровиих отримаємо: 30240/5!=252 чисел, у яких цифри розташовані у зростаючому порядку.

Для 4-цифровиих отримаємо: 5040/4!=210 чисел, у яких цифри розташовані у зростаючому

 Для 3-цифровиих отримаємо: 720/3!=120 чисел, у яких цифри розташовані у зростаючому порядку.

Для 2-цифровиих отримаємо: 90/2!=45 чисел, у яких цифри розташовані у зростаючому порядку.

Для 1-цифровиих отримаємо: 10/1!=10 чисел, у яких цифри розташовані у зростаючому порядку.

Загальна кількість натуральних чисел,   у яких цифри розташовані у зростаючому порядку: 2(10+45+120+210)+252 =1022 (враховуючи і одноцифрові натуральні числа та нуль)

                 

Стратегічна задача на оптимізацію кількості інформаційних зв’язків

Стратегічна задача на  оптимізацію кількості

 інформаційних  зв’язків між користувачами.

У деякій освітній системі є n працівників. Між деякими із них здійснюються двосторонні мобільні зв'язки.

 Відомо, що з мобільного телефону будь-якого працівника можна додзвонитися до будь-якого мобільного іншого працівника. 

Провайдер-фірма хоче вибрати декілька працівників і назвати їх вузловими  операторами таким чином, що із будь-якого  мобільного системи освіти існує прямий зв'язок до деякого вузлового оператора системи освіти. 

Яку найменшу  кількість вузлових міст треба обрати, щоб гарантовано, навіть у найгіршому випадку, вистачило усіх цих  зв'язків  провайдер-фірмі.

Відповідь: m(n)=n-[n/3]-1.

Вказівка. Переформулюємо умову задачі на мові теорії графів. Потрібно знайти таке мінімальне число s,  що у будь-якому зв’язному графі, у якого n вершин можна відмітити не більше ніж s його вершин таким чином, що у будь-якої вершини знайдеться відмічена сусідня вершина(вважаємо,  що сусідня вершина зветься сусідкою).

Доведемо, що s >= n-[n/3]-1. Розглянемо граф з чотирма вешинами v⁽⁰⁾, v⁽¹⁾_j, v⁽²⁾ _j, v⁽³⁾_j , j = 1, . . . , [n/3], та ребрами (v⁽⁰⁾, v⁽¹⁾_j), (v⁽¹⁾, v⁽²⁾_j),  (v⁽²⁾, v⁽³⁾_j), j = 1, . . . , [n/3].

Нехай k - довільне число від 1 до [n/3]. У вершин v⁽²⁾ _k, v⁽³⁾_k  повинна бути відмічена сусідка, а це значить обов’язково буде відмічена v⁽²⁾ _k, як єдина сусідка v⁽³⁾_k  і одна з вершин v⁽¹⁾_j, v⁽³⁾_j повинна бути відмічена, оскільки інших сусідів у   v⁽²⁾ _k  немає. Таким чином, всього повинно бути відмічено  не менше  2*[n/3]-1 вершини.

Доведемо, що s <= n-[n/3]-1. Можна вважати, що заданий граф являється деревом, так як в протилежному випадку можна виділити скріплююче дерево і довести твердження для нього.  Виберемо в якості кореня висячу вершину і назвемо її v⁽⁰⁾,а інші розташуємо по рівнях стандартним чином.  Розфарбуємо вершини в три кольори так, що  вершини на рівнях 3k+1 пофарбовані в один колір, на рівнях виду 3k+2 пофарбовані в другий колір, а інші в третій колір. За принципом Діріхле знайдеться такий колір, в який пофарбовано що найменше  [n/3]+1 вершини. Відмітимо вершини інших кольорів. Тоді ми відмітили не більше n-[n/3]-1 вершин, і у будь-якої невисячої вершини є відмічена сусідня вершина. Нехай v – висяча вершина(v не дорівнює v⁽⁰⁾),  нехай v₁ – батько– батько v₁. ВІдмітимо, що v₂ існує, так як рівнів не менше трьох. Якщо у v не існує відміченої v, v₂ сусідньої вершини, то v₁ – невідмічена, а значіть, відмічені  v та  v₂. Приберемо мітку з вершини v, та відмітимо вершину v₁. Тоді кількість відмічених вершин не зміниться, у всіх вершин, у яких   була відмічена сусідка, вона залишається, а також вона і у вершини v тепер буде відмічена сусідка. Аналогічно зробимо для кореневої вершини. Зробивши, при необхідності подібну операцію скінчену кількість разів, ми отримаємо те, що у всіх вершин була відмічена сусідка. Що і вимагало довести.