Розв'язник вправ по дискретній математиці/Комбінаторика

Розв'язник вправ по дискретній математиці. Комбінаторика

Задача 1

а) Яких чисел більше серед цілих чисел першої тисячі (включаючи і 1000): в записі яких є одиниця, або інших? б) Яких семизначних чисел більше: тих, в запису яких є одиниця, або інших?

Розв'язання.  

а) Є $8^{3}=512$ тризначних чисел, що не містять 1 і 0. Це вже більше половини чисел першої тисячі.

Відповідь: більше чисел, в запису яких немає одиниці;

б) Підрахуємо кількість чисел, в запису яких немає одиниці. На першому місці може стояти кожна з 8 цифр (0 і не 1), на кожному з решти - будь-яка з 9 цифр, відмінних від 1. Всього отримуємо $8*9^{6}$ чисел, що становить менше половини від кількості 9 · 10^6 всіх семизначних чисел.

Відповідь: більше чисел, в запису яких є ​​одиниця.

Задача 2

Скількома способами 3 людини можуть розділити між собою 7 однакових яблук, один апельсин, одну сливу і один мандарин?

Розв'язання.  

Формула для розподілу k однакових речей серед n різних людей: F (k, n) = C (n-1, n + k-1);

C(2,9)=9!/(7!*2!)= 36;

"Поодинокі" фрукти можуть дістатися кожному з трьох, тоді: $36*3^{3}=972$ способів.

Відповідь: 972 способів;

Задача 3

• Розв'язати завдання з leetcode.com (Count Sorted Vowel Strings). Нехай дане ціле число n — потрібно повернути кількість рядків довжини n, які складаються лише з голосних (a, e, i, o, u) та є лексикографічно впорядкованими.

Рядок s вважається лексикографічно впорядкованим, якщо для всіх допустимих i символ s[i] такий самий або йде перед s[i+1] в алфавіті.

Приклад 1:  

Input: n = 1

Output: 5

Пояснення: 5 лексикографічно впорядкованих рядків, що складаються лише з голосних: ["a","e","i","o","u"].

Приклад 2:  

Input: n = 2

Output: 15

Пояснення: 15 впорядкованих рядків з голосних: ["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"]. Зверніть увагу: "ea" — невалідний рядок, бо 'e' йде після 'a' в алфавіті.

Приклад 3:  

Input: n = 10

Output: 1001

Задача 4

• Розв'язати завдання з leetcode.com (Pairs of Songs With Total Durations Divisible by 60). Дано список пісень, де i-та пісня має тривалість time[i] секунд.

Потрібно повернути кількість пар пісень, для яких сумарна тривалість у секундах ділиться на 60. Формально, знайти кількість індексів i, j, таких що i < j і виконується умова: (time[i] + time[j]) % 60 == 0.

Приклад 1:  

Input: time = [30,20,150,100,40]

Output: 3

Пояснення: Три пари мають сумарну тривалість, кратну 60:

(time[0] = 30, time[2] = 150): сумарна тривалість 180

(time[1] = 20, time[3] = 100): сумарна тривалість 120

(time[1] = 20, time[4] = 40): сумарна тривалість 60

Приклад 2:  

Input: time = [60,60,60]

Output: 3

Пояснення: Усі три пари мають сумарну тривалість 120, яка ділиться на 60.

Приклад 3:  

Input: time = [418,204,77,278,239,457,284,263,372,279,476,416,360,18]

Output: 1

Пояснення: (457 + 263) — лише одна пара, яка задовольняє умову.

Задача 5

• Розв'язати завдання з leetcode.com (62. Unique Paths). На сітці m x n знаходиться робот. Спочатку робот знаходиться у лівому верхньому куті (тобто grid[0][0]). Робот намагається переміститись у правий нижній кут (тобто grid[m - 1][n - 1]). У довільний момент часу робот може рухатись лише вниз або праворуч.

За заданими двома цілими числами m та n виведіть кількість можливих унікальних шляхів, якими робот може дістатись до правого нижнього кута.

Приклад 1:  

Вхідні дані: m = 3, n = 2

Результат: 3

Пояснення: З лівого верхнього кута можна дістатись до правого нижнього кута 3 способами:

1. Праворуч -> Вниз -> Вниз

2. Вниз -> Вниз -> Вправо

3. Вниз -> Вправо -> Вниз

Задача 6

• Розв'язати завдання з leetcode.com (3185. Count Pairs That Form a Complete Day II). За заданим цілочисельним масивом hours, що представляє час у годинах, поверніть ціле число, яке позначає кількість пар i, j, де i < j за умови, що hours[i] + hours[j] утворюють повний день.

Повна доба визначається як тривалість часу, яка кратна 24 годинам.

Наприклад, 1 день - це 24 години, 2 дні - 48 годин, 3 дні - 72 години і так далі.

Приклад 1:  

Вхід: hours = [12,12,30,24,24]

Результат: 2

Пояснення: Парами індексів, які формують повний день, є (0, 1) та (3, 4).

Приклад 2:  

Вхід: hours = [72,48,24,3]

Результат: 3

Пояснення: Парами індексів, які формують повний день, є (0, 1), (0, 2) та (1, 2).