[ Нестандартні завдання з математики ]! | |
' | відповідають усім 7 склянках, тому що при зміні знаку у 4 співмножників добуток не змінюється. Але в початковому положенні це добуток дорівнює -1, а значить, стати +1 воно ніколи не зможе. 2.5. На столі коштують 7 перевернутих склянок. Дозволяється одночасно перевертати будь-які дві склянки. Чи можна домогтися того, щоб всі склянки стояли правильно? 2.6. На столі стоять вверх дном 9 склянок. Дозволяється за один раз перевернути будь-які 4 склянки. Чи можна за кілька таких ходів поставити всі склянки в нормальне положення? 2.7. Три коника грають в чехарду: якщо коник з точки А стрибає через коника, що знаходиться в точці В, то він опиниться в точці С, симетричної точці А відносно точки В. У вихідному положенні коники займають три вершини квадрата. Чи можуть вони, граючи в чехарду, потрапити в четверту його вершину? Рішення. Введемо на площині систему координат так, щоб три вершини квадрата, в яких знаходяться коники, мали координати (0; 0), (0; 1) і (1; 0). При зазначених стрибках кожна з координат коників або залишається незмінною, або змінюється в ту чи іншу сторону на парне число (рис 12) х Так як у початковому положенніщонайменше одна з координат кожної з трьох точокпарна, то вона при стрибках залишиться парному: парність хо тя б однієї з двох кожній з точок є інваріант. Тому потрапити в М один з коників не може Відповідь: не може. 2.8. Є 30 карток, кожна з яких пофарбована з одного боку в червоний, а з іншого - в синій колір. Картки розклали поспіль у вигляді смуги так, що у 8 карток зверху виявився синій колір. За один дозволяється перевернути будь-які 17 карток. Чи можна за кілька ходів домогтися того, щоб смуга стала повністю: а) червоною; б) синій? Завдання 1: На дошці написано десять плюсів і п'ятнадцять мінусів. Дозволяється стерти будь-які два знаки і написати замість них плюс, якщо вони однакові, і мінус у противному випадку. Який знак залишиться, на дошці після виконання двадцяти чотирьох таких операцій. Рішення. Замінимо кожний плюс числом 1, а кожен мінус числом -1. Дозволена операція описується тоді так: стираються будь-які два числа і записується їх твір. Тому твір всіх написаних на дошці чисел залишається незмінним. Так як спочатку це твір дорівнювало -1, то і в кінці залишиться число -1, то є знак мінус. Це міркування можна було провести інакше. Замінимо всі плюси нулями, а мінуси-одиницями, і зауважимо, що сума двох стираних чисел має ту ж парність, що і число, що записується замість них. Так як спочатку сума всіх чисел була непарної (вона дорівнювала 15), то й останнє, на дошці число буде непарних, тобто одиницею, і, значить, на дошці залишиться мінус. Нарешті, третє рішення задачі можна отримати, зауваживши, що в результаті кожної операції число мінусів або не змінюється, або зменшується на два. Оскільки спочатку число мінусів було непарним, то і в кінці залишиться один мінус. Проаналізуємо всі три рішення. Перше рішення грунтувалося на незмінності твори написаних чисел, друге-на незмінності парності їх суми та третє - на незмінності парності числа мінусів. У кожному рішенні нам вдалося знайти інваріант: твір написаних чисел, парність суми, парність числа мінусів. Рішення наступних завдань також грунтується на вдалому підборі інваріанту. 2.9. На дошці написано кілька плюсів і мінусів. Дозволяється стерти будь-які два знаки і написати замість них плюс, якщо вони різні, і мінус у противному випадку. Доведіть, що останній залишився на дошці знак не залежить від порядку, в якому проводилися стирання. 2.10. У таблиці 4х4 знаки «+» і «-» розставлені так, як показано на малюнку 13. Дозволяється змінити знак на протилежний одночасно у всіх клітинах, розташованих в одному рядку, в одному стовпці або вздовж прямої, паралельної який-небудь з діагоналей (зокрема, в будь-якій кутовий клітці). Чи можна за допомогою цих операцій отримати таблицю, що не містить жодного мінуса? Рішення. Замінимо плюси і мінуси числами 1 і -1. В якості інваріанта можна взяти твір чисел, що перебувають у клітках, які заштриховані на малюнку 14, оскільки воно внаслідок дозволеної операції весь час зберігає первинне значення, рівне -1. Але, значить, серед заштрихованих чисел завжди буде залишатися -1, отже, отримати таблицю, що не містить жодного мінуса, не можна. 2.11. Вирішіть задачу 2 для таблиць, зображених на малюнках 15 - 17. 2.12. На дошці написано кілька нулів, одиниць і двійок. Дозволяється стерти дві нерівні цифри і замість них написати одну цифру, відмінну від стертих (2 замість 0 і 1, 1 замість 0 і 2, 0 замість -1 і 2). Доведіть, що якщо в результаті декількох таких операцій на дошці залишиться одна-єдина цифра, то вона не залежить від порядку, в якому проводилися стирання. Рішення. Позначимо через х0, х1, х2 число нулів, одиниць і двійок відповідно. Виконавши один раз дозволену операцію, ми змінимо кожне з цих чисел на 1 і, отже, змінимо парність всіх трьох чисел. Коли на дошці залишається одна цифра, два з чисел х0, x1, х2 стають рівними нулю, а. Третє - одиниці. Значить, з самого початку два з цих чисел мають одну парність, а третє-другу. Тому незалежно від того, в якому порядку проводяться стирання, в кінці одиниці може дорівнювати лише одне з чисел х0, х1, x .2, яке з самого початку мало не ту парність, що два інших. З наведеного рішення видно, що якщо числа х0, х1, х2 мають одну і ту ж парність, то ми не зможемо добитися, щоб на дошці залишилася одна-єдина цифра. Доведіть, що якщо серед чисел х0, х1 х2 є як парні, так і непарні, і, крім того, хоча б два з них відмінні від нуля, то існує такий порядок стирок, що в результаті на дошці залишиться "одна цифра. Змінимо умову задачі 3: зажадаємо,. Щоб одні і ті ж дві нерівні цифри стиралися два рази, а замість них записувалася одна цифра, відмінна від стертих. Припустимо, що знову після деякого числа операції на дошці залишилася одна-єдина цифра. Чи можна заздалегідь, за кількістю нулів, одиниць і двійок, передбачити, яка це цифра? Міркування з парністю тут не допомагає, бо в результаті виконання кожної операції одне з чисел х0, х1, x 2 змінює свою парність, а два інших зберігають парність, так що числа, які мали різну парність, можуть тепер отримати одну і ту ж парність. Однак можна помітити, що залишки від ділення чисел х0, х1, х2 на 3 змінюються щоразу таким чином, що рівні рештки залишаються рівними, а нерівні залишаються нерівними. Подальші міркування повторюють рішення задачі 3. 2.13. У кожній клітці таблиці 8х8 написано деяке ціле число. Дозволяється вибирати в таблиці будь-який квадрат розмірами 3х3 або 4х4 і збільшувати на одиницю всі, хто стоїть в клітинах обраного квадрата числа. Чи завжди можна за допомогою таких операцій перетворити вихідну таблицю в таблицю, у якій вага числа діляться на З? Рішення. Ні, не завжди. Знайдемо суму чисел, написаних у заштрихованих на малюнку 6 клітинах. Оскільки будь-який квадрат розмірами 4х4 містить 12 заштрихованих клітин, а квадрат розмірами 3х3-6 або 9 таких клітин, то в результаті описаної операції залишок від ділення на 3 цієї суми (чисел, що стоять в заштрихованих клітинах) не буде змінюватися. Тому, якщо з самого початку знайдена сума не ділиться на 3, то серед заштрихованих клітин весь час будуть зберігатися клітини, в яких написані числа не кратні трьом. 2.14. З будь-якої чи таблиці можна в умовах задачі 4 отримати таблицю, що не містить парних чисел? 2.15. Числа I, 2, 3, ...., n розташовані в певному порядку. Дозволяється міняти місцями будь-які два поруч стоять числа. Доведіть, що якщо виконати непарне число таких операцій, то напевно вийде відмінний від початкового розташування чисел 1, 2, 3, ..., n. Рішення. Нехай a 1, a 2, ..., an - довільна перестановка з чисел 1, 2, 3, ..., п. Будемо говорити, що числа а i, і а j, утворюють в цій перестановці інверсію, якщо i 2.16. Доведіть, що затвердження завдання 2.15 залишиться справедливим, якщо дозволити міняти місцями будь-які два числа в перестановці. Зазначення. Доведіть, що будь-які два числа можна поміняти місцями, виконавши непарне число раз операцію, описану в задачі 2.12. Перехід від однієї перестановки чисел 1, 2, 3, .... п до іншої перестановці цих чисел, при якому будь-які два числа міняються місцями, а решта залишається на місці, називається транспозицією. Результат завдання 2.16 можна сформулювати так: виконавши непарне число транспозицій, ми змінимо перестановку 2.17. У різних пунктах кільцевого автодрому в один і той же час в одному напрямку стартували 25 автомобілів. За правилами гонки автомобілі можуть обганяти один одного, але при цьому заборонено подвійний обгін. Автомобілі фінішували одночасно в тих же пунктах, що і стартували. Доведіть, що під час гонки було парне число обгонів. Рішення. Забарвимо один з автомобілів у жовтий колір, а іншим автомобілям привласнимо номери 1, 2, 3, ..., 24 в тому порядку, в якому вони розташовуються на старті за жовтим автомобілем. У центрі автодрому встановимо світлове табло, на якому після кожного обгону будемо вказувати номери автомобілів в тому порядку, в якому вони слідують за жовтим автомобілем. Тоді обгін, в якому не бере участь жовтий автомобіль, призводить до того, що на світловому табло міняються місцями два сусідніх числа. Подивимося, що станеться, якщо який-небудь автомобіль обжене жовтий. Якщо перед цим обгоном числа на табло утворювали перестановку а1, а2, ..., А24, то після обгону вони утворюють перестановку а2, а3, ..., А24, а1. Зауважимо, що до такої ж перестановці можна прийти, виконавши послідовно 23 транспозиції: а1, а2, а3, ..., А24 à а2, а1, а3, ..., А24 à а2, а3, а1, ..., А24 à а2, а3, а1, ..., А24 à ... à а2, а3, ..., а1, А24 à а2, а3, ..., А24, а1 Якщо ж жовтий автомобіль зробив обгін, то з перестановки а1, а2, ..., А24 отримаємо перестановку А24, а1, а2, а3, ..., А23. Цей перехід також можна замінити двадцятьма трьома транспозиція. Таким чином, будь-який обгін зводиться до непарному числу транспозицій. Якщо б загальне число обгонів було непарним, то непарних виявилося б і загальне число транспозицій. Залишається скористатися результатом завдання 2.16. 3. Графи Графом на площині називається скінченна множина точок площини, деякі з яких з'єднані лініями. Ці точки називаються вершинами графа, а що з'єднують їх лінії - ребрами. Число ребер, що виходять з вершини графа, називається ступенем цієї вершини. З графами ми зустрічаємося частіше, ніж це, можливо, здається на перший погляд. Прикладами графа може служити будь-яка карта доріг, електросхема, креслення багатокутника і т. д. Теорія графів виникла в 1736 р., коли Леонард Ейлер опублікував першу статтю про графах. Починалася вона з розбору широко відомої тепер задачі про кенігсберзькими мостах. Довгий час вважалося, що теорія графів застосовується головним чином для вирішення логічних завдань, а сама теорія розглядалася як частина геометрії. Однак у ХХ столітті були знайдені широкі застосування теорії графів в економіці, біології, хімії, електроніці, мережевому плануванні, комбінаториці і інших областях науки і техніки. У результаті вона стала бурхливо розвиватися і перетворилася на самостійну розгалужену теорію. Завдання на відповідність між множинами. 3.1. У п'яти корзинах А, Б, В, Г і Д лежать яблука п'яти різних сортів. У кожній з кошиків А і Б знаходяться яблука 3-го і 4-го сорту, у кошику В - 2-го і 3-го, у кошику Г - 4-го і 5-го, у кошику Д - 1-го і 5-го. Занумеруйте кошика так, щоб у кошику № 1 були яблука 1-го сорту (принаймні одна), в кошику № 2 - яблука 2-го сорту і т. Д Рішення. Зобразимо дві множини безліч кошиків і безліч їх номерів. У кожному з цих множин по п'ять елементів позначимо їх точками Встановимо відповідність між цими двома множинами так, щоб умови завдання виконувалися. Будемо відповідні елементи двох множин з'єднувати суцільними лініями, а не відповідні - пунктирними або зовсім не з'єднувати. Так як яблука першого сорту лежать тільки в кошику Д, то саме цьому кошику і потрібно дати номер 1; проведемо суцільну лінію між точками Д і 1. Далі номер 2 можна привласнити тільки кошику В, а після цього номер 5 - лише кошику Г. Нарешті, номери 3 і 4 дамо кошиках А і Б (у будь-якому порядку). Відповідь: кошики розташувалися, починаючи з № 1, у послідовному порядку Д, В, А, Б, Г або в порядку Д, В, Б, А, Г. 3.2. Петро, Геннадій, Олексій і Володимир займаються в одній дитячій спортивній школі в різних секціях: гімнастики, легкої атлетики, волейболу та баскетболу. Петро, Олексій і волейболіст навчаються в одному класі. Петро і Геннадій на тренування ходять пішки разом, а гімнаст їздить на автобусі. Легкоатлет не знайомий ні з волейболістів, ні з баскетболістом. Хто в якій секції займається? 3.3. Футбольні команди п'яти шкіл міста беруть участь у розіграші кубка. У фінал кубка виходять дві команди. До змагань п'ять уболівальників висловили прогнози, що у фінал вийдуть команди: 1) Б і Г, 2) У і Д, 3) Б і В, 4) А і Г, 5) Г і Д. Один прогноз виявився повністю невірним, в решті була правильно названа тільки одна з команд-фіналісток. Які команди вийшли у фінал? 3.4. Три товариші - Володимир, Ігор і Сергій - закінчили один і той же педагогічний інститут і викладають математику, фізику і літературу в школах Тули, Рязані і Ярославля. Володимир працює не в Рязані, Ігор - не в Тулі. Рязанець викладає не фізик, Ігор - не математику, туляк викладає літературу. Який предмет і в якому місті викладає кожен з них? 3.5. Серед офіцерів А, Б, В і Г - майор, капітан і два лейтенанти. А і один з лейтенантів - танкісти, Б і капітан - артилеристи, А молодші за званням, ніж В. Визначте рід військ і військове звання кожного з них. 3.6. У країні Радонеж деякі міста пов'язані між собою авіалініями. Зі столиці виходить 1985 авіаліній, з міста Далекого одна, а з решти міст - по 20 ліній. Доведіть, що зі столиці можна дістатися до Далекого. Рішення. Розглянемо безліч міст, до яких можна дістатися зі столиці. Це граф: його вершини - міста, ребра - авіалінії, їх з'єднують. З кожної вершини графа виходить стільки ребер, скільки всього авіаліній виходить з відповідного міста. Граф містить непарну вершину - столицю. Оскільки число непарних вершин у графі парне, в ньому є ще одна непарна вершина. Цією вершиною може бути тільки місто Далекий. Завдання, при вирішенні яких використовуються вершини, сторони і діагоналі багатокутника 3.7. Чи можна організувати футбольний турнір дев'яти команд так, щоб кожна команда провела по чотири зустрічі? Рішення Зобразимо кожну команду точкою, а проведену нею зустріч - відрізком, що походить з цієї точки. Дев'ять точок краще розташувати так, щоб при послідовному з'єднанні їх відрізками утворився опуклий девятіугольнік. Завдання зводитися до наступного: чи можна дев'ять точок з'єднати відрізками так, щоб з кожної точки виходили чотири відрізка? Іншими словами, чи існує граф з деят вершинами, у якого ступінь кожної вершини дорівнює 4? Перш за все проведемо всі сторони девятіугольніка; вони будуть означати, що кожна команда провела дві зустрічі. Для того щоб отримати ще дві зустрічі будемо, наприклад, з'єднувати всі вершини діагоналями через одну (рис. 19). (Доцільно для всіх триматися однієї і тієї ж системи проведення з них відрізків, інакше рішення ускладниться.) Після цього все виходить. Відповідь: можна. 3.8. Чи можна провести футбольний турнір восьми команд так, щоб кожна команда провела: а) по чотири зустрічі, б) по п'ять зустрічей 3.9. Чи можна провести футбольний турнір семи команд так, щоб кожна команда провела по три зустрічі? Рішення. Спроби вирішити цю задачу тим же методом, що й попередні завдання, призводять до невдачі. Виникає підозра, що провести турнір таким чином не можна. Для того щоб довести нашу гіпотезу, спробуємо замість малюнка підрахувати загальне число зустрічей, які треба провести командам. Воно дорівнює 7 (3 / 2). Але це число не є цілим. Відповідь: не можна. 3.10. Доведіть що загальне число вершин графа, які мають непарну ступінь парне. 3.11. У трьох вершинах правильного п'ятикутника розташували по фішці. Дозволяється пересувати їх по діагоналі в будь-яку вільну вершину. Чи можна таким чином домогтися того, щоб одна з фішок повернулася на своє місце, а дві інші помінялися місцями? 3.12. Дан правильний 45-і кутник. Чи можна так розставити в його вершинах цифри від 0 до 9 так, щоб для будь-якої пари різних цифр знайшлася сторона, кінці якої занумеровані цими цифрами. Зазначення. Розглянути повний граф, вершини якого суть цифри від 0 до 9. Завдання зводиться до його обходу. 3.13. Доведіть що загальне число вершин графа, які мають непарну ступінь парне. Рішення. Позначимо число вершин графа, що мають непарну ступінь, через k, а ступені таких вершин - відповідно через а1, а2, ..., а k. Крім того, у графа можуть бути вершини з парної ступенем; позначимо ступеня цих вершин відповідно через b 1, b 2, ..., bn. Припустимо, що число k непарній. Підрахуємо загальне число ребер графа. Воно дорівнює [(а1 + а2 + ... + а k) + (b 1 + b 2 + ... + bn)] / 2. Сума в перших дужках чисельника отриманої дробу є число непарне, як сума непарного числа непарних доданків, а сума в других дужках число парне. Але тоді весь чисельник - число непарне, а значить дріб не є натуральним числом. Ми прийшли до протиріччя. 3.14. Чи можна 15 телефонів з'єднати між собою так, щоб кожен з них був пов'язаний рівно з 11 іншими? 3.15. Дев'ять школярів, роз'їжджаючись на канікули, домовилися, що кожен з них пошле листівки п'ятьом з інших. Чи може виявитися, що кожен з них отримає листівки саме від тих друзів, яким напише сам? 3.16. У шаховому турнірі в одне коло беруть участь 17 шахістів. Чи вірно, що в будь-який момент турніру знайдеться шахіст, який зіграв до цього моменту парне число партій (може бути жодної)? Завдання на обведення контуру фігури безперервної лінією 3.17. У 18 столітті місто Кенігсберг (нині Калінінград у складі нашої країни) був розташований на берегах річки і двох островах. Різні частини міста було сполучено сімома мостами (рис. 20). Чи можна обійти всі ці мости так, щоб побувати на кожному з них рівно один раз? Це і є завдання Ейлера про кенігсберзькими мостах, про яку згадувалося на початку параграфа. Рішення. Позначимо різні частини міста літерами А, В, С і К і зобразимо їх точками. Мости зобразимо лініями, що з'єднують ці точки. Отримаємо граф (рис. 21). Завдання зводиться до наступної: чи існує шлях, що проходить по всіх ребрах графа, причому по кожному ребру тільки один раз? Розглянемо два випадки. 1) Припустимо, що існує такий замкнутий шлях. Тоді ступінь кожної вершини графа повинна бути парному, так як, входячи в будь-яких вершину, ми потім повинні з неї вийти, причому по іншому ребру. Що стосується початку шляху, то після виходу з нього ми повинні врешті-решт у нього і повернутися, оскільки шлях замкнутий. Однак на малюнку 20 немає жодної вершини, ступінь якої була б парному. Значить цей випадок неможливий. 2) Нехай існує такий незамкнений шлях; наприклад, нехай він починається у вершині А, а закінчується в С. Тоді з вершин А і С повинно виходити вже непарне число ребер, а з проміжних вершин В і К - як і раніше парне число. Але на малюнку ступеня вершин В і К непарних. Отже, і цей випадок відпадає. Відповідь: не можна. Хоча міркування проведене під час вирішення завдання 3.13, виконано для окремого випадку, воно носить загальний характер: 1) якщо існує замкнутий шлях, що проходить по всіх ребрах графа, причому по кожному ребру тільки один раз, то ступеня усіх вершин графа парні, 2) якщо існує аналогічний незамкнений шлях, то ступеня початку і кінця шляху непарні, а інших вершин - парні. Ейлер у своїй статті довів і зворотні твердження. Нехай граф зв'язний, тобто будь-які дві його вершини можна зв'язати шляхом, які пройшли за його ребрах. Тоді шлях, що проходить по всіх ребрах графа, причому по кожному ребру тільки один раз, існує лише в наступних двох випадках: 1) коли ступінь кожної вершини парна (у цьому випадку шлях замкнутий), 2) коли граф має тільки дві вершини А і В з непарної ступенем (тоді шлях не замкнутий і має своїми кінцями вершини А і В). 3.18. Чи можна обвести олівцем, не відриваючи його від паперу і не проводячи по одній лінії двічі: а) квадрат з діагоналями, б) правильний п'ятикутник з діагоналями? 3.19. Чи можна з дроту довжиною 12 дм виготовити каркас куба з ребром довжини 1 дм, не ламаючи дріт на частини? 3.20. Чи можна граф, зображений на малюнку 22, обвести олівцем, не відриваючи його від паперу і не проходячи жодної лінії двічі? Якщо можна, то як? 3.21. У точці А розташований гараж для снігоочисної машини (рис. 23). Водієві машини було доручено прибрати сніг з вулиць частини міста зображеної на малюнку. Чи може він закінчити свою роботу на тому перехресті, де знаходиться гараж, якщо по кожній вулиці своєї ділянки міста водій буде проїжджати тільки один раз? 3.22. У марсіанському метро 100 станцій. Від будь-якої станції до будь Інший можна проїхати. Страйковий комітет хоче закрити проїзд через одну із станцій так, щоб між усіма іншими станціями був можливий проїзд. Доведіть, що така станція знайдеться. 3.23. У тридев'ятому царстві кожні два міста з'єднані дорогою з одностороннім рухом. Доведіть, що існує місто, з якого в будь-який інший можна проїхати не більше ніж за двома дорогами. 3.24. У місті на кожному перехресті сходиться парне число вулиць. Відомо, що з будь-вулиці міста можна проїхати на будь-яку іншу. Доведіть, що всі вулиці міста можна об'їхати, побувавши на кожній по одному разу. Різні завдання на графи. 3.25. У кутах шахівниці 3х3 коштують 4 коня: 2 білих (у сусідніх кутах) і два чорних. Чи можна за кілька ходів (з шахових правилами) поставити коней так, щоб у всіх сусідніх кутах стояли коні різного кольору? Рішення. Відзначимо центри клітин дошки і з'єднаємо відрізками пари зазначених точок, якщо з однієї в іншу можна пройти ходом коня. Ми отримаємо граф, що містить «цикл» з восьми точок і одну ізольовану точку (рис. 24). Переміщення коней по дошці відповідає руху по ребрах цього циклу. Ясно, що при русі по циклу не можна змінити порядок проходження коней. 3.26. Випишіть в ряд цифри від 1 до 9 так, щоб число, складене з двох сусідніх цифр, поділялося або на 7, або на 13. Рішення. Напишемо цифри на аркуші. З'єднаємо стрілками ті цифри, які можуть слідувати один за одним (рис. 25). Тепер ясно, що першою йде 7, потім 8 і 4. Оскільки 8 вже використана, то стрілки, що йдуть до неї, треба прибрати. Після 4 йде 9, оскільки до дев'ятці іншого шляху немає. Далі йде 1 і так далі. Відповідь: 784913526. 3.27. У шкільному турнірі в одне коло грають шість шахістів: Олександр, Борис, Віктор, Григорій, Дмитро і Костя. Щодня гралися три партії, і весь турнір закінчився у п'ять днів. У перший день Боря грав з Олексою, а в другій - з Костею. Вітя в четвертий день грав з Костею, а в п'ятий з Дімою. Хто з ким грав у кожен день турніру? Рішення. Позначимо шахістів відповідно точками А, Б, В, Г, Д і К, а зіграні ними партії - відрізками, що з'єднують ці точки. Точки краще розташовувати так, щоб при послідовному їх поєднанні вони стали вершинами правильного шестикутника. 1) Перший день турніру. За умовою в цей день Боря грав з Олексієм. З ким грав Вітя? Тільки з Грицем, так як з Дімою і Костею він грав у інші дні. Отже, третю партію в перший день грали Діма з Костею. Побудуємо відповідний граф (рис. 26). 2) Другий день турніру. У цей день Боря грав з Костею, тому Вітя, з огляду на перший і п'ятий дні, міг грати лише з Олексою (рис. 27). 3) Третій день турніру. Вітя, з урахуванням всіх попередніх і наступних турніру, міг грати тільки з Борею. Так як Діма вже грав з Костею і Грицем, то в цей день він грав з Олексою (рис. 28). Значить Гриша грав з Костею. 4) Четвертий день турніру. Тут неважко визначити, хто з ким грав: Вітя - з Костею, Альоша - з Грицем, Боря з Дімою (рис.29). 5) П'ятий день турніру (рис. 30). 3.28. В одному купе поїзда їхали чотири пасажири. Серед них не було трьох осіб, які раніше були знайомі один з одним, але один був знайомий з трьома іншими. Доведіть, що ці три останніх пасажира раніше не були знайомі один з одним. 3.29. Кожні дві з шести ЕОМ з'єднані проводом. Чи можна всі ці дроти розфарбувати в один з п'яти кольорів так, щоб з кожної ЕОМ виходили п'ять проводів різного кольору? Рішення. Для вирішення накреслимо опуклий шестикутник і проведемо в ньому все діагоналі (рис. 31). Нехай кожна вершина шестикутника означає однуB з ЕОМ, а кожен відрізок провід, що з'єднує дві ЕОМ. Занумеруем різні кольори натуральними числами від 1 до 5 для того, щоб відрізняти їх один від одного. Почнемо наприклад з вершини Апроведем з неї відрізки всіх п'яти кольорів. Перейдемо до вершини В і з неї проведемо чотири відрізка всіх квітів з № 2 по № 5, враховуючи, що відрізок ВА, що виходить з цієї вершини, вже забарвлений в колір № 1. Потім займемося вершиною С. І т. д. У результаті отримуємо позитивну відповідь на питання завдання. Відповідь: можна. На малюнку 31 кожні дві вершини графа з'єднані своїм ребром. Такий граф називається повним. 3.30. На туристському зльоті з'ясувалося, що кожен юнак знаком з 8 дівчатами, кожна дівчина знайома з 6 юнаками. Кого на зльоті більше: юнаків або дівчат? 3.30. На гуртку, в якому беруть участь шість школярів, було дано шість завдань. Кожен школяр вирішив два завдання, і кожне завдання вирішили два школярі. Доведіть, що розбір завдань можна організувати так, щоб кожен школяр виклав вирішення однієї з вирішених ним завдань і всі завдання були розібрані. Рішення. Зобразимо школяра точкою, а вирішену їм завдання - лінією виходить із цієї точки. Нехай один із школярів позначений крапкою А.. Проведемо з неї лінію. Так як кожне завдання вирішили два школяра, то проведена лінія з'єднує точку А з іншою точкою В, яка позначає другу школяра, який вирішив ту ж задачу. Оскільки кожен школяр вирішив два завдання, то з точки В повинна виходити ще одна лінія, яка з'єднує точку В з ще однією точкою С і т. д. Можливі наступні випадки. 1) Може вийти шестикутник. Тоді твердження завдання виконується. 2) Може вийти чотирикутник і «двуугольнік»; останнє можливо тоді, коли двоє школярів вирішили одні й ті ж завдання. 3) Можуть вийти два трикутника. 4) Можуть вийти три «двуугольніка». Цим вичерпуються всі можливості. У кожному з розглянутих випадків твердження завдання виконується. 3.31. На столі в приймальні перукарні лежать журнали. Кожен клієнт перукарні переглянув два журнали; кожен журнал переглянули три людини; для кожної пари журналів є тільки один клієнт, який їх переглянув. Скільки журналів і скільки клієнтів у приймальні перукарні? Рішення. Позначимо журнал точкою, а клієнта, переглянув цей журнал - відрізком, що виходять з цієї точки. Візьмемо одну таку точку А. Так як кожен журнал переглянули три людини, то з точки А повинні виходити три відрізки. Оскільки кожен клієнт переглянув два журнали, то кожен Відрізок з'єднають дві точки. (Рис. 32). Оскільки кожну пару журналів переглянув одна людина, то треба кожну пару точок з'єднати відрізком. Отримуємо чотирикутник з діагоналями (рис. 33). Перевірте ще самі, що тут всі три умови задачі виконуються. Може виникнути питання: а чи не існує ще хоча одна, п'ята точка Е, така, що всі умови задачі виконуються? Тоді з кожної з п'яти точок буде виходити не по три, а по чотири відрізка, а це суперечить умовам завдання. Відповідь: 4 журналу, 6 клієнтів. 3.32. У одній установі кожен співробітник виписує дві газети, кожну газету виписує п'ять людей і кожну пару газет виписує тільки одна людина. Скільки людей в установі і скільки вони виписують газет. 3.33. Шість точок, з яких ніякі три не лежать на одній прямій з'єднані всілякими відрізками і кожен відрізок забарвлений в чорний або червоний колір. Доведіть, що знайдеться трикутник з вершинами в даних точках, у якого всі сторони чорні, або трикутник, у якого всі сторони червоні. Рішення. Візьмемо одну з шести точок А1более чотирьох відрізків (по узагальненому принципу Діріхле). Нехай відрізки А1А2, А1А3 і А1А4 - червоні. Розглянемо два випадки. 1) Припустимо, що серед відрізків А2А3, А2А4 і А3А4 є червоний, наприклад відрізок А2А3. Тоді у трикутника А1А2А3 всі сторони червоні. Саме цей варіант зображений на малюнку 34. 2) Якщо припустимо, що серед відрізків А2А3, А2А4 і А3А4 немає червоного, тоді всі ці відрізки - чорні, а отже у трикутника А2А3А4 всі сторони чорні. 3.34. Доведіть, що якщо в задачі 3.33 замість шести точок взяти п'ять, трикутник з одноколірними сторонами може і не знайтися. 3.35. У міжнародному туристичному таборі шість туристів познайомилися між собою. З'ясувалося, що серед будь-яких трьох з них є двоє, які можуть розмовляти один з одним на якому-небудь мовою. Чи вірно, що серед них знайдуться троє, кожен з яких може розмовляти з кожним із двох інших на якому-небудь мовою? 3.36. 17 учених із різних країн переписуються між собою на одному з трьох мов: англійською, французькою або російською. Доведіть, що серед них знайдуться троє, які переписуються між собою на одному і тому ж мовою. Рішення. Позначимо кожного з учених точкою і з'єднаємо ці точки всілякими відрізками. Точки розташуємо так, щоб ніякі три з них не лежали на одній прямій. Так як кожен учений листується з 16 іншими, то з кожної точки виходить 16 відрізків. Кожен з відрізків, що означає листування вчених на англійській мові, забарвимо в чорний колір, французькою - в червоний, російською - у білий. Розглянемо два випадки. 1) Нехай серед відрізків, що з'єднують точки А2, А3, А4, А5, А6 і А7 попарно між собою, є чорний, скажімо А2А3. Тоді у трикутника А1А2А3 всі сторони чорні, тобто відповідна трійка вчених переписуються між собою англійською мовою. 2) Нехай серед цих відрізків немає чорного. У цьому випадку відрізки між шістьма точками А2, А3, А4, А5, А6 і А7 пофарбовані не більше, ніж у два кольори - червоний і білий. Тоді на підставі затвердження завдання 3.33 серед відрізків, що з'єднують ці точки, є три, складові трикутник зі сторонами одного кольору. 3.37. На площині дано п точок, з яких ніякі три не лежать на одній прямій. Вони з'єднані всілякими відрізками, і кожен відрізок забарвлений в один з чотирьох різних кольорів. При якому найменшому п обов'язково знайдеться трикутник з одноколірними сторонами з вершинами у трьох з даних точок? 3.38. Послідовність з 36 нулів та одиниць починається з п'яти нулів. Серед п'ятірок поспіль стоять цифр зустрічаються всі 32 можливі комбінації. Знайдіть п'ять останніх цифр послідовності. 3.39. Доведіть, що можна розташувати по колу символи 0 і 1 так, щоб будь-який можливий набір з n символів, що йдуть поспіль, зустрівся. Зазначення. Розглянути граф, вершини якого суть слова довжини n -1. Дві вершини u і v з'єднуються стрілкою, якщо існує слово довжини n, у якого u є початком, а v - кінцем. 4. Розмальовки Кажуть, що фігура пофарбована в кілька кольорів, якщо кожній точці фігури приписаний певний колір. Бувають завдання, де розфарбування вже дана, наприклад для шахової дошки, бувають завдання, де розфарбування з даними властивостями потрібно придумати, і бувають завдання, де розфарбування використовується як ідея рішення. Завдання 4.1. З шахової дошки вирізали дві протилежні кутові клітини. Доведіть, що залишилася постать не можна розрізати на «доміно» з двох клітин Рішення. Кожна фігура «доміно» містить 1 білу і 1 чорну клітину. Але в нашій фігурі 32 чорних і 30 білих клітин (або навпаки). 4.2. Чи можна все клітини дошки 9х9 обійти конем по одному разу і повернутися у вихідну клітку? Рішення. Кожним ходом кінь змінює колір клітини, тому, якщо існує обхід, то число чорних клітин дорівнює числу білих, що невірно. 4.3. Дан куб 6х6х6. Знайти максимально можливе число паралелепіпедів 4х1х1 (зі сторонами паралельними сторонам куба), які можна помістити в цей куб без перетинів. Ідея рішення. Легко розмістити 52 паралелепіпеда всередину куба. Доведемо, що не можна більше. Розіб'ємо куб на 27 кубиків 2х2х2. Розфарбуємо їх у шаховому порядку. При цьому утворюється 104 клітини одного кольору (білого) і 112 - іншого (чорного). Залишилось зауважити, що кожен паралелепіпед містить дві чорних і два білих клітини. Відповідь: 52. 4.4. Пряма розфарбована в 2 кольори. Доведіть, що знайдуться 3 точки А, В, С одного кольору такі, що AB = НД 4.5. Розфарбуйте пряму в 3 кольори так, щоб не можна було знайти трьох точок А, В, С різного кольору таких, що AB = НД 5. Площина розфарбована а) в 2 кольори, б) в 3 кольори. Доведіть, що знайдуться 2 точки одного кольору, відстань між якими дорівнює 1 Ідею, винесену в заголовок, добре ілюструє наступне завдання. 4.6. Є квадрат 8Х8, з якого видалено дві кутові клітини, розташовані на одній діагоналі. Чи можна цей квадрат замостити кісточками доміно розмірами 1х2? Рішення дає нам правильна «шахова» розфарбування цієї дошки. Кожна кісточка доміно закриває дві клітини різного кольору, у той час як клітин чорного і білого кольорів різна кількість. А ось ще два завдання на цю ідею.
Будь ласка, не зберігайте тестовий текст.4.7. Ділянка прямокутної форми розбитий на квадрати, що утворюють n рядів по m квадратів в кожному ряду. Кожен квадрат є окремою ділянкою, сполученим хвіртками з усіма сусідніми ділянками. За яких m і n можна обійти всі квадратні ділянки, побувавши у кожному по одному разу, і повернутися в початковий? Рішення. Розфарбуємо квадрати в шаховому порядку. При кожному переході міняється колір квадрата. Тому, якщо такий маршрут можливий, то число кроків має бути парним, тобто m або n парне. Залишилося перевірити, що в цьому випадку шуканий маршрут можливий. 4.8. Всі ми в дитинстві грали в «морський бій». Нагадаємо, що грається він на квадраті 10Х10, на картатої папері. «Лінкором» у цій грі називається «корабель» 1х4. У зв'язку з цим виникає питання: чи можна весь квадрат для морського бою розрізати на 25 лінкорів? А до речі, дайте відповідь ще на одне питання: яку найменшу число «пострілів» треба зробити, щоб напевно хоча б один раз потрапити у лінкор, самотньо плаваючий по морю? Рішення. Розфарбуємо клітини в 4 кольори, як на рис. 36. Кожен «лінкор» закриває чотири клітини різного кольору. Але клітин кольору 2 всього 26, а «лінкорів» має бути 25. Ця ж розфарбування допомагає відповісти і на друге питання. Найменше число пострілів дорівнює числу клітин кольори 4, тобто 24. 5. Завдання з цілими числами. Парні і непарні числа Зазвичай парні і непарні числа пов'язують лише з натуральними числами. Тут ми розповсюдимо їх на будь-які цілі числа. Ціле число називається парним, якщо воно ділиться на 2, і непарних, якщо воно на 2 не ділиться. Будь-яке парне число можна представити у вигляді 2 а, а будь-яке непарне - у вигляді 2 а + 1, де а - ціле число. Два цілих числа називаються числами однаковою парності, якщо обидва вони парні чи непарні обидва. Два цілих числа називаються числами різної парності, якщо одне з них парне, а інше непарне. Розглянемо властивості парних і непарних чисел важливі, для вирішення завдань. 1) Якщо хоча б один множник твори двох (або декількох) чисел четен, то і весь твір парне. 2) Якщо кожен множник твори двох (або декількох) чисел непарне, то і весь твір непарній. 3) Сума будь-якої кількості парних чисел є число парне. 4) Сума парного і непарного чисел є число непарне. 5) Сума парного кількості непарних чисел є число парне; сума непарної кількості непарних чисел є число непарне. Завдання 5.1. У п'ятиповерховому будинку з чотирма під'їздами підрахували число жителів на кожному поверсі і, крім того, в кожному під'їзді. Чи можуть все отримані 9 чисел бути непарними? Рішення. Позначимо число жителів на поверхах відповідно через а1, а2, а3, а4, а5, а число жителів у під'їздах - відповідно через b 1, b 2, b 3, b 4. Тоді загальна кількість жителів будинку можна підрахувати двома способами - по поверхах і по під'їздах: a1 + а2 + а3 + а4 + а5 = b 1 + b2 + b3 + b 4. Якби всі ці 9 чисел були непарними, то сума в лівій частині записаного рівності була б непарної, а сума в правій частині - парному. Отже, це неможливо. Відповідь: не можуть. 5.2. У футбольному турнірі в одне коло беруть участь 15 команд. Доведіть, що в будь-який момент турніру знайдеться команда, яка зіграла до цього моменту парне число матчів (може бути, жодного). Рішення. Позначимо число матчів, проведених першої, другої, третьої і т. д. командами, через а1, а2, а3, ..., А15. Припустимо, що всі ці 15 чисел непарних. Підрахуємо загальне число матчів, проведених командами. Воно дорівнює (А1 + а2 + ... + А15) / 2. Але чисельник дробу є число непарне, як сума непарного числа непарних доданків. Тоді загальна кількість матчів є число дробове. Отримали протиріччя. Затвердження завдання є окремий випадок однієї з теорем теорії графів. 5.3. Парне чи непарне твір (7а + b - 2 c +1) (3 a - 5 b + 4 c + 10), де числа a, b, c - цілі? Рішення. Можна перебирати випадки, пов'язані з парністю або непарних чисел а, b, c (8 випадків!), Але простіше поступити інакше. Складемо множники: (7 a + b - 2 c + 1) + (3 a - 5 b + 4 c + 10) = = 10 a - 4 b + 2 c + 11. Так як отримана сума непарна, то один із множників цього твору четен, а інший непар. Отже, сам твір парне. Відповідь: парне. 5.4. Нехай а 1, а 2, а 3, ..., а 25 - цілі числа, а з 1, с 2, с 3, ..., з 25 - ті ж самі числа, взяті в іншому порядку. Доведіть, що число (А 1 - з 1) (а 2 - з 2) (а 3 - з 3) ... (а 25 - з 25) є парним. 5.5. Парне чи непарне число 1 - 2 + 3 - 4 + 5 - 6 + ... + 993? Рішення. Різниця 1 - 2 має ту ж парність, що і сума 1 + 2, різниця 3 - 4 - ту ж парність, що і сума 3 + 4, і т. д. Тому дана сума має ту ж парність, що і сума 1 + 2 + 3 + 4 + 5 + 6 + ... + 993. З 993 доданків останньої суми 496 парних і 497 непарних, отже, сума непарній. П о в е т: непарній. 5.6. На пряме розташовано кілька точок. Потім між кожними двома сусідніми точками поставили ще по точці. І т. д. Доведіть, що після кожної такої операції загальна кількість точок буде непарним. Зазначення. Якщо є п точок і до них додається ще п - 1 проміжних точок, то загальна кількість точок стає непарних, так як п + (п -1) = = 2 п - 1. 5.7. Знайдіть всі цілі значення а, при яких число x 3 + ax 2 + 5x + 9 непарній для всіх цілих значень х. 5.8. На семи картках написали числа 1, 2, 3, 4, 5, 6 і 7. Потім картки перевернули, перемішали і на зворотних сторонах написали ті самі числа. Числа, написані на обох сторонах кожної картки, склали і отримані суми перемножила. Парне або непарній отримане твір? Рішення. Припустимо, що твір непарній. Для цього всі 7 множників повинні бути непарними. Але тоді у чотирьох карток, у яких на одній стороні написані непарні числа 1, 3, 5, 7, на іншій стороні повинні бути числа парні. Однак парних чисел тут - тільки три. Отже, цей випадок неможливий. Відповідь: парне. 5.9. Доведіть, що в будь-якій компанії число тих людей, які знайомі з непарним числом членів компанії, парне. Рішення. Позначимо число людей, які мають у компанії непарне число знайомих, через k, а число знайомих цих людей відповідно через a 1, a 2, ..., a k. Крім того, число людей, знайомих з парним числом членів компанії, позначимо через n, а число знайомих цих людей відповідно через b 1, b 2, ..., b n. Тоді загальна кількість знайомств одно (A 1 + a 2 + ... + a k + b 1 + b 2 + ... + b n ) / 2 Сума b 1 + b 2 + ... + b n парна, так як всі її складові парні. Тоді для того, щоб ця частина була рівна цілому, сума a 1 + a 2 + ... + a k , Повинна бути парному. Але всі складові останньої суми непарних, тому число k доданків суми може бути тільки парним. 5.10. Доведіть, що не існує багатогранника, у якого 1997 граней - трикутники, а інші грані - чотирикутники і шестикутники. 5.11. Окружність розділили на 40 рівних дуг і в 40 точках розподілу поставили по шашці. Серед шашок 25 білих і 15 чорних. Доведіть, що серед шашок знайдуться біла і чорна, які стоять на кінцях одного діаметра. Рішення. Припустимо, що це не вірно. Розглянемо будь-яку білу шашку і діаметр, на якому вона стоїть. Тоді на нашу допущенню на іншому кінці цього діаметру повинна стояти теж біла шашка. Виходить, що всього білих шашок (як і чорних) парне число. Але останнє суперечить умові задачі. 5.12. Сума номерів будинків одного кварталу дорівнює 99, а сусіднього кварталу тієї ж вулиці - 117. Знайдіть номери всіх будинків цих кварталів. 5.13. У деякому натуральному числі довільно переставили цифри. Доведіть, що сума отриманого числа з вихідним не може бути дорівнює 999 ... 9 (125 дев'яток). Рішення. Позначимо вихідне число через а, число, отримане з нього після перестановки цифр - через b. Припустимо, що рівність а + b = 999 ... 9 (125 дев'яток) можливо. Тоді при додаванні чисел а і b не може бути перенесення одиниці в наступний розряд. Так як сума цифр чисел а і b рівні, то сума цифр у числа а + b у два рази більше, ніж у числа а, а значить вона парні. Але з іншого боку, ця сума дорівнює 9 125, а отже, непарна. Ми отримали протиріччя. 5.14. Яке найбільше кількість натуральних чисел можна записати в рядок так, щоб сума будь-яких трьох сусідніх чисел була парною, а сума будь-яких чотирьох сусідніх чисел - непарної? Рішення. Позначимо послідовні натуральні числа рядка через а 1, а 2, а 3 і т. д. За умовою суми а 1 + а 2 + а 3, а 2 + а 3 + а 4, а 3 + а 4 + а 5, а 4 + а 5 + а 6 та інші парні. Віднімаючи з кожної суми, починаючи з другої, попередню отримаємо, що різниці а 4 - а 1, а 5 - а 2, а 6 - а 3, ... парних, а отже, мають однакову парність пари чисел а 4 і а 1, а 5 і а 2, а 6 і а 3 і т. д. Випишемо непарні суми, що складаються з чотирьох сусідніх чисел: а 1 + а 2 + а 3 + а 4 = (а 1 + а 2 + а 3) + а 4, а 2 + а 3 + а 4 + а 5 = (а 2 + а 3 + а 4) + а 5, а 3 + а 4 + а 5 + а 6 = (а 3 + а 4 + а 5) + а 6, ... Звідси випливає, що числа а 4, а 5, а 6 і т. д. непарних. Але тоді сума а 4 + а 5 + а 6 непарна, а це суперечить умові. Отримане протиріччя виникає кожного разу, коли чисел не менше шести. Спробуємо взяти п'ять чисел. Розмірковуючи аналогічно, встановлюємо, що числа а 4, а 5 непарних, а отже, за попереднім, непарних і числа а 1, а 2. Тоді, так як сума а 1 + а 2 + а 3 парна, то число а 3 парне. Зробимо ще перевірку і переконаємося в тому, що якщо взяти п'ять чисел а 1, а 2, а 3, а 4, а 5, де число а 3 парне, а інші непарних, то кожна із сум а 1 + а 2 + а 3 , а 2 + а 3 + а 4, а 3 + а 4 + а 5 парна, а кожна із сум а 1 + а 2 + а 3 + а 4, а 2 + а 3 + а 4 + а 5 непарних. Відповідь: 5. 5.15. Чи можна на картатій папері, зафарбувати 25 клітин так, щоб у кожної з них було: а) парне, б) непарне число зафарбованих сусідів? (Клітини називаються сусідами, якщо у них спільна сторона) Рішення. Припустимо, що вдалося зафарбувати 25 клітин потрібним чином. Спробуємо знайти число загальних сторін зафарбованих кліток і прийдемо до протиріччя. Порахуємо, скільки в кожної клітини загальних сторін з сусідами, складемо отримані числа і суму розділимо навпіл (так як кожну загальну сторону ми вважали при цьому двічі). У кожної клітини - непарне число сусідів, і клітин 25. Сума 25 непарних чисел непарна і тому без остачі на 2 не ділиться. Відповідь: а) можна, б) не можна. Таке ж міркування показує, що при будь-якій непарній n, зафарбувати n клітин так, щоб у кожній було непарне число зафарбованих сусідів, неможливо. У разі будь-якого парного n таке розфарбовування можлива. 5.16. Чи існує замкнута ламана, яка перетинає кожне свою ланку рівно один раз і складається з: а) 6 ланок, б) 7 ланок? Прості і складені числа Натуральне число, більше 1, називається простим, якщо воно ділиться тільки на 1 і на саме себе. Натуральне число називається складовим, якщо воно має більше двох різних дільників. Прийнято вважати, що число 1 не відноситься ні до простих, ні до складних чисел. Звідси випливає, що безліч натуральних чисел можна розбити на такі три підмножини: безліч простих чисел, безліч складових чисел і безліч містить єдиний елемент 1. Справедлива наступна теорема. Будь-яке натуральне число, більше 1, можна і до того ж єдиним чином представити у вигляді добутку простих чисел. Це пропозиція називається основною теоремою арифметики натуральних чисел. Серед простих дільників натурального числа можуть бути рівні, і їх добуток можна записати у вигляді ступеня. Тоді розкладання натурального числа а на прості множники можна представити в наступному вигляді: a = p 1 k 1 p 2 k 2 ... p n kn , де p 1, p 2, ..., p n - Різні прості числа, k1, k2, ..., kn - натуральні. Завдання 5.17. До двузначному числа приписали таке ж число. Чи може отримане число бути простим? 5.18. До числа, що є твором двох послідовних натуральних чисел, приписали праворуч число 21. Доведіть, що отримане число - складене. 5.19. Натуральні числа a і b такі, що 31 a = 54 b. Доведіть, що число a + b - складене. Рішення. Так як число 31 а ділиться на 54 і числа 31 і 54 - взаємно прості, то а ділиться на 54: a = 54 n; де n ÎN. Тоді 31 54 n = 54 b, b = 31n. Звідси a + b = 54 n + 31 n = 85 n, а отже, число a + b є складовим. 5.20. Натуральні числа a і b задовольняють умові 15 a = 32 b. Чи може число a - b бути простим? Якщо може - побудуйте приклад, якщо не може - доведіть. 5.21. Назвіть всі натуральні n, при яких число n 4 + 4-складене. Рішення. Спробуємо розкласти вираз n 4 + 4 на множники з цілими коефіцієнтами. Ми звикли до того, що сума квадратів на множники з цілими коефіцієнтами не розкладається. У даному випадку це робиться за допомогою прийому «плюс - мінус» наступним чином: n 4 + 4 = (n 4 + 4 + 4 n 2) - 4 n 2 = (n 2 + 2) 2 - 4 n 2 = (n 2 + 2 n + 2) (n 2 - 2 n + 2) . Очевидно, множник n 2 + 2 n + 2 завжди більше 1. Другий множник n 2 - 2 n + 2 може бути рівним 1: n 2 - 2 n + 2 = 1, n 2 - 2 n + 1 = 0, (n - 1) 2 = 0, n = 1. Тому що при n = 1 множник n 2 + 2 n + 2 приймає значення 5, що є простим числом, то значення n = 1 потрібно відкинути. Відповідь: все n не рівні 1. 5.22. Доведіть, що будь-яке число виду а = 101010 ... 101 (n нулів, n + +1 одиниця, де n> 1) - складене. Рішення. Перетворимо число а, враховуючи, що всього у нього 2 n + 1 цифр, а отже, перша одиниця - розряду 2 n: a = 101010 ... 101 = 10 2n + 10 2n-2 + 10 2n-4 + ... + 10 2 + 1 = = (1 / (10 2 -1)) (10 2 - 1) (10 2n + 10 2n-2 + ... +10 2 +1) = = (1 / 99) (10 2n +2 -1) = (1 / 99) ((10 n +1) 2 - 1) = (1 / 99) (10 n +1 +1) (10 n +1 -1). Тепер розглянемо два випадки. 1) Нехай n парне. Тоді сума 10 n +1 +1 ділиться на 11, причому частка від такого розподілу більше 1, тому що 10 n +1 +1> 11; різниця 10 n +1 -1 ділиться на 9, причому приватне також більше 1, тому що 10 n +1 +1> 11; різниця 10 n +1 -1 ділиться на 9, причому приватне також більше 1. Вийшло складене число а = ((10 n +1 +1) / 11) ((10 n +1 -1) / 9). 2) Нехай n непарне. У цьому випадку різниця 10 n +1 -1 ділиться на 10 2 - 1 = 99 і приватне більше 1, оскільки 10 n +1 -1> 99. 5.23. Доведіть, що всі числа виду 10001,100010001,1000100010001, ... - Складові. 5.24. Доведіть, що число 8 (3 травня k + 5 травня n) - 5 при будь-яких натуральних k і n є складеним. 5.25. Яке найбільше число простих чисел може бути серед 15 послідовних натуральних чисел, великих 2? Рішення. Очевидно, прості числа потрібно шукати серед непарних. З 15 послідовних натуральних чисел є 7 чи 8 непарних. Серед будь-яких трьох послідовних чисел натуральних рівно одне ділиться на 3, тому серед 7 або 8 послідовних непарних натуральних чисел є 2 або 3 числа, що діляться на 3. Якщо їх відкинути, то залишиться 5 або 6 непарних чисел. Потрібно ще переконатися, що такі 6 простих чисел можливі. Наприклад, якщо взяти такі 15 послідовних натуральних чисел: 3, 4, 5, 6, ..., 17, то серед них - 6 простих. 3, 5, 7, 11, 13, 17. П о в е т: 6. 5.26. Складіть з простих чисел всі можливі арифметичні прогресії з різницею 6 і числом членів, великим 4. 5.27. Доведіть, що всі числа p, p + 2, p + 4 є простими тільки у випадку, коли вони утворюють трійку 3, 5, 7. Рішення. Розглянемо кілька випадків, в залежності від p. При p = 2 число p +2 = 4 - складене, тому значення p = 2 відпадає. При p = 3 отримаємо трійку 3, 5, 7, про яку згадується в умові завдання. При p = 5 число p + 2 = 7 - просте, але число p + 4 = 9 - складене, значить, p = 5 потрібно відкинути. При p = 7 число p + 2 = 9 - складене. При p = 11 число p + 4 = 15 - теж складене. Виникає припущення, що підходить тільки p = 3. Доведемо його. Неважко помітити, що значення p = 5, p = 7, p = 11 не підходили тому, що або p + 2 або p + 4 діляться на 3. Переконаємося, що так буде завжди при простому p> 3. Просте число, більше 3, не ділиться на 3 і, отже, при діленні на 3 може давати в залишку лише 1 або 2. Розглянемо обидва випадки. 1) Нехай p при діленні на 3 дає в залишку 1: p = 3k + 1 (kÎN). Тоді число p + 2 = (3k + 1) + 2 = 3k = 3 ділиться на 3, причому частка від цього поділу більше 1. Значить число p + 2 складене. 2) Нехай p = 3k + 2 (kÎN). Тоді число p + 4 = (3k + 2) + 4 = 3k + 6 - складене. 5.28. Знайдіть всі такі p, що числа p, p + 10 і p + 20 - прості. Завдання цього пункту - це, по суті, числові ребуси. Своєрідність таких завдань у тому, що одна з двох компонент дії виходить з іншої шляхом перестановки або закреслення цифр. Завдання на закреслення цифр у натуральному числі 5.29. Знайдіть всі натуральні числа, які при закреслення останньої цифри зменшуються в 14 разів. Рішення. Позначимо дані число через 10 x + y, де x - кількість десятків числа, y - його остання цифра. Тоді 10 x + y = 14 x, y = 4 x. Так як y є цифра, то і x - цифра, причому не перевершує 2. Вважаючи x = 1, 2, знаходимо, що відповідно y = 4, 8. |