Умови задач з комбінаторики

Вишенський В.А., Перестюк М.О., Самоленко А.М.
Збірник задач з математики. — Київ, Либідь, 1993, 344 с. §5.
  1. У просторі взяли n "червоних" і m "синіх" точок, причому так, що жодні чотири з них не лежать в одній площині.
    1. Скільки є відрізків, у яких один кінець — червона точка, а інший — синя?
    2. Скільки є відрізків з обома червоними кінцями? з обома синіми кінцями?
    3. Скільки є трикутників, у яких усі вершни червоні? усі вершини сині? дві вершини червоні, а одна синя?
    4. Скільки є тетраедрів (трикутних пірамід), у яких усі вершини червоні? три вершини червоні, а одна синя? дві вершини червоні і дві вершини сині?
  2. На одній стороні трикутника взяли n точок, на другій — m точок, на третій — k точок, причому жодна з них не є вершиною трикутника.
    1. Скільки є трикутників з вершинами у цих точках?
    2. Скільки є чотирикутників з вершинами у цих точках?
  3. Прямі l1, l2, l3 паралельні і не лежать в одній площні. На l1 взяли n різних точок, на l2 — m різних точок, на l3 — k різних точок.
    1. Скільки є трикутників з вершинами у цих точках?
    2. Скільки є тетраедрів з вершинами у цих точках?
  4. На півколі взяли n різних точок, а на діаметрі, який стягує це півколо, взяли m різних точок, причому жодна з цих n + m точок не є кінцем діаметра.
    1. Скільки є трикутників з вершинами у цих точках?
    2. Скільки є чотирикутників з вершинами у цих точках?
  5. Кожну сторону квадрата поділили на n частин.
    1. Скільки є трикутників з вершинами у точках поділу?
    2. Скільки є чотирикутників з вершинами у точках поділу?
  6. На колі взяли n різних точок. Скільки є опуклих многокутників, вершини яких лежать у цих точках?
  7. Кожну сторону правильного 6-кутника поділено на n + 1 рівних частин. Скільки є прямокутників з вершинами у точках поділу, у яких є сторони, паралельні сторонам 6-кутника?
  8. На площині проведено n різних прямих, жодні три з яких не мають спільної точки і жодні дві не паралельні.
    1. У скількох точках попарно перетинаються ці прямі?
    2. На скільки частин вони поділяють площину?
    3. Скільки серед цих частин обмежених і скільки необмежених?
    4. Скільки є трикутників, усі три сторони яких лежать на цих прямих?
  9. У просторі проведено n різних площин так, що жодні чотири з них не проходять через спільну точку, жодні три не проходять через спільну пряму, і жодні дві не паралельні.
    1. Уздовж скількох прямих попарно перетинаються ці площини?
    2. Скільки є тетраедрів, грані яких лежать у проведених площинах?
    3. На скільки частин ці площини поділяють простір?
    4. Скільки серед цих частин обмежених і скільки необмежених?
  10. На площині проведено n різних кіл так, що кожні два з них перетинаються у двох точках і жодні три з яких не мають спільної точки. На скільки частин поділяють площину ці кола?
  11. Визначити кількість різних (не подібних між собою) членів розкладу (x1 + x2 + ... + xn)3.
  12. Коло поділено на n однакових частин. Скільки є не рівних між собою правильних многокутників, вершини яких лежать у точках поділу?
  13. Коло поділено на 100 однакових частин.
    1. Скільки є не рівних між собою правильних многокутників, вершини яких лежать у точках поділу?
    2. Скільки всього є правильних многокутників, вершини яких лежать у точках поділу?
  14. Скільки є різних (не рівних між собою) трикутників, сторони яких вимірюють цілими числами з проміжку (n, 2n]. Скільки серед них рівнобедрених трикутників і скільки рівносторонніх?
  15. Опуклий n-кутник має таку форму, що жодні його три діагоналі не мають спільної точки всередині n-кутника (діагональ — це відрізок, сполучає дві несуміжні, тобто не сполучені стороною, вершини многокутника).
    1. У скількох точках всередині n-кутника перетинаються попарно його діагоналі?
    2. Скільки є трикутників, утворених діагоналями n-кутника?
    3. На скільки частин діагоналі розтинають внутрішню частину n-кутника?
  16. Скільки є трицифрових натуральних чисел, у десятковому запису яких немає парних цифр? Знати суму всіх таких чисел.
  17. Скільки є трицифрових натуральних чисел, у десятковому запису яких немає непарних цифр? Знати суму всіх таких чисел.
  18. Скільки є п'ятицифрових натуральних чисел, десятковий запис яких містить цифру нуль?
  19. Скільки є п'ятицифрових натуральних чисел, у десятковому запису яких немає двох або більше однакових цифр, які стоять поряд?
  20. Скільки є шестицифрових натуральних чисел, десятковий запис яких містить три парні і три непарні цифри?
  21. Скільки є шестицифрових натуральних чисел, які мають парну суму цифр?
  22. Скільки є шестицифрових натуральних чисел, які не містять цимфри 0 у десятковому запису й діляться на 9?
  23. Скільки п'ятицифрових натуральних чисел, які діляться на 3, можна записати, використавши цифри 1, 2, 3, 4, 5, 6?
  24. Скільки чотирицифрових натуральних чисел, які діляться на 4, можна записати, використавши цифри 1, 2, 3, 4, 5?
  25. Обчислити суму всіх трицифрових натуральних чисел, які можна записати цифрами 1, 2, 3, 4?
    1. Скільки чотирицифрових натуральних чисел, які діляться на 25, можна записати, використавши цифри 2, 3, 4, 5, 6, 7, 8?
    2. Скільки серед них таких, у яких всі цифри різні?
  27. Скільки є п'ятицифрових натуральних чисел, у десятковому запису яких кожна наступна цифра менша від попередньої?
  28. Скільки є п'ятицифрових натуральних чисел, у десятковому запису яких кожна наступна цифра більша від попередньої?
  29. Скільки є п'ятицифрових натуральних чисел, у десятковому запису яких не всі цифри різні?
  30. Скільки є п'ятицифрових натуральних чисел, десятковий запис яких містить цифру 1 (одну або більше)?
  31. Скільки є чотирицифрових натуральних чисел, десяткоиий запис яких містить не менше як три різні цифри?
  32. Скількома способами з множини {1, 2, ..., 2n} можна вибрати три числа, які утворюють арифметичну прогресію з додатною різницею?
  33. Скільки є десятицифрових натуральних чисел, сума цифр яких дорівнює трьом?
  34. Скількома способами можна посадити за круглим столом шість осіб, якщо неістотно, хто на якому місці сидить, але істотно, хто кому буде лівим і правим сусідом?
  35. Скількома способами можна розташувати на шахівниці вісім тур одного кольору так, щоб вони не нападали одна на одну?
  36. Скількома способами можна розташувати на шахівниці дві тури різного кольору так, щоб вони не нападали одна на одну?
  37. Скільки є таких перестановок n елементів, у якій два виділені елементи a, b стоять поряд?
  38. Скільки є таких перестановок n елементів, у якій між двома виділеними елементами a, b стоять точно k елементів?
  39. У класі є p хлопчиків і q дівчаток.
    1. Скількома способами можна обрати редколегію класної газети з трьох учнів з умовою, щоб серед них обов'язково були хлопчики й дівчатка?
    2. Скількома способами можна вишикувати учнів класу в колону по одному так, щоб усі дівчатка стояли на чолі колони?
    3. Скількома способами можна вишикувати учнів класу в колону по одному так, щоб жодні дві дівчини не стоояли безпосередньо одна за одною?
    4. Скількома способами можна вишикувати учнів класу в колону по одному так, щоб усі дівчатка стояли поряд?
  40. Є p червоних і q синіх кубиків. Кубики всі однакові й відрізняються один від одного лише кольором.
    1. Скільки можна побудувати різних колон, ставлячи кубики один на одний?
    2. Скільки серед цих колон таких, в яких жодні два червоні кубики не лежать безпосередньо один на одному?
  41. Число 3 можна чотирма способами записати у вигляді суми натуральних чисел з урахуванням порядку доданків:

    3 = 1 + 1 + 1 = 2 + 1 = 1 + 2 = 3.

    Скількома способами можна записати так натуральне число n?

  42. Число 5 можна шістьма способами записати у вигляді суми трьох натуральних чисел з урахуванням порядку доданків:

    5 = 1 + 1 + 3 = 1 + 2 + 2 = 1 + 3 + 1 = 2 + 1 + 2 = 3 + 1 + 1 = 2 + 2 + 1.

    Скількома способами можна записати так натуральне число n у вигляді суми k натуральних чисел?

  43. Спираючись лише на комбінатшорний зміст біноміальних коефіцієнтів, довести тотожність: $$C^0_n - C^1_n + C^2_n - C^3_n +\cdots + (-1)^{n-1} C^{n-1}_n + (-1)^n C^n_n = 0.$$
  44. Нехай m, n — деякі натуральні числа. Скільки існує найкоротших маршрутів між точками (0, 0) та (m, n), ланки яких сполучають точки з цілими координатами і спрямовані вертикально або горизонтально.
  45. Придумати комбінаторну модель тотожності: $$(C^0_n)^2 + (C^1_n)^2 + (C^2_n)^2 + \cdots + (C^n_n)^2 = C^n_{2n}.$$