Точки і прямі • Микола Авілов • Науково-популярні завдання на "Елементи" • Математика

Точки і прямі

завдання

Як нас вчать в школі на уроках геометрії, через дві різні точки можна провести рівно одну пряму. Можна сказати, що пара точок визначає єдину пряму. Але якщо точок більше, то кількість обумовлених ними прямих може бути різним. Наприклад, три точки в залежності від свого розташування можуть визначати три прямі (якщо ці точки – вершини невиродженого трикутника) або одну пряму (якщо ці точки колінеарні, тобто лежать на одній прямій). Якщо точок ще більше, то різних можливостей їх взаємного розташування стає більше, тому і варіантів відповіді на питання "скільки прямих визначають ці n точок? "буде багато. Але в цьому завданні пропонується розібратися з конкретними конфігураціями точок, а деякі загальні питання обговоримо потім.

Мал. 1

а) На картатій папері візьмемо квадрат зі стороною п'ять клітин і відзначимо всі крапки всередині нього і на його кордоні – вийде 36 точок у вигляді квадратної решітки 6 × 6 (рис. 1). скільки прямих визначають ці точки? А якщо точок 64 (у вигляді решітки 8 × 8)?

б) Довжина ребер правильного тетраедра дорівнює 4. На кожному з них відзначені по три точки, що розбивають ребро на одиничні відрізки. Вершини тетраедра теж відзначені. скільки прямих визначають всі зазначені точки?


Підказка

Спробуйте порахувати прямі, які визначаються меншим числом точок – 4, 9 або 16 точками. Якщо відповіді вийдуть 6, 20 і 62 прямих, то ви на правильному шляху.

Головні труднощі в тому, що деякі прямі проходять тільки через дві відмічені точки, а деякі – через три і більше зазначених точок. При вирішенні задачі важливо організувати систему підрахунку прямих.


Рішення

Всі прямі розділимо на непересічні класи паралельних прямих. У кожен клас потрапляють прямі з одним кутовим коефіцієнтом k.

Мал. 2. Деякі з класів паралельних прямих

На рис. 2 вказані деякі класи прямих. Їх кутові коефіцієнти, крім 0 і 1, – це всілякі правильні нескоротні дроби, знаменник яких не більше 5. Щоб отримати взагалі все класи, потрібно враховувати симетрію картинки. Так що при підрахунку, – а отримані числа залишилося просто скласти, – кількість прямих в класах з k = 0 і k = 1 потрібно збільшити в два рази, а в інших класах – в чотири рази. У підсумку вийде 2 × (6 + 9) + 4 × (5 + 4 + 3 + 2 + 10 + 6 + 15 + 12 + 12) = 306 прямих.

Аналогічний підрахунок для 64 точок дасть 938 прямих.

Тепер розберемося з тетраедром. Це завдання можна відразу розглянути в загальному вигляді. Нехай каркас тетраедра з ребром довжини m розділений точками на одиничні відрізки.Скільки різних прямих визначають ці точки і вершини самого тетраедра?

У тетраедра 4 вершини і 6 ребер. Разом з вершинами і точками ділення на каркасі тетраедра відзначено 4 + 6 (m − 1) = 6m – 2 точки. Якби всі ці точки були в загальному положенні (тобто ніякі три з них не лежали б на одній прямій), то вони визначили б (6m − 2)(6m − 3)/2 = (3m − 1)(6m – 3) прямі (бо якщо точки знаходяться в загальному положенні, то будь-які дві з них визначають свою власну пряму). Тепер треба врахувати, що на кожному ребрі тетраедра відзначено по m + 1 точці загального положення. Будь ці точки в загальному положенні, вони б визначали m(m + 1) / 2 прямих. Але всі ці прямі збігаються – це пряма, яка містить дане ребро тетраедра. Значить, загальне число прямих, визначених зазначеними точками, так само (3m − 1)(6m − 3) − 6·m(m + 1) / 2 + 6. Після спрощення отримаємо 15m2 − 18m + 9 прямих. У нашій задачі m = 4, тому відповідь – 177 прямих.


Післямова

Якщо застосувати міркування, які ми використовували при відповіді на перше питання задачі, то можна знайти відповіді і для інших квадратів з n2 точок. Ось вони для n від 2 до 10: 6, 20, 62, 140, 306, 536, 938, +1492, 2306. Ця послідовність входить в Онлайн-енциклопедію цілочисельних послідовностей під номером A018808.

А чи є порівняно проста формула, яка б дозволила висловити число N таких прямих для довільного n? Спробуємо її пошукати.

Скористаємося двома відомими фактами з геометрії инцидентности.

1) Якщо на площині відзначити k точок загального положення (нагадаємо, що це означає, що ніякі три з цих точок не лежать на одній прямій), то число різних прямих, які визначаються цими точками, так само k(k − 1)/2.

Цим твердженням ми користувалися в рішенні, і воно легко доводиться по індукції.

2) Якщо на площині відзначити k точок, які не лежать на одній прямій, то вони визначають не менше k різних прямих.

Друге твердження звучить зовсім очевидно, проте воно вперше було доведено тільки в середині ХХ століття і відомо зараз, як теорема де Брёйна – Ердеша.

Спираючись на ці дві властивості можна зробити оцінки числа N(n). Використовуючи другий факт, отримаємо нижню оцінку: N(n) ≥ n2. Використовуючи перший факт, отримаємо верхню оцінку: N(n) ≤ n2(n2 – 1) / 2 – це число прямих, визначених n2 точками загального положення.

Це означає, що якщо існує формула N (n) у вигляді многочлена від n, – а це самий, напевно, простий вигляд формули, – то цей многочлен може мати тільки 2, 3 або 4 ступінь. Використовуючи наведені вище перші кілька значень N, Методом невизначених коефіцієнтів можна показати, що не існує формули у вигляді такого многочлена.

Спробуємо інший підхід і узагальнимо прийом підрахунку прямих розбиттям на класи паралельних. У кожен клас входять всі паралельні прямі з кутовим коефіцієнтом k = a/b (Тут і далі дроби – правильні нескоротні).

Так як будь-яка пряма на площині однозначно задається кутовим коефіцієнтом і однією точкою, то для кожного класу з k = a/b в точковому квадраті виділимо ті точки, які визначають всі прямі цього класу. При цьому можливі два випадки:
1) якщо b < n/ 2, то точки, які визначають прямі з кутовим коефіцієнтом a/b, Розташовані всередині блакитного і зеленого прямокутників, показаних зліва на рис. 3, і їх b·(na) + a·(n − 2b) = n·(a + b) − 3ab;
2) якщо bn/ 2, то точки, які визначають прямі з кутовим коефіцієнтом a/b, Розташовані всередині блакитного прямокутника, показаного праворуч на рис. 3, і їх (na) (nb).

Мал. 3. Точки, за допомогою яких можна задати всі прямі з даного класу в квадраті з 100 точок. Зліва приклад для k = 2/3, праворуч – для k = 2/7

число N(a/b) Прямих в класі c k = a/b дорівнює числу виділених точок, і обчислюється за знайденими вище формулами.

Тому, число N(n) Всіх прямих, заданих n2 точками можна обчислювати за формулою:

\ [N (n) = 2 (N_0 + N_1) +4 \ sum \ limits_ {b = 2} ^ {n-1} \ sum \ limits_ {a = 1} ^ {b-1} N \ left (\ frac ab \ right), \]

де N0 = n – число горизонтальних прямих, N1 = 2n – 3число прямих, паралельних діагоналі квадрата. Цю формулу нескладно запрограмувати і перевірити, що результати збігаються.

Можна отримати і рекурентні співвідношення на число прямих, визначених точковими квадратами, однак вони теж виходять досить громіздкими. За подробицями відсилаємо до статті S. Mustonen, 2009. On lines and their intersection points in a rectangular grid of points.

Міркування, які в рішенні були приведені для правильного тетраедра, працюють для будь-якого опуклого багатогранника, у якого всі ребра рівні між собою. Справді, там ніде не використовувалися ніякі специфічні для тетраедра властивості, враховувалося лише кількість його вершин і ребер. Так що міркування повторюються майже дослівно.

Нехай у багатогранника B вершин і P ребер. Разом з вершинами і точками ділення на каркасі багатогранника відзначено В + Р(m – 1) точок. Якби всі ці точки були в загальному положенні, то вони визначили б \ (\ frac12 (B + P (m-1)) (B + P (m-1) -1) \) прямих. Але на кожному ребрі багатогранника відзначено по (m + 1) точці, які, будь вони в загальному положенні, визначали б m(m + 1) / 2 прямих, але замість цього вони визначають тільки одну пряму, яка містить ребро. Значить, все їх потрібно відняти від загального числа і додати число прямих, що містять ребра. вийде

\ [\ Dfrac12 (B + P (m-1)) (B + P (m-1) -1) -P \ cdot \ dfrac12m (m + 1) + P. \]


Like this post? Please share to your friends:
Залишити відповідь

;-) :| :x :twisted: :smile: :shock: :sad: :roll: :razz: :oops: :o :mrgreen: :lol: :idea: :grin: :evil: :cry: :cool: :arrow: :???: :?: :!: