Расстановки цифр и целых чисел, их преобразования
Немного теории
В решениях задач о конечных последовательностях из целых чисел, букв, фишек, расстановках их по окружности или в таблице сочетаются различные соображения, связанные с делимостью, комбинаторикой, оценками, использующими индукцию.
Задачи с решениями
1. Сто разных фишек положены в один ряд. Любые две фишки, стоящие через одну, можно менять местами. Удастся ли переставить фишки в обратном порядке?
Так как разрешается менять местами лишь фишки, стоящие через одну, то фишка, стоящая на чётном месте, может оказаться лишь на чётном месте, поэтому, например, сотая фишка не может стать первой.
Ответ: не удастся.
2. Дана таблица 4 на 4 клетки, в некоторых клетках которой поставлено по звёздочке. Показать, что можно так расставить семь звёздочек, что при вычёркивании любых двух строк и любых двух столбцов этой таблицы в оставшихся клетках всегда была бы хотя бы одна звёздочка. Доказать, что если звёздочек меньше чем семь, то всегда можно так вычеркнуть две строки и два столбца, что все оставшиеся клетки будут пустыми.
Ясно, что расположение семи звездочек, показанное на рисунке ниже, удовлетворяет условию задачи.
Если же звездочек шесть или меньше, то найдутся два столбца, в каждом из которых стоит не более одной звездочки. Вычеркнем оставшиеся два столбца. После этого останется не больше двух звездочек, которые можно вычеркнуть вместе со строками, в которых они стоят.
Замечание. Было бы интересно исследовать общую аналогичную задачу: какое наименьшее число звездочек можно расставить в таблице m на n, чтобы при вычеркивании любых k столбцов и t строк оставалась хотя бы одна звездочка. (Здесь k, t, m, n – натуральные числа, k < m, t < n.) Но даже для m = n, k = t = n – 2 она весьма трудна.
3. Дан правильный 45-угольник. Можно ли расставить в его вершинах цифры 0, 1, ... , 9 так, чтобы для любой пары различных цифр нашлась сторона, концы которой занумерованы этими цифрами?
Цифра а образует 9 пар (с каждой из девяти остальных цифр). Чтобы для всех этих пар нашлась сторона 45-угольника, занумерованная соответствующими цифрами, необходимо поставить а по крайней мере в пяти его вершинах. Так как цифр всего десять, то для их размещения необходимо 50 мест. Поэтому требуемое в условии размещение цифр невозможно.
Замечание. С другой стороны, если n четно, то числа 0, 1, 2, ... , n можно так расставить в вершинах правильного (n+1)(n+2)/2-угольника, чтобы для каждой пары этих чисел нашлась сторона с соответствующими числами на концах.
Ответ: нельзя.
4. а) Можно ли выписать в строчку 25 чисел так, чтобы сумма любых трёх соседних чисел была положительна, а сумма всех чисел – отрицательна?
б) Один человек каждый месяц записывал свой доход и расход. Может ли быть так, что за любые пять идущих подряд месяцев его общий расход превышал доход, а в целом за год его доход превысил расход?
а) Приведём пример:
–9, 5, 5, –9, 5, 5, –9, 5, 5, –9, 5, 5, –9, 5, 5, –9, 5, 5, –9, 5, 5, –9, 5, 5, –9.
Здесь шестнадцать чисел равны 5 и девять чисел равны –9. Очевидно, что сумма любых трёх соседних чисел равна 1, а сумма всех 25 чисел равна –1.
Ответ: можно.
б) Приведем пример:
2, 2, 2, 2, –9, 2, 2, 2, 2, –9, 2, 2.
Здесь выписаны подряд (с учетом знака) разности между доходами и расходами человека (сальдо) за каждый месяц года. Мы видим, что сумма любых пяти последовательных чисел выписанной цепочки отрицательна, равна –1, а в целом за год сумма всех чисел положительна, равна 2.
Ответ: можно.
Замечание. Обобщение рассмотренных задач: в строчку выписано n чисел, при этом сумма любых k соседних чисел положительна (отрицательна); может ли в такой ситуации сумма всех n чисел быть отрицательной (положительной)? Ответ здесь такой: если n кратно k, то этого быть не может, а если n не делится на k, то может. В задаче а) n = 25, k = 3, в задаче б) n = 12, k = 5.
5. Можно ли на окружности расположить числа
а) 0, 1, 2, ... , 9 так, чтобы любые два соседних отличались на 3, 4 или 5;
б) 1, 2, 3, ... , 13 так, чтобы любые два соседних числа отличались на 3, 4 или 5?
а) Заметим, что никакие два из чисел 0, 1, 7, 8, 9 не могут стоять рядом. Значит, они должны стоять через одно, а остальные пять чисел – между ними. Однако число 2 не может оказаться ни на одном из пяти оставшихся мест, ведь рядом с ним из выписанных чисел может стоять только 7.
Ответ: нельзя.
б) Никакие два из чисел 1, 2, 3, 11, 12, 13 не могут стоять рядом. Следовательно, в шесть промежутков между ними надо поставить остальные семь чисел. В одном из этих промежутков будут два числа из оставшихся, в остальных по одному. Рассмотрим теперь числа 4 и 10. Только 1 может стоять рядом с 4 и только 13 рядом с 10. Тогда 4 и 10 должны стоять рядом, но это противоречит условию.
Ответ: нельзя.
6. а) Докажите, что числа 1, 2, 3, ... , 32 можно расставить в таком порядке, чтобы ни для каких двух чисел их полусумма не равнялась ни одному из чисел, поставленных между ними.
б) Можно ли числа 1, 2, 3, ... , 100 расставить в таком порядке, чтобы ни для каких двух чисел их полусумма не равнялась ни одному из чисел, поставленных между ними?
а) Чтобы получить требуемую расстановку, в одной половине строки запишем четные числа, а в другой – нечетные. При этом полусумма любых двух чисел из разных половин будет не целой и поэтому не содержится между ними. Затем с первой и второй половинами проделаем аналогичную процедуру: каждую из них разобьем на две четверти и разместим в них числа вида 4k, 4k+2, 4k+1 и 4k+3 соответственно: при этом полусумма чисел из разных четвертей в левой половине будет нечетной, а в правой – четной и поэтому не содержится между ними, далее разобьем каждую четверть пополам, причем роль «четных» и «нечетных» чисел теперь будут играть числа с разными остатками от деления на 8 и так далее. В итоге получится такая расстановка:
8, 24, 16, 32, 4, 20, 12, 28, 6, 22, 14, 30, 2, 18, 10, 26,
7, 23, 15, 31, 3, 19, 11, 27, 5, 21, 13, 29, 1, 17, 9, 25.
Доказательство окончено.
б) Для того чтобы доказать это утверждение для любого количества N чисел, достаточно доказать его для N = 2n (лишние числа можно выбросить; например, из расстановки 128 = 27 чисел можно выбросить числа большие 100 и получить нужную расстановку N = 100 чисел). Основная идея уже показана в решении а); более формально и коротко можно изложить доказательство как индукцию по n.
Для n = 1 и n = 2 утверждение очевидно: годятся расстановки (1, 2), (2, 4, 1, 3).
Если a1, a2, ... , aN – расстановка N = 2n чисел 1, 2, ... , N, удовлетворяющая условию, то
2a1, 2a2, ... , 2aN, 2a1 – 1, 2a2 – 1, ... , 2aN – 1
будет расстановкой 2N = 2n+1 чисел 1, 2, ... , 2N, также, как нетрудно убедиться, удовлетворяющей условию: для чисел из разных половин – по соображениям четности, для чисел из одной половины – по предположению индукции.
Ответ: можно.
7. Какое наименьшее число фишек нужно поставить на поля шахматной доски размером
а) 8 на 8 клеток,
б) n на n клеток,
для того, чтобы на каждой прямой, проходящей через центр произвольного поля и параллельной какой-либо стороне или диагонали доски, стояла хотя бы одна фишка? (Фишки ставятся в центры полей.)Расположение такого количества фишек ясно из рисунков 1 и 2. Доказательство того, что меньшим числом обойтись нельзя, проще для четного n; на каждой прямой, параллельной одной диагонали, должно стоять по фишке, а на самой диагонали – две (в углах).
Другое доказательство: на каждой показанной на рисунках пунктиром прямой должно стоять по фишке. Именно это доказательство переделывается на случай нечетного n (рисунок 2): кроме 2n–2 пунктирных прямых (на каждой – по фишке), следует рассмотреть еще шесть прямых, соединяющих центры клеток A, B, C, D; на них нужно потратить еще не менее 3 фишек.
Ответ: а) 16 фишек при n = 8; б) 2n фишек при четном n, 2n+1 – при нечетном n.
8. В клетках шахматной доски в произвольном порядке записаны числа 1, 2, 3, ... , 63, 64, по одному в каждой клетке. За один вопрос, указав любую совокупность полей, можно узнать множество чисел, записанных на этих полях. Докажите, что за шесть таких вопросов можно узнать распределение чисел от 1 до 64 по клеткам шахматной доски.
Сформулируем шесть вопросов, ответы на которые позволяют узнать распределение чисел от 1 до 64 по клеткам шахматной доски.
Пусть Мi, – множество всех чисел, записанных в клетках 1-й горизонтали доски, где i = 1, 2, ... , 8. Сначала укажем три вопроса, которые позволяют определить распределение чисел по горизонталям, то есть определить множества М1, М2, … , М8.
Первый вопрос: «Назовите множество А всех чисел, записанных в клетках 1-й, 2-й, 3-й, 4-й горизонталей доски, – объединение множеств М1, М2, М3, М4».
Заметим, что после ответа на этот вопрос становится известным не только множество А, но и множество A’ всех чисел, записанных в клетках 5-й, 6-й, 7-й, 8-й горизонталей доски, – объединение множеств М5, М6, М7, М8.
Второй вопрос: «Назовите множество В всех чисел, записанных в клетках 1-й, 2-й, 5-й, 6-й горизонталей доски, – объединение множеств М1, М2, М5, М6».
После ответа на этот вопрос становится известным и множество B’ всех чисел, записанных в клетках 3-й, 4-й, 7-й, 8-й горизонталей доски, – объединение множеств М3, М4, М7, М8.
Третий вопрос: «Назовите множество С всех чисел, записанных в клетках 1-й, 3-й, 5-й, 7-й горизонталей доски, – объединение множеств М1, М3, М5, М7».
Если известно множество С, то, очевидно, известно и множество C’, являющееся объединением множеств М2, М4, М6, М8.
Зная множества А, В, С (а следовательно, и множества A’, B’, C’), можно найти любое из множеств М1, М2, … , М8. Действительно, множество М1 –это общая часть множеств А, В, С; множество М2 – это общая часть множеств А, В, C’; множество М3 – это общая часть множеств А, B’, С; множество М4 – это общая часть множеств A, B’, C’ и так далее.
Далее, задав три аналогичных вопроса о числах, записанных в клетках вертикалей шахматной доски, мы сможем для каждого j=1, 2, … , 8 определить множество Nj всех чисел, записанных в клетках j-й вертикали.
Зная множества М1, М2, … , М8 и множества N1, N2, … , N8, можно определить число в любой клетке шахматной доски. Действительно, в клетке на пересечении i-й горизонтали и j-й вертикали записано число, которое является общим для множеств Мi и Nj.
9. Существуют ли 10 различных целых чисел таких, что все суммы, составленные из 9 из них – точные квадраты?
Обозначим искомые числа и их сумму соответственно через x1, x2, ... , x10 и S. Тогда
S – x1 = n12,
S – x2 = n22,
. . .
S – x10 = n102,
где ni – натуральное число. Следовательно, S = (n12 + n22 + … + n102)/9. Пусть nk = 3k (k =1, ... , 10). Тогда сумма квадратов делится на 9. Ясно, что числа xi = S – ni2 удовлетворяют требованиям задачи. Например,
x1 + x2 + ... + x9 = 9S – (n12 + n22 + ... + n92) = n102.
Ответ: да, существуют.
10. Правильный шестиугольник разбит на 24 треугольника. Во всех 19 узлах фигуры, показанной на рисунке
записаны различные числа. Докажите, что среди 24 треугольников разбиения имеется по крайней мере 7 треугольников, в вершинах которых тройки чисел записаны в порядке возрастания, если мы будем считать против часовой стрелки.
Пусть числа а и b (а < b) стоят в соседних узлах А и В сетки. Проведем маленькую стрелку, направленную влево от АВ, если двигаться от А к В как показано на рисунке ниже.
Если числа, записанные в вершинах некоторого треугольника, возрастают при обходе вершин против часовой стрелки, то внутри этого треугольника находятся ровно 2 стрелки, если по часовой стрелке – то ровно одна. Пусть n – количество треугольников первого типа, второго – m (n + m = 24). Общее количество N стрелок внутри шестиугольника равно
2n + m = 2n + 24 – n = n + 24.
Осталось доказать, что N > 31 (тогда n = N – (n + m) > 31 – 24 = 7).
Стрелки, отвечающие 30 внутренним отрезкам разбиения, заведомо лежат внутри шестиугольника. Из 12 остальных стрелок, расположенных по контуру шестиугольника, хотя бы одна должна быть направлена внутрь. (В противном случае, обходя границу шестиугольника по часовой стрелке, мы каждый раз встречали бы все большее число.) Итак, N > 30.
Доказательство окончено.
Задачи без решений
1. Какое максимальное число дамок можно расставить на чёрных полях шахматной доски размером 8 на 8 так, чтобы каждую дамку била хотя бы одна из остальных?
2. Можно ли вершины куба занумеровать различными трёхзначными числами, составленными из цифр 1 и 2 так, чтобы номера любых двух соседних вершин различались не менее чем в двух разрядах?
3. Можно ли написать все 12 чисел 1, 2, … , 12 на окружности так, чтобы для любых трёх чисел a, b, c, стоящих подряд, число b2 = a·c делилось на 13?
4. На листе клетчатой бумаги размером 50 на 50 клеток в каждой клетке записано число. Известно, что в каждых четырёх клетках, которые можно покрыть фигурой вида
сумма чисел равна 4. Докажите, что каждое число равно 1.
5. В концах диаметра окружности стоят единицы. Каждая из получившихся полуокружностей делится пополам, и в её середине пишется сумма чисел, стоящих в концах (первый шаг). Затем каждая из четырёх получившихся дуг делится пополам, и в её середине пишется число, равное сумме чисел, стоящих в концах дуги (второй шаг). Такая операция проделывается n раз. Найдите сумму всех записанных чисел.
Создано на конструкторе сайтов Okis при поддержке Flexsmm - накрутка инстаграм