Задача
а) Каждая сторона равностороннего треугольника разбита на m равных частей, и через точки деления проведены прямые, параллельные сторонам, разрезавшие треугольник на m² маленьких треугольников. Среди вершин полученных треугольников нужно отметить N вершин так, чтобы ни для каких двух отмеченных вершин A и B отрезок АВ не был параллелен ни одной из сторон. Каково наибольшее возможное значение N (при заданном m)? б) Разделим каждое ребро тетраэдра на m равных частей и через точки деления проведём плоскости, параллельные граням. Среди вершин полученных многогранников отметим N вершин так, чтобы никакие две отмеченные вершины не лежали на прямой, параллельной одной из граней. Каково наибольшее возможное N? в) Среди решений уравнения x1 + x2 + ... + xk = m в целых неотрицательных числах нужно выбрать N решений так, чтобы ни в каких двух из выбранных решений ни одна переменная xi не принимала одного и того же значения. Чему равно наибольшее возможное значение N?
Решение
Покажем, что задача а) эквивалентна задаче в) при k = 3. Примем за единицу расстояние между соседними параллельными прямыми, разрезающими треугольник. Каждой точке треугольника сопоставим три числа: x1, x2 и x3, выражающие расстояния от этой точки до сторон треугольника. Легко видеть, что x1 + x2 + x3 = m для всех точек треугольника.
Заметим, что вершинам маленьких треугольников сопоставлены целые неотрицательные числа. В задаче а) требуется, чтобы ни для каких двух отмеченных вершин A и B отрезок AB не был параллелен ни одной из сторон исходного треугольника. В задаче в) ни в каких двух из выбранных решений никакое неизвестное xi не должно принимать одно и то же значение. Оба требования означают одно и то же. Аналогично проверяется, что задача б) эквивалентна задаче в) при k = 4. Переформулируем задачу в).
Пусть в прямоугольной таблице из k столбцов и n строк можно так расставить неотрицательные целые числа, что сумма чисел в каждой строке равна m и ни в каком столбце числа не повторяются. k и m фиксированы. Каково наибольшее возможное значение n?
В каждом столбце n чисел, и они не повторяются. Значит, сумма их не меньше чем 0 + 1 + ... + (n – 1) = ½ n(n – 1), а сумма чисел во всей таблице не меньше чем ½ kn(n – 1).
С другой стороны, сумма чисел во всей таблице равна mn. Итак, kn(kn – 1) ≤ 2mn, то есть n – 1 ≤ 2m/k.
Значит, n ≤ [2m/k] + 1.
Построим для любых целых k ≥ 2 и m ≥ 0 удовлетворяющие условиям задачи таблицы k×N , где N = [2m/k] + 1.
1) Пусть k = 2r чётно. Если m = rl + q (l ≥ 0, 0 ≤ q < r), то N = l + 1, и искомая таблица – табл. 1.
2) Пусть k = 3.
Если m = 3l + t (t = 0, 1), то N = 2l + 1. Искомая таблица – табл. 2.
Если m = 3l – 1, то N = 2l. Искомая таблица – табл. 3.
3) Пусть k = 3 + 2r – нечётное число, большее 3. Обозначим через p остаток от деления m на k и рассмотрим два случая.
3-1) 0 ≤ p ≤ r + 1. Тогда m = kl + q, q = p, 2q < k, и N = l + 1, Соответствующая таблица образуется добавлением к табл. 2 (с t = 0) таких 2r столбцов, которые получаются, если в табл. 1 заменить l на 2l.
3-2) r + 2 ≤ p ≤ 2r + 2. Тогда m = k(l – 1) + r + 2 + q, 0 ≤ q ≤ r, N = 2l. Соответствующая таблица образуется добавлением к табл. 3 таких 2r столбцов, которые получаются, если в табл. 1 заменить l на 2l – 1.
Ответ
а) [2m/3] + 1; б) [m/2] + 1; в) 1 при k= 1, [2m/k] + 1 при k> 1.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь