Сумма 2-х раскрашенных красным и синим множеств есть континуальный квадрат, так? У квадрата должно быть две одинаковые, идентичные континуальные стороны, нет? Как-то не нахожу мест неким, вроде разным (и впервые дающим о себе знать) нечетному и четному множествам (?) в этой картине

Serge_P написал(а):Континуум можно положить равным почти любой т.н. регулярной мощности, то бишь под ним и над счётной мощностью алеф_0 может быть большое число/мощность несчётных мощностей, некоторые из которых континууму запрещены.

Не уверен, может быть, эта задачка уже здесь и упоминалась. Но не грех вспомнить еще разок - решение красивое

Колония маленьких зеленых человечков живёт на клетках шахматной доски. На каждом шаге колония захватывает одну из пустых клеток, у которой 2, 3 или 4 соседа уже захваченных колонией (по диагонали соседи не считаются, только через общую сторону). Если таковых нет - то процесс останавливается. Известно, что изначально было захвачено 7 клеток. Могут ли маленькие зеленые человечки захватить всю доску?

Ээээ...
Чтоб зохавать клетку а1, надо предварительно зохавать клетки а2 и b1. Для этого должны быть предварительно зохаваны клетки а3, b2, c1... И так далее, вплоть до диагонали а7-g1. А на ней 7 клеток. Чтоб ее хавать, должна быть зохавана предварительно большая диагональ а8-h1. А на ней 8 клеток и ее нельзя зохавать с оставшейся половины. Вывод: для зохавывания всей доски нужно минимум 8 зохаванных клеток, причем если их 8, то они должны быть расположены по большой диагонали.

Да, я знаю, что доказательство некорректное

-

Отредактировано LUKA (2012-06-13 10:21:15)

LUKA написал(а):Хмм... Вот колония a1,b1, b2 . Rank 2
По правилам рождается a2 . Rank становится 1.

Пусть каждый зелёный человечек будет ладьёй.
Захват клетки возможен только, если клетка находится под ударом двух ладей (условие необходимое, хотя и недостаточное).
Лемма: Суммарная сумма небитых горизонталей и вертикалей всё равно не будет меньше двух при любых вариантах роста колоний.
Случай 1. В начальной конфигурации все ладьи расположены на разных горизонталях и вертикалях. В этом случае рость колонии возможен только без увеличения количества битых полей. - невозможен захват новых горизонталей и вертикалей - это видно факта конкретного рассмотрения правил роста колоний - в этом случае невозможен рост, когда ЕДИНСТВЕННЫМИ двумя соседями колонизуруемой клетки будут клетки НАПРОТИВ друг друга.
В самом начале игры под двойным ударом не находится часть поля только из-за того, что ладьи захватили лишь 7 горизонталей и 7 вертикалей.
Так как количество битых полей не увеличивается, то в этом случае невозможно создать ситуацию, чтобы все клетки находились под двойным ударом ладей при росте колоний.
Случай 2. В начальной конфигурации часть ладей стоят на одной горизонтали или вертикали больше, чем по одному. В этом случае в начальной конфигурации будет уже больше НЕбитых горизонталей или вертикалей. Пусть для определённости две ладьи стоят на одной горизонтали.

В этом случае возможна ситуация, когда при росте колоний количество битых вертикалей увеличится на 1 - если соседи с ладьями расположены напротив друг друга. Однако в этом случае количество бытых вертикалей увеличится только максимум на 1, что компенсируется тем, что в начальной конфигурации количество НЕбитых горизонталей на 1 больше.

Сколько бы пар ладей в начальной конфигурации ни было - для каждой пары мы сможем родить максимум по одной новой битой вертикали. Но даже в этом случае количество битых горизонталей будет на столько же меньше в начальной конфигурации, сколько пар ладей расположены на одной горизонтали.
Проводим симметричное рассмотрение случаев, когда ладьи стоят на одной вертикали. В этом случае баланс максимально возможной суммы небитых горизонталей и вертикалей сохраняется. Значит, суммарная сумма небитых горизонталей и вертикалей всё равно не будет меньше двух при любых вариантах роста колоний.
Таким образом, при любой начальной конфигурации при росте колоний обязательно останется хотя бы одна горизонталь или вертикаль, которая не бьётся ладьёй (это наследственное свойство и позволяет быть уверенным в незаполнении части клеток).
Этот факт означает, что не все клетки могут быть колонизированы.

Отредактировано LUKA (2012-06-13 12:50:24)

Я хотел выпуклость зайдействовать (каждая новая клетка ее не уменьшает), но через ладьи изящнее и эффективнее

Serge_P написал(а):Насколько я помню, эта теорема в виде задачи встречается в некоторых книжках по теории множеств. Доказательство сформулированного утверждения основано на использовании теоремы Кантора-Бернштейна (Если множество А равномощно некоторому подмножеству множества В, а В равномощно некоторому подмножеству множества А, то множества А и И равномощны).
Вот суперкороткое доказательство. Автор - вроде как и есть сам Кантор, хотя сам Кантор, сформулировав свою замечательную теорему (Кантора-Бернштейна) вроде как так и не привёл её доказательства, а, значит, в данной задаче использовал её без доказательства.
Достаточно доказать, что если квадрат (можно и треугольник, или даже круг рассматривать - monopenisualis) разбит на два множества, то хотя бы одно из них равномощно континууму.
Рассматриваются два случая.
1. Одна из двух объединяемых в континуальное множество частей содержит отрезок. Тогда можно воспользоваться теоремой Кантора - Бернштейна.
2. Если же, для определённости, первая часть не содержит отрезков, то мощность континуума должна иметь вторая часть объединения.
Действительно, в каждом горизонтальном сечении квадрата (треугольника, круга) есть точка второй части (иначе был бы справедлив случай 1). Для построения биекции каждой такой точки сечения с континуальным множеством используется аксиома выбора. Множество горизонтальных сечений квадрата (треугольника, круга) имеет мощность континуума, стало быть и сконструированное с помощью аксиомы выбора подмножество второго множества (взяли с помощью аксиомы выбора по одному элементу второго множества из каждого сечения) - тоже континуальное. Далее снова можно сослаться на теорему Кантора - Бернштейна.
Значит, мощность второго множества - участника объединения - тоже континуальное
Что и требовалось доказать.
Кстати, доказательство и правда красивое.
Как видите, континуум-гипотеза здесь не используется. Зато используется аксиома выбора, причём в сильном (несчётном) варианте.

P.S. Просьба - если кто-то знает красивые решения приведённых здесь задачь - не стесняться и приводить.
Красота = Простота Х Неожиданность.

Отредактировано LUKA (2012-06-13 13:25:45)

LUKA написал(а):Я бы не сказал - доказательство Сергея/Кантора намного проще и неожиданее

ЗЫ. Предупреждение не использовать гипотезу континуума почти лишнее: объединение всего лишь двух меньших множеств никак НЕ может дотянуть до любой мощности.

Хайдук написал(а):Я не читал доказательства Сергея, но думаю, что у Кантора вряд ли сильно отличалось. Поскольку приведённое доказательство излагается лишь в двух шагах (куда уж проще даже не знаю)
Возможны две альтернативы:
1. Одно из двух множеств квадрата содержит отрезок или
2. Горизонтальные сечения содержат элементы второго множества.
Я лишь подробно описал почему это наглядное решение, в том числе и факт использования аксиомы выбора, до чего Кантор не дошёл.
А каково ДРУГОЕ более простое решение?

Отредактировано LUKA (2012-06-13 15:11:39)

quantoforum.ru/mathematics/131-matematik...v-2?start=480#202095

Vladimirovich написал(а):А проще всего, imho, так:

Хайдук написал(а):Только теперь увидел, что нужно выделять мышкой.
Цитата: Очевидно, можно считать что множества не пересекаются. Пусть одно будет красное, второе - синее, и отобразим их объединение на единичный квадрат. Рассмотрим проекцию красного множества на горизонтальную ось. Если эта проекция - весь отрезок [0,1], то тогда красное множество континуально. Если же хоть одна точка этой проекции не принадлежит, то тогда весь перпендикуляр над этой точкой - синий, и значит синее множество континуально.
Однако мне видятся данные рассуждения сходными - в одном случае альтернатива существованию какого-то отрезка вообще (любой длины и направления) и для широкого класса фигур, в другом случае - альтернатива только перпендикулярному отрезку единичной длины. Обе идеи видятся одинаково простыми и очень сходными.

Сергею: хотел попросить не давать так быстро решения, а то стоило выходные поотсутствовать и задачи, и решения.
Спасибо за задачи - будем благодарны за новые.

Отредактировано LUKA (2012-06-13 19:47:31)

Любопытное, элегантное решение очевидной задачке.

Думаю, что будет интересно тянуть с изложением авторского решения как можно дольше, дабы максимум вариантов был изложен. Тем более, что не каждый день удаётся зайти на сайт.
Любопытна версия про выпуклость.

Отредактировано LUKA (2012-06-13 20:03:42)

28 32
Оказалось у Сергея тоже самое. Я когда-то помнится решал (и решил ) аналогичную задачу(а может ту же, смутно помню)

Отредактировано Grigoriy (2012-06-13 20:49:44)

LUKA написал(а):Ну так, я ж решения прячу (белый цвет в цитате), можно проявить силу воли и не подсматривать

LUKA написал(а):

ЛУКА - пахатель задач

Serge_P написал(а):Вообще использование наследственного свойства архиполезнейший приём во многих задачах. Наверно будет полезным вспомнить и другие задачи на использование наследственного свойства.
А вот в матлогике этот приём используют для доказательства независимости аксиом (и других утверждений). А всякие там мат (трансфинитные) индукции - это тоже в некотором роде наследственные свойства.

Докажите, что для любого n1 можно расставить числа 1,2,3,...,n в ячейки матрицы n x n (имеется в виду, без повторений) таким образом, что получится матрица полного ранга.

Serge_P написал(а):Интересный факт, для нечетного n, магический квадрат обеспечивает полный ранг.

PP написал(а):А это можно как-нибудь просто доказать?

Serge_P написал(а):Доказательство идет методом построения. Оно не слишком сложное, но не для чайников. Это я так, эрудицию проявил.

По идее тут должно работать такое нехитрое построение.
1)Записываем числа слева направо, сверху вниз по мере убывания
2)В полученной матрице меняем местами на каждом ряду диагональный элемент и левый элемент.

PP написал(а):Может быть. Но пока не вижу, почему оно работает.

Serge_P написал(а):После первого шага мы получили линейно зависимые векторы - каждый следующий ряд есть предыдущий плюс n. А потом мы свопнули уникальную координату в каждом ряду. Если начать расписывать линейную комбинацию то должно получиться противоречие для самого левого и самого правого элемента каждого ряда. Надо попробовать расписать на бумаге.

Так и хочется свершить
Serge_P написал(а):Доказательство основано на следующей лемме:

Если у нас есть две линейно зависимые строчки
а1, а2, а3, а4, а5, а6, .....
и
b1, b2, b3, b4, b5, b6, ...
то очевидно, что если мы к каким-то (но обязательно не всем) элементам только одной из строчек прибавим 1, то возникнут линейно-независимые строчки.

С использованием этой леммы задача решается просто - легко написать алгоритм построения такой матрицы. Дольше наверно объяснять, чем решать. Построение чем-то напоминает диагональный метод (хотя преобразуются здесь не элементы диагонали, а только элементы (d+1)-го столбца и (d+1)-й строчки, оставляя без изменения матрицу (dxd)):

Пусть у нас уже построена матрица меньшего размера с полным рангом, заполняем матрицу следующего размера методом челнока: сначала вверху столбца, затем слева в стоке, затем вверху столбца, затем слева в строке.

а1 а2 а3 10.....
а4 а5 а6 12.....
а7 а8 а9 14.....
11 13 15 16.....

Зачем? Чтобы для каждого числа в этом крайнем правом столбце мы в всегда в нижней строке имели число, бОльшее его на единицу.

Алгоритм, надеюсь, понятен из рисунка.

Здесь на рисунке это видно 10 в столбце, 11 - в строчке, 12 - в столбце, 13 - в сточке и т.д.
Теперь начинаем проверять линейную зависимость вновь построенного (d+1)-го столбца со всеми остальными.
Если четвёртый столбец линейно зависим с первым, то 10 меняем на 11 (меняем местами цифры в четвёртой строе и столбце!). Всё, этот столбец стал линейно независимым. Теперь, даже если мы в этом столбце какие-то элементы увеличим на 1, то всё равно линейная независимость останется согласно лемме, так как нижний элемент столбца не изменится.

Если со вторым, - то 12 на 13. Если же первое число столбца НЕ преобразовывалось, то надо снова проверить линейную независимость, и если она возникнет, то заменить первое число на единицу бОльшую (методом взаимной замены со строчкой) - после этой процедуры линейная зависимость уже ВНОВЬ не возникнет согласно лемме.
Короче - если увеличиваем k-е число в столбце на единицу, то забываем про это число, так как линейная независимость с k-м столбцом уже не изменится при дальнейших преобразованиях, если же не увеличиваем, то при следующих возможных преобразованиях (k+1)-го, (k+2) и т.д. чисел надо проверять, не возникла ли эта линейная зависимость и тогда увеличить-таки это k-е число на единицу.

Ну и так далее по мере построения матрицы.

Быстрее наверно представил, чем писал.

Отредактировано LUKA (2012-06-18 12:55:31)

LUKA написал(а):Это рассуждение меня не убеждает. Например, даже три вектора уже могут быть линейно независимы попарно но линейно зависимы все вместе, а потому совершенно недостаточно проверять линейную независимость с каждым из векторов индивидуально.

Serge_P написал(а):Сдаётся мне, ув. Сергей, что Вы просто невнимательно прочитали. Разве речь шла ТОЛЬКО о попарной независимости? .
Предполагается, что для всех меньших порядков мы уже построили матрицу с полным рангом. И строим следующую - при этом изменяем только крайний правый столбец и нижнюю строку, не трогая старые построения. Строим последовательно так, чтобы сначала последний столбец был линейно независим с первым, затем - со вторым столбцом, при этом проверяется (если нужно - в случае, если ДО этого не меняли соответствующее первое число, если меняли - то, согласно лемме УЖЕ не нуно возвращаться.) линейная независимость с первым.т
Лемма гарантирует, что с использованием такого рода построением не возникнет вновь линейной зависимости (если уже трогали - увеличивали на единицу n-ю цифру, то линейная независимость останется с n-м столбцом, если нет - то мы её восстановим ОДИН РАЗ увеличив на единицу- и больше не возвратимся)

Отредактировано LUKA (2012-06-18 17:56:49)