Здравствуйте, задача с олимпиады для 8 класса,
так что теорией графов, и другими разделами
высшей математики, при ее решении, пользоваться
нельзя ...
Дана квадратная таблица NxN, клетки которой
заполнены целыми числами, таким образом, что разность
чисел в соседних (имеющих общую грань) клетках равна
1, либо 0, либо -1.
Доказать, что в таблице присутствует число повторенное
не менее N раз.
C>Дана квадратная таблица NxN, клетки которой
C>заполнены целыми числами, таким образом, что разность условие связанности
C>чисел в соседних (имеющих общую грань) клетках равна
C>1, либо 0, либо -1.
C>Доказать, что в таблице присутствует число повторенное
C>не менее N раз.
Попробую...
Лемма 1: В квадрате 2х2 всегда есть минимум 2 одинаковых числа
Попробуем найти такое расположение, чтобы в квадрате не было 2 одинаковых чисел.
Ставим в любую клетку число X. - квадрат симметричен, поэтому, пусть будет левый верхний угол.
X ?
? ?
Очевидно, что больше ни один Х ставить нельзя.
Тогда рядом с Х можно поставить только +1 или -1.
Два одинаковых числа (++ или --) ставить тоже нельзя, значит, ставим один + и один -
В силу симметричности не важно куда именно
Х -
+ ?
Для выполнения условия "связанности" на оставшееся место можно поставить только Х
Это означает, что в квадрате 2х2 всегда будут минимум два одинаковых числа.
Любой NxN (N > 2 ) квадрат можно разбить на подобласти 2х2 - их будет (N-1)^2
В каждой подобласти должно быть минимум 2 совпадающих числа (по лемме 1),
=> ((N-1)^2) = (N^2 - 2N + 1) = N^2 - 2N + 1 пар одинаковых чисел в квадрате
Всего же чисел N^2
N^2 - (N^2 - 2N + 1) = 2*N - 1 максимум разных чисел во всем квадрате
От противного:
Для того, чтобы одинаковых чисел было менее N
во всем квадрате должно быть более N^2 - N + 2 разных чисел
Но
(2*N - 1) < (N^2 - N + 2) или, что то же самое: 0 < N^2 - 3*N + 3, для N >= 2
Противоречие. Значит в любом квадрате есть как минимум N одинаковых чисел.
UgN>Любой NxN (N > 2 ) квадрат можно разбить на подобласти 2х2 - их будет (N-1)^2
UgN>В каждой подобласти должно быть минимум 2 совпадающих числа (по лемме 1),
=> ((N-1)^2) = (N^2 - 2N + 1) = N^2 - 2N + 1 пар одинаковых чисел в квадрате
UgN>Всего же чисел N^2
Уважаемый UgN! Тут я не уверен, что Вы правы (это отнюдь не означает, что вы неправы)! Помните задачку: В любых 5 последовательный месяцах доходы меньше расходов. Может ли быть, что за год в целом, доходы больше расходов?
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
UgN>Лемма 1: В квадрате 2х2 всегда есть минимум 2 одинаковых числа
UgN>Попробуем найти такое расположение, чтобы в квадрате не было 2 одинаковых чисел.
UgN>Ставим в любую клетку число X. - квадрат симметричен, поэтому, пусть будет левый верхний угол.
UgN>X ?
UgN>? ?
UgN>Очевидно, что больше ни один Х ставить нельзя.
UgN>Тогда рядом с Х можно поставить только +1 или -1.
UgN>Два одинаковых числа (++ или --) ставить тоже нельзя, значит, ставим один + и один -
UgN>В силу симметричности не важно куда именно
UgN>Х -
UgN>+ ?
UgN>Для выполнения условия "связанности" на оставшееся место можно поставить только Х
UgN>Это означает, что в квадрате 2х2 всегда будут минимум два одинаковых числа.
UgN>
Упс. А кто мешает в таблице 100*100 один квадратик 2*2 заполнить одинаковыми и больше их нигде не применять?
UgN>Любой NxN (N > 2 ) квадрат можно разбить на подобласти 2х2 - их будет (N-1)^2
UgN>В каждой подобласти должно быть минимум 2 совпадающих числа (по лемме 1),
=> ((N-1)^2) = (N^2 - 2N + 1) = N^2 - 2N + 1 пар одинаковых чисел в квадрате
UgN>Всего же чисел N^2
fAX>
fAX>Уважаемый UgN! Тут я не уверен, что Вы правы (это отнюдь не означает, что вы неправы)!
Ваше право (каламбур, однако!). А что именно смущает?
fAX>Помните задачку: В любых 5 последовательный месяцах доходы меньше расходов. Может ли быть, что за год в целом, доходы больше расходов? Что-то смутное шевелится, но можно сказать, что эту задачку я не знаю.
Здравствуйте, UgN, Вы писали:
UgN>Здравствуйте, Demon, Вы писали:
D>Упс. А кто мешает в таблице 100*100 один квадратик 2*2 заполнить одинаковыми и больше их нигде не применять?
UgN>Попробуй. UgN>У меня не получается.
ОК. Тогда вот четкое доказательство несостоятельности одного из переходов
UgN>Лемма 1: В квадрате 2х2 всегда есть минимум 2 одинаковых числа
UgN>Попробуем найти такое расположение, чтобы в квадрате не было 2 одинаковых чисел.
UgN>Ставим в любую клетку число X. - квадрат симметричен, поэтому, пусть будет левый верхний угол.
UgN>X ?
UgN>? ?
UgN>Очевидно, что больше ни один Х ставить нельзя.
Почему это? Если у нас таблица 100*100, никто не мешает нам поставить еще 98 чисел Х.
В задаче не сказано что условие должно выполняться для каждой из подтаблиц
<skip>
Здравствуйте, Chorkov, Вы писали:
C>Здравствуйте, задача с олимпиады для 8 класса, C>так что теорией графов, и другими разделами C>высшей математики, при ее решении, пользоваться C>нельзя ...
C>
C>Дана квадратная таблица NxN, клетки которой
C>заполнены целыми числами, таким образом, что разность
C>чисел в соседних (имеющих общую грань) клетках равна
C>1, либо 0, либо -1.
C>Доказать, что в таблице присутствует число повторенное
C>не менее N раз.
1) Лемма: Если в строке\столбце имеются как число <=С, так и число >=С, то С также присутствует (между ними, очевидно)
2) Ищем в каждой строке минимальный элемент
3) Ищем среди найденных на предыдущем шаге максимальный элемент, обозначим его значение А, а номер строки — x1
4а) Если А имеется в каждой строке — успех
4б) Имеется строка, в которой все элементы меньше А, её номер — х2
Результат:
В каждом столбце имеется число >=А(в строке х1) и <=А(в строке х2) , следовательно, есть и А
Здравствуйте, Demon, Вы писали:
D>Упс. А кто мешает в таблице 100*100 один квадратик 2*2 заполнить одинаковыми и больше их нигде не применять?
UgN>Попробуй. UgN>У меня не получается. D>ОК. Тогда вот четкое доказательство несостоятельности одного из переходов
D>
UgN>Лемма 1: В квадрате 2х2 всегда есть минимум 2 одинаковых числа
UgN>Попробуем найти такое расположение, чтобы в квадрате не было 2 одинаковых чисел.
UgN>Ставим в любую клетку число X. - квадрат симметричен, поэтому, пусть будет левый верхний угол.
UgN>X ?
UgN>? ?
UgN>Очевидно, что больше ни один Х ставить нельзя.
<skip>
D>
D>Почему это? Если у нас таблица 100*100, никто не мешает нам поставить еще 98 чисел Х. D>В задаче не сказано что условие должно выполняться для каждой из подтаблиц
Извиняюсь, возможно, я не очень четко выразился.
В доказательстве я пытаюсь найти такое расположение, при котором не будет двух одинаковых чисел в квадратике 2х2.
Поэтому второй Х ставить нельзя (именно в этом квадратике)
Здравствуйте, Les, Вы писали:
UgN>Для того, чтобы одинаковых чисел было менее N UgN>во всем квадрате должно быть более N^2 — N + 2 разных чисел
Les>Думаю, всегда достаточно N + 2
Здравствуйте, UgN, Вы писали:
UgN>Здравствуйте, Les, Вы писали:
UgN>Для того, чтобы одинаковых чисел было менее N UgN>во всем квадрате должно быть более N^2 — N + 2 разных чисел
Les>Думаю, всегда достаточно N + 2
UgN>
UgN>N = 3
UgN>N + 2 = 5. А клеточек 9 => 4 числа повторяются.
Хм. Возможно, вы имели в виду что-то другое, но:
Вот множество из 9 чисел, в котором 5 различных, и каждое присутствует не более 2 раз.
Здравствуйте, UgN, Вы писали:
UgN>Здравствуйте, fAX, Вы писали:
UgN>
UgN>Любой NxN (N > 2 ) квадрат можно разбить на подобласти 2х2 - их будет (N-1)^2
UgN>В каждой подобласти должно быть минимум 2 совпадающих числа (по лемме 1),
=> ((N-1)^2) = (N^2 - 2N + 1) = N^2 - 2N + 1 пар одинаковых чисел в квадрате
UgN>Всего же чисел N^2
fAX>
fAX>Уважаемый UgN! Тут я не уверен, что Вы правы (это отнюдь не означает, что вы неправы)! UgN>Ваше право (каламбур, однако!). А что именно смущает?
Квадрат с нечётной стороной
fAX>Помните задачку: В любых 5 последовательный месяцах доходы меньше расходов. Может ли быть, что за год в целом, доходы больше расходов? UgN> Что-то смутное шевелится, но можно сказать, что эту задачку я не знаю.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте, fAX, Вы писали:
UgN> А что именно смущает? fAX>Квадрат с нечётной стороной
Не понял. Если вы имеете в виду, что квадрат с нечетной стороной плохо покрывается квадратиками 2х2, то здесь нет проблемы -- они идут внахлест.
Я сдуру стер эту картинку из своего решения, а не надо было...
Здравствуйте, Les, Вы писали:
Les>Хм. Возможно, вы имели в виду что-то другое, но: Les>Вот множество из 9 чисел, в котором 5 различных, и каждое присутствует не более 2 раз.
Les>{1,1,2,2,3,3,4,4,5}
Да, я имел в виду кое-что другое...
Но вы правы, этот вопрос я не рассмотрел.
Предложенная вами комбинация невозможна при соблюдении условия связанности.
Здравствуйте, UgN, Вы писали:
UgN>Здравствуйте, fAX, Вы писали:
UgN> А что именно смущает? fAX>Квадрат с нечётной стороной
UgN>Не понял. Если вы имеете в виду, что квадрат с нечетной стороной плохо покрывается квадратиками 2х2, то здесь нет проблемы -- они идут внахлест. UgN>Я сдуру стер эту картинку из своего решения, а не надо было...
Я прекрасно понимаю, что Вы имели в виду. Проблема как раз в "нахлёсте". Вы считаете числа в различных позициях различное число раз.
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте, Chorkov, Вы писали:
C>Здравствуйте, задача с олимпиады для 8 класса, C>так что теорией графов, и другими разделами C>высшей математики, при ее решении, пользоваться C>нельзя ...
C>
C>Дана квадратная таблица NxN, клетки которой
C>заполнены целыми числами, таким образом, что разность
C>чисел в соседних (имеющих общую грань) клетках равна
C>1, либо 0, либо -1.
C>Доказать, что в таблице присутствует число повторенное
C>не менее N раз.
На самом деле всё гораздо проще:
Возьмём максимальное число. На сколько от него может уйти минимальное? Да не больше, чем на N (из условия связности)!!! По принципу "голубятни" — Есть как минимум одно число которое содержится N или более раз. (Если меньше, то сумма всех чисел меньше N^2)
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
fAX>На самом деле всё гораздо проще: fAX>Возьмём максимальное число. На сколько от него может уйти минимальное? Да не больше, чем на N (из условия связности)!!! По принципу "голубятни" — Есть как минимум одно число которое содержится N или более раз. (Если меньше, то сумма всех чисел меньше N^2)
Читать: (Если меньше, то количество всех чисел меньше N^2)
...Complex problems have simple, easy-to-understand wrong answers...
(Grossman's Misquote of H.L.Mencken)
Здравствуйте, fAX, Вы писали:
UgN> А что именно смущает? fAX>Квадрат с нечётной стороной
UgN>Не понял. Если вы имеете в виду, что квадрат с нечетной стороной плохо покрывается квадратиками 2х2, то здесь нет проблемы -- они идут внахлест.
fAX>Я прекрасно понимаю, что Вы имели в виду. Проблема как раз в "нахлёсте". Вы считаете числа в различных позициях различное число раз.
Так а при чем тут нечетная сторона квадрата?
А нахлест -- это не проблема -- это основа решения.
Я просто считаю пары совпадающих чисел.
Мне не важно какие они, но важно что они есть (обязательно!) согласно лемме.
Каждую пару я посчитаю только один раз.
И каждая пара сокращает количество различных чисел в ячейках квадрата.
Что-то смутное шевелится, но можно сказать, что эту задачку я не знаю.
