Umovi-ta-rozvyazannya-1-tur


Міністерство освіти і науки України
Київський міський педагогічний університет імені Б.Д. Грінченка
Київський національний університет імені Тараса Шевченка
ІІІ етап Всеукраїнської
олімпіади з математики
LXХ Київська міська
олімпіада юних математиків
Умови та вказівки до розв’язань задач
1 тур
18 січня 2015 року
7 клас
1. Порівняйте з нулем число , де:
а) ;
б) .
Тут у кожному з пунктів знаки перед послідовними числами йдуть таким чином – спочатку один «+», а далі по черзі по два знаки «-» та по два «+» і перед останнім числом знак «+».
Відповідь: а) ; б) .
Розв’язання. а) Якщо розбити усі числа по 4 зліва направо на 504 групи, то у кожній такій групі будуть числа такого типу:
.
Як бачимо їх сума дорівнює у кожні групі. А тому й .
б) Аналогічно доведенню пункту а), розіб’ємо їх на групи по 4: . Тоді у кожній групі сума чисел додатна:
.
1
1
2
2
3
Рис. 1









2. Розріжте квадрат на 3 частини прямолінійними розрізами так, щоб з одержаних частин можна було скласти тупокутний трикутник.
Після першого розрізу перекладати частини розрізаного квадрату не можна.
Відповідь: один з варіантів розрізання показаний на рис. 1.
Розв’язання. На рис. 1 точки та середини відповідних сторін квадратів. Тоді та , звідки стає зрозумілим, що з одержаних частин утворюється тупокутний .
3. Назвемо номер року барвистим, якщо в його десятковому записі жодна цифра не повторюється. Наприклад, роки з 2013 по 2019 – барвисті, а 2020 – ні.
а) Знайдіть, коли наступного разу утвориться ланцюжок з семи барвистих років поспіль.
б) Чи може в майбутньому з’явитися такий ланцюжок, що містить більше семи барвистих років?
(Рожкова Марія)
Відповідь: а) 2103, …, 2109; б) не може.
Розв’язання. а) Покажемо, що найближчий барвистий ланцюжок довжини 7 – це роки з 2103 по 2109. Спершу доведемо, що у цьому сторіччі довжина барвистого ланцюга не більше 6. Дійсно, цифри 0 та 2 заборонені для запису розрядів одиниць і десятків. Отже, у кожному десятку шуканий ланцюг переривається, якщо цифра одиниць 0 або 2. Лишається така можливість утворити ланцюг довжиною 7:
20*3, 20*4, …, 20*9.
Замість * можна обрати лише 1, але ця цифра вже «спрацювала» в умові задачі.
У наступному сторіччі, після 2100 року, легко знаходиться шукана послідовність: 2103, …, 2109.
б) Маємо справу з числами, записаними щонайменше чотирма цифрами. У барвистому ланцюгу не може бути числа **99, тому цифра сотень року незмінна. А тоді для запису одиниць може використовуватись щонайбільше 8 цифр.
Припустимо, що барвистий ланцюг містить 8 чисел. Розглянемо два випадки.
1. Усі числа ланцюга містять однакову кількість десятків. Тоді на одиниці лишається 7 вільних цифр. Суперечність.
2. У шуканому ланцюгу відбувається «перехід через десяток». Цифра десятків при цьому не може бути 9. Нехай ця цифра QUOTE x та змінюється на . QUOTE x+1. У ланцюгу 8 чисел, тому обов'язково є наступні два числа:
, QUOTE a b x x+1 .
Наприклад, це 2145 та 2154. Але тоді у ланцюгу щонайменше 10 чисел (наприклад, від 2145 по 2154). Знову суперечність.
4. Квадрат розбито на 81 квадратик , 8 з яких пофарбовано у чорний колір, а решта – у білий. З квадрата вирізають повністю білий прямокутник (або квадрат). Яку найбільшу площу може гарантовано мати цей прямокутник? Вирізати дозволяється лише вздовж ліній, які розділяють квадрат на одиничні квадратики.
(Рубльов Богдан)
Рис. 2
Відповідь: .
Розв’язання. Розріжемо весь квадрат на 9 квадратів , оскільки чорних квадратиків рівно 8, то принаймні в одному з цих квадратів немає чорних квадратиків. Тому квадрат площею завжди можна вирізати.
Покажемо, що більшого розміру не завжди можна вирізати. Для цього достатньо пофарбувати в чорний колір квадратики, як це показане на рис. 2. Тут можна вирізати або квадратик , або прямокутник , більшої площі прямокутник вирізати не можна.
3.1. Доведіть, що 2015-цифрове число не є простим.
Розв’язання. Запишемо задане число таким чином:
,
а тому не є простим.
4.1. По колу рівномірно розкладені 2015 цукерок, які за рухом годинникової стрілки перенумеровані числами від 1 до 2015. Андрій та Олеся грають у таку гру – вони по черзі беруть розкладені цукерки. За один хід можна взяти 2 чи 3 цукерки, номера яких є послідовними числами (вважаємо, що 1 та 2015 також є «послідовними»). Програє той, хто не може зробити черговий хід. Хто переможе у цій грі, якщо першим ходить Андрій та кожен намагається виграти?
Відповідь: Олеся переможе.
Розв’язання. Своїм ходом Андрій бере деякі 2 (або 3) цукерки, що лежать поруч. Олеся своїм ходом бере 3 (або 2 цукерки) протилежні по колу взятим Андрієм, таким чином, щоб між групами взятих цукерок стало порівну (а саме по 1005) цукерок. Далі вона просто копіює хід Андрія на іншій частині кола. Якщо Андрій може зробити хід, то й Олеся може його зробити. А тому вона не може програти. Оскільки гра закінчиться, то програє Андрій.
8 клас
1. Троє велосипедистів стартують одночасно та їдуть по сторонах трикутника у порядку: Відомі їх швидкості на кожному з відрізків : у першого велосипедиста вони дорівнюють відповідно 12, 10 та 20 км/год, у другого – 15, 15 та 10 км/год, у третього – 10, 20 та 12 км/год. Яким може бути значення кута , якщо відомо, що вони прибули в точку одночасно?
Відповідь: .
Розв’язання. Позначимо довжини сторін як , , , тоді повинна справджуватись така рівність:
або .
Звідси та . Тоді звідси одержимо, що та . Тобто - рівносторонній, а тому усі кути по .
2. Чи можна з усіх 10 цифр 0, 1, ..., 9, використавши кожну цифру рівно один раз, утворити два числа, одне з яких є квадратом іншого?
Цифра 0 не може стояти на першому місці в жодному з чисел.
Відповідь: не можна.






Рис. 3
Розв’язання. Якщо число має 3 цифри, то його квадрат не більше 6 цифр, разом виходить не більше 9 цифр. Якщо число має не менше 4 цифр, то його квадрат не менше 7 цифр, тобто разом не менше 7 цифр. Таким чином шуканих чисел не існує.
3. У рівнобедреному трикутнику провели бісектрису , а у трикутнику – бісектрису . Знайдіть величини кутів трикутника , якщо відомо, що бісектриси кутів та перетинаються на прямій .
(Федак Іван)
Відповідь: , .
Розв’язання. Нехай – точка перетину бісектрис кутів та (рис. 3). Тоді ця точка знаходиться на відрізку і є рівновіддаленою як від променів та , так і від променів та . А отже, вона буде рівновіддалена також від променів та . Тому – бісектриса . Звідси та з умови задачі випливає, що . А оскільки , то . Отже, остаточно отримуємо:
, .
4. Задача № 4 за 7 клас.
5. Чи можна утворити трикутник з відрізків , якщо вони задовольняють рівність:
?
(Рубльов Богдан)
Відповідь: не можна.
Розв’язання. Задану рівність перепишемо таким чином:
.
Ліва частина розкладається на множники таким чином:
.
Звідси маємо, що ліва частина від’ємна, а тому принаймні один з множників від’ємний. Перший завжди додатний, тому від’ємним є, наприклад, другий, тобто , а це суперечить нерівності трикутника.
4.1. У комітеті утворили 4 підкомітети, кожним з яких керують по 3 людини з комітету. Для узгодження їхніх дій, кожні два підкомітети серед керівників мають рівно одного спільного члена. Яка найменша кількість людей може бути в комітеті?
Відповідь: .
Розв’язання. Якщо розглянути керівництво двох підкомітетів, то вони мають рівно одного 1 спільного члена, тоді разом вони містять рівно 5 членів. Таким чином усього в комітеті мінімум 5 людей, позначимо їх числами: . Але з цих 5 членів вибрати керівництво ще одного підкомітету неможливо. Таким чином у комітеті мінімум 6 людей. З них можна утворити керівництво підкомітетів належним чином:
.
5.1. Для яких цілих чисел існують такі цілі числа , що виконується рівність:
?
(Рубльов Богдан)
Відповідь: для будь-яких чисел однакової парності.
Розв’язання. Якщо однакової парності, то задамо цілі числа такими рівностями:
, .
Тоді очевидно, що вони цілі, і простою підстановкою в задане рівняння переконуємось, що вони йому задовольняють.
Якщо різної парності, то права частина заданого рівняння є непарним числом. Дійсно, якщо, наприклад, - парне, а - непарне, то - парне, а - непарне, а тому задана рівність неможлива.
9 клас
1. Задача № 1 за 8 клас.
2. У січні Петрик щоденно купляв собі від однієї до трьох машинок. Першого лютого він спробував усі куплені машинки розставити у прямокутник. Коли він розставив їх в ряди по 7 машинок у кожному ряді, то виявилась 1 зайва машинка. Коли розставив в ряди по 10 машинок, то зайвими лишилися 2 машинки. Чи зможе Петрик розставити їх в ряди по 4 машинки?
Відповідь: так.
Розв’язання. Для деяких натуральних повинна виконуватись рівність:
або .
Тобто треба знайти число між та , яке закінчується на цифру та ділиться на . Найменшим таким число є , але воно менше за . Наступним числом є число . Зрозуміло, що інших чисел не існує у вказаному проміжку. Таким чином усього машинок у Петрика:
Рис. 4









.
Оскільки , то розставити в ряд по він зможе.
3. Відомо, що у дану прямокутну трапецію можна вписати квадрат таким чином, щоб кожна його вершина лежала на відповідній стороні трапеції (жодна з вершин квадрата не співпадає з вершиною трапеції). Побудуйте цей вписаний квадрат за допомогою циркуля і лінійки.
(Рожкова Марія)
Розв’язання. Аналіз. Нехай - дана трапеція з прямими кутами при вершинах та , - шуканий квадрат із центром у точці , при цьому , . У чотирикутнику QUOTE EBFO два протилежні кути прямі, тому навколо нього можна описати коло. Звідси , як вписані кути, що спираються на дугу (рис. 4). Аналогічно . Отже в точці перетинаються бісектриси внутрішніх кутів при вершинах та трапеції. Крім того, точки симетричні відносно точки .
Побудова. Будуємо точку як перетин бісектрис кутів при вершинах та трапеції. Далі будуємо пряму , що симетрична прямій відносно точки . Пряма перетинає відрізок у єдиній точці , що є шуканою вершиною квадрата. Знаючи центр квадрату та одну з його вершин, зрозуміло, що такий квадрат єдиний і він відновлюється очевидним чином.
4. Для додатних чисел доведіть нерівність:
.
Розв’язання. Декілька разів застосуємо нерівність між середніми:

.
5. Квадрат розбито на 121 квадратик , 4 з яких пофарбовано у чорний колір, а решта – у білий. З квадрата вирізають повністю білий прямокутник (або квадрат). Яку найбільшу площу може гарантовано мати цей прямокутник? Вирізати дозволяється лише вздовж ліній, які розділяють квадрат на одиничні квадратики.
(Рубльов Богдан)
Відповідь: .
Розв’язання. Спочатку розставимо чорні клітини, як це показане на рис. 5, тоді неважко збагнути, що вирізати можна квадрат площею і це найбільша можлива площа для прямокутника.
1
Рис. 5
113
7
9
5











Тепер покажемо, що це максимальна можлива площа. Методом від супротивного, припустимо, що існує таке розташування чорних квадратиків, при якому максимальна площа прямокутника, що можна вирізати не перевищує . Це означає, що який би ми не вибрали прямокутник розміром чи більше, то там повинна бути чорна клітина. Для зручності занумеруємо поля на кшталт шахової дошки (рис. 5). Горизонталі позначимо числами знизу до гори від 1 до 11, а вертикалі зліва направо українськими літерами: а, б, ,.., і. Будемо називати клітини сірими, якщо в них точно не повинна бути чорна клітина.
Якщо вирізати квадрати з такими кутами: (а1-д5), (е1-и5), (а6-д10), (е6-и10). Тому сірими є 11-та горизонталь та стовпчик і, аналогічно сірими є горизонталь 1 та стовпчик а.
1
Рис. 6
113
7
9
5






Якщо вирізати квадрати з такими кутами: (а1-д5), (є1-і5), (а7-д11), (є7-і11). Тому сірими є 6-та горизонталь та стовпчик е (середні стовпчики та рядок) (рис. 6).
Припустимо, що чорний квадратик є принаймні в одній з ліній б, и чи 2, 10. Наприклад, у вертикалі б, Тоді є чорні квадратики у прямокутника з кутами в1-і3 та в9-і11. Кожен з них має площу . Тоді на прямокутник в4-і8 завбільшки , який розбивається на два прямокутники в4-і6 та в6-і8, у кожному з них повинна бути чорний квадрат. Тому він вимушений бути на їх спільній горизонталі 6. Але за доведеним, ця горизонталь сіра, одержана суперечність показує, що сірою є частина квадрата, як на рис. 7.
1
Рис. 7
113
7
9
5






Зрозуміло, що в кожному з чотирьох квадратів повинний знаходитись рівно 1 чорний квадратик. Якщо чорним є принаймні один з квадратиків в3, в9, з3, з9. Наприклад, в9. Тоді у двох прямокутниках г7-ж11 та а6-і8. Тому чорний квадратик повинен бути є7-ж8. Аналогічно у г4-д5. Тоді чорним зобов’язаний бути квадратик з3. З прямокутників а1-г8 та а1-ж4 чорним повинен бути квадратик г4, аналогічно ж8. Але тоді вільним є прямокутник д1-є11. Таким чином жовтими є усі 4 квадратики в3, в9, з3, з9. Але тоді повинні рівно по 1 чорному квадратику повинно бути в смугах в4-в8, г9-ж9, г3-ж3, з4-з8. Але тоді вільним залишиться центральний квадрат г4-ж8. Одержана суперечність завершує доведення.
4.1. Для додатних чисел доведіть нерівність:
.
Розв’язання. Застосуємо двічі нерівність між середніми:
.
5.1. Маємо 9 гир, на яких написано, що вони важать 1г, 2г, 3г, ..., 9г відповідно. Відомо, що рівно одна з гир важить легше, ніж на ній зазначено, а решта рівно стільки, скільки на них зазначено. Чи можна на терезах з двома шальками без додаткових гир визначити хибну гирю не більше ніж за 2 зважування?
Відповідь: так, можна.
Розв’язання. Покладемо на шальки при першому зважуванні гирі на ліву та на праву. Якщо маємо рівність , то фальшива гиря серед інших трьох.
Тоді покладемо на шальки, наприклад, такі комбінації: та .
Якщо , то ці гирі – справжні, тому фальшива .
Якщо , то фальшива , бо фальшива – більш легка і там її треба шукати. З урахуванням першого зважування нею є .
Аналогічно, при фальшивою є .
Аналогічно, якщо при початковому зважуванні вийшла нерівність, то фальшива там, де менша вага. Решта шість гир справжні. Залишається покласти на різні шальки по одній потенційно фальшивій і врівноважити їх справжніми. Наприклад, та . Далі все аналогічно, фальшива на більш легкій шальці терезів, при рівновазі – та, що не покладена.
10 клас
1. Для довільних попарно різних додатних чисел розв’яжіть рівняння:
.
(Рубльов Богдан)
Відповідь: .
Розв’язання. Зрозуміло, що його можна спробувати розв’язати перетвореннями, спочатку звести до квадратного і далі за відомою схемою.
Ми запропонуємо дещо інший підхід. Позначимо ліву частину , а праву – . Неважко переконатись, що та . Але це означає, що різні числа є коренями цього рівняння. Порівнюючи коефіцієнт зліва і справа при , бачимо, що це рівняння є квадратним. А тому усі корені рівняння.
2. Знайдіть найменше натуральне число , для якого існують такі натуральні числа , що виконується рівність: .
(Рубльов Богдан)
Відповідь. .
Розв’язання. Очевидно, що . Якщо , де , то з рівності , спочатку маємо, що . Але тоді при будь-якому друга цифра з кінця добутку дорівнює при та при , то ж ніколи не вийде. Таким чином . Очевидно, що умову не задовольняє, бо . А от значення – шукане, бо .
3. Вінні-Пух і П’ятачок грають у гру за такими правилами. Є палиця довжиною 15 см. Першим ходом П’ятачок розламує її на дві частини, далі гравці по черзі розламують на дві частини один із наявних шматків. При цьому, шматки повинні мати натуральну довжину (в сантиметрах) і не можуть дорівнювати 1 см. Програє той, хто не може зробити хід. У кого з гравців є виграшна стратегія?
(Чорний Максим)
Відповідь. У П’ятачка.
Розв’язання. Очевидно, що в кінці гри залишаться тільки шматки довжиною 2 і 3 см, при цьому П’ятачок виграє тоді і тільки тоді, коли їхня кількість парна (це означає, що була зроблена непарна кількість ходів, тому останнім ходив П’ятачок). Є три можливі варіанти кінцевого положення:
.
Звідси видно, що П’ятачку для перемоги достатньо гарантувати собі наявність двох шматків по 3 см і одного шматка на 2 см (це унеможливить перший і третій варіанти). Тому на першому ході він розламує палицю на шматки 5 см і 10 см, перший з яких гарантовано рано чи пізно буде розламаний на 2 см і 3 см. Якщо Вінні-Пух наступним ходом розламує палицю 10 см, П’ятачок має право відламати 3 см від більшого шматка, якщо ні - просто розламати 10 см на 3 см і 7 см. У такому разі, незалежно від подальших дій гравців, наприкінці гри будуть принаймні 2 шматки довжиною 3 см і 1 шматок довжиною 2 см, а отже, загальна кількість шматків буде рівна шести, що означатиме перемогу П’ятачка.
4. Для невід’ємних чисел доведіть нерівність:
.
(Митрофанов Вадим)
Розв’язання. Спочатку доведемо допоміжну нерівність:
.
Дійсно, піднесемо до квадраті та зведемо подібні:
.
Далі використаємо ці нерівності:

.
5. Кола та з центрами в точках та відповідно перетинаються в точках та . Навколо трикутника описали коло з центром у точці , яке перетинає кола та вдруге в точках та відповідно. Пряма перетинає кола та у точках та відповідно. Прямі та перетинаються в точці . Доведіть, що точка лежить на колі та .
(Митрофанов Вадим)
Розв’язання. Спочатку сформулюємо одну з лем Архімеда (Г. Филипповский, «Автоская школьная геометрия», с. 37)
Лема Архімеда. Кола та перетинаються в точках та , при цьому центр кола лежить на колі . Хорда кола перетинає вдруге коло у точці . Тоді .
Позначимо через , що спираються на одну дугу в колі . Аналогічно, , що спираються на одну дугу в колі . Звідси , звідки випливає, що (рис. 8).
За лемою Архімеда, для кіл та можемо записати, що: , але тоді , а звідси вже з кола маємо, що .
Рис. 9
10096569215Рис. 8

4.1. Розв’яжіть систему рівнянь:

(Рубльов Богдан)
Відповідь: , та .
Розв’язання. Додамо ці рівняння і одержимо, що
або .
Тоді або .
Якщо , то з другого рівняння маємо, що
, звідки або .
Звідси маємо, що – розв’язок системи, а от пара розв’язком системи не є.
Якщо , то знову з першого рівняння маємо, що
, звідки .
Знайдемо корені останнього рівняння: та . Одержуємо пари та . перевіркою переконуємось, що вони задовольняють систему рівнянь, а тому є розв’язками.
Рис. 9










5.1. Точки вибрані відповідно на сторонах і опуклого чотирикутника . Знайдіть відношення , якщо відомо, що , , та .
Відповідь: .
Розв’язання. Позначимо шукане відношення через . З теореми Фалеса та з того, що – паралелограм випливає рівність . З аналогічних міркувань:
.
Далі з отриманого рівняння для знаходимо наведену відповідь.
11 клас
1. Чи існують дійсні числа , що задовольняють рівність:
?
Відповідь: не існують.
Розв’язання. Позначимо , , тоді і задана рівність переписується таким чином:
.
З останнього маємо, що ця рівність можлива лише при , що неможливо внаслідок умов задачі. Таким чином задана рівність не можлива.
2. Знайдіть усі такі натуральні числа , які мають більше дільників.
(Рубльов Богдан)
Відповідь: .
Розв’язання. Зрозуміло, що число не може мати дільників, більших від , окрім самого числа . Тому, щоб мати більше дільників, ніж воно повинно ділитись на усі числа від до та на число . Позначимо через те з двох чисел чи , яке є цілим. Тоді при одне з чисел або взаємно просте з . Тому , оскільки воно повинно ділитись на та на одночасно. Але тоді тобто , що суперечить умові . Для випадку числа перевіряються безпосередньо.
3. Відомо, що многочлен

можна також подати у вигляді , де серед чисел принаймні 2015 від’ємних та не обов’язково різних. Знайдіть усі коефіцієнти многочлену .
(Голоднов Кирило)
Відповідь. , .
Розв’язання. Без обмеження загальності будемо вважати, що . Звідси за теоремою Вієта для многочленів (або просто із заданого розкладу многочлену на множники) . Тому значення також дійсне та від’ємне. Далі з теореми Вієта маємо:

З нерівності між середнім арифметичним та геометричним:
.
З рівності між середнім арифметичним та середнім геометричним випливає, що
, тобто ,
тому , звідки маємо, що , .
31438855715
4. В гострокутному трикутнику сторони і мають різну довжину, а продовження медіани перетинає описане коло в точці . На цьому колі відмітимо таку точку , що , де – точка перетину висот трикутника . Точка обрана таким чином, що - паралелограм. Доведіть, що прямі , і перетинаються в одній точці.
(Нагель Ігор)
Рис. 10
Розв’язання. Нехай – точка перетину висот і трикутника . Точки , , , і лежать на одному колі з діаметром , бо (рис. 10).
Далі, так як чотирикутники і – вписані, то і . Звідси випливає, що . Але (як вертикальні) і (як протилежні кути паралелограма. Тому одержуємо, що , тобто чотирикутник – вписаний. Звідси випливає, що . Далі, , бо , а , бо ці кути – вписані в описане коло трикутника . Отже, , а це означає, що точка також належить колу з діаметром .
Позначимо через – описане коло трикутника , через – коло з діаметром , а через – описане коло чотирикутника . Тоді , і – радикальні осі кіл і , і , та і . Як відомо: радикальні осі трьох кіл перетинаються в одній точці – радикальному центрі трьох кіл, або паралельні.
Оскільки , то прямі , і перетинаються в одній точці.
........
........











Рис. 11
5. У країні є 2015 міст, деякі з яких з’єднані двосторонніми авіалініями. Відомо, що для кожного не існує попарно різних міст , для яких існував би замкнений маршрут перельотів (для трьох міст такі маршрути можуть існувати). Яка найбільша кількість пар міст цієї країни можуть бути з’єднані прямим авіасполученням?
(Рубльов Богдан)
Відповідь: .
Розв’язання. Перепишемо умову задачі мовою графів.
Граф складається з вершин та ребер , які з’єднують деякі з вершин. Циклом довжини у цьому графі назвемо таку послідовність ребер , , ..., , де , . Відомо, що у графі немає циклів довжини більше 3-х. Скільки максимум у цього графі може бути ребер?
Спочатку покажемо, що існує граф, що задовольняє умови та має вершин. Він зображений на рис. 11.
Доведемо, що ця величина є максимальною.
Очевидно, що граф зв’язний, якщо ні, то достатньо провести ребро між будь-якими двома компонентами зв’язності і умова про цикли не зміниться, а кількість ребер збільшиться.



........
Рис. 12
Позначимо через – кількість ребер найкоротшого шляху, що з’єднує відповідні вершини, а через – найбільшу можливе значення для усіх .
Розглянемо граф, у якому кількість ребер є максимальною. Серед усіх таких графів виберемо той, у якого мінімальне значення приймає величина .
Припустимо, що . Нехай один з найдовших шляхів складається з послідовних вершин , .



........

Рис. 13
Розглянемо вершину . Якщо вона має степінь (висяча вершина, рис. 12), тобто ребро – єдине, що проходить через вершину . Тоді ми просто замість ребра проведемо ребро . При цьому довжина найдовшого шляху зменшиться. Вчинимо таким чином з усіма висячими вершинами усіх найдовших шляхів. Припустимо знову, що і шлях утворюють вершини , .
Нехай окрім ребра існує ребро . При цьому можливі такі випадки.
Існує також ребро (рис.13). Тоді міняємо граф таким чином – замість ребер та проводимо ребра та . При цьому і тут довжина найдовшого шляху скоротиться.




Рис. 14
Ребра не існує. Найкоротший шлях від до не може проходити через вершини , бо його довжина більша від . Тому існує інший шлях від до . Але тоді зв’язана принаймні з однією з вершин , нехай перша з вершин, яка зустрічається на найкоротшому шляху між та – це , . Тоді маємо цикл , який має більше 3 ланок. Одержана суперечність показує неможливість цього випадку.
Таким чином можемо вважати, що . Припустимо, що немає вершини, що має степінь . Виберемо вершину , що має максимальну степінь , тоді існує вершина , яка не зв’язана з (рис. 14). Тоді найкоротший шлях від до дорівнює , оскільки . Нехай цей шлях буде . Якщо існує вершина , для якої існують ребра та , то утворюється цикл довжини . Тоді виберемо довільну вершину , що з’єднана з та не з’єднана з . Тоді повинне бути ребро , бо інакше найкоротший шлях між та буде більше . Але це означає, що степінь вершини більше ніж у , оскільки вона ще з’єднана з , на відміну від . Або для наступної вершини , для якої існує та маємо цикл – суперечність.
Таким чином існує вершина, позначимо її через . Вона зв’язана з кожною іншою вершиною. Якщо степінь деякої з інших вершин більше , тобто існують ребра та , де . Але тоді маємо заборонений цикл , оскільки з’єднана з усіма іншими вершинами.
Тому окрім усі інші вершини можуть мати степінь не більше . Але це й призводить на до прикладу на рис. 1, де й маємо максимальну кількість ребер.
Альтернативне розв’язання. (Лішунов Віталій)
Відповідь: .
Розв’яжемо задачу для довільної кількості вершин .
Нехай і − кількість вершин і ребер графа відповідно, і позначимо через максимум ребер, які може мати граф , який задовольняє умову задачі і . Доведемо індукцією по , що . Базі індукції безпосередньо перевіряється при . Припустимо, що ми довели твердження для всіх , при , і доведемо його для .
Якщо граф не має циклів, то кількість його ребер дорівнює , де кількість компонент зв’язності графа . В такому випадку, і твердження доведене.
Нехай тепер граф має цикл. За умовою, довжина цього циклу дорівнює і тому можемо вважати, що його утворюють вершини , і . Розглянемо граф , який утворений з графа вилученням ребер, що сполучають ці вершини. Помітимо, що , і належать різним компонентам зв’язності графа . Справді, якщо це не так, то хоча б дві вершини, нехай і , належать одній компоненті зв’язності, а тому існує простий шлях , , …, у якого , .
Якщо , то маємо простий цикл , , …, , , довжина якого не менша за , що суперечить умові.
Якщо , то граф має цикл , , , , довжина якого дорівнює , що також не можливо.
Якщо , то граф має ребро , яке ми вилучили.
Отже, ми довели, що вершини , і належать різним компонентам зв’язності графа . Нехай , де − компонента зв’язності, яка містить вершину , − компонента, що містить , а − решта вершин графа . Оскільки і підграфи , і задовольняють умову задачі, то за припущенням індукції , при , звідки

.
Оскільки нерівність виконується для довільного графа, який задовольняє умову задачі, то , тобто .
Залишається побудувати приклад, для якого .
При можемо розглянути граф
,
а при максимум досягається на графі
.Неважко обчислити, що при маємо .
4.1. На бісектрисі кута трикутника вибрали такі точки , для яких , . Точка – середина відрізку . Доведіть, що .
Розв’язання. Нехай перпендикуляр з точки на перетинається з ним у точці , аналогічно . Нехай – проекції точки на прямі та відповідно. Не обмежуючи загальності розгляду вважаємо, що розташування точок має вигляд як на рис. 14. Тоді:
та .
Рис. 14
A
A
A
A
A
A
A
A
A
A
Тоді з властивостей середньої лінії маємо, що , . Тому та . Оскільки та , то це означає, що , звідки , тому .
5.1. Задача № 5.1 за 9 клас.

Приложенные файлы

  • docx 17458806
    Размер файла: 1 MB Загрузок: 0

Добавить комментарий