Математика для чайников №2
25 Нояб 2013 21:22 #961
Хайдук wrote:
чисел не нужно, нужно знать что это за операция [tex]\displaystyle \bigoplus[/tex], а [tex]\displaystyle \wedge[/tex] есть конъюнкция, булевское произведениеИ между битами.
И всё-таки - можно пример ? Например у нас есть две строки битов:
Очень милая задачка от Джона Конвея (изобретателя игры "Жизнь").
Есть три карты: туз, король и дама, и они могут лежать на одной из трех позиций на столе перед вами - назовем эти позиции L,M,R (left, middle, right).
Карты всегда лежат лицом вверх, но если больше одной карты лежат в одной позиции, то вы видите только верхнюю. Например, может быть так, что слева лежит король на даме (и вы видите только короля), посредине туз, а справа ничего. Может, все три карты лежат справа, и вы видите только верхнюю. И так далее.
На каждом ходу вы можете переместить одну карту - всегда верхнюю - с любой позиции на любую другую. Например, если слева лежит король на даме, а посредине туз, вы можете решить снять короля и положить его на туза или на пустое место справа.
Ваша задача - придумать алгоритм, как перекладывать карты, чтобы в конце концов придти к выигрышному положению, когда слева лежат туз, король, дама (туз верхний, дама нижняя), а остальные позиции пустые. Но есть одно осложнение. У вас нет краткосрочной памяти. Каждый раз, когда вы делаете ход, вы забываете, что было раньше, и видите только карты, как они лежат сейчас. Иными словами, решение, что двигать куда, может быть основано только на видимых сейчас картах.
(да, из этого следует, что вы не можете обнаружить, когда правильно все сделали. Предполагаем, что есть посторонний наблюдатель, и как только в игре получается состояние туз-король-дама слева, он останавливает вас).
Это все. Нужно придумать алгоритм, который любое начальное положение приводит к выигрышному. Я думаю, что можно эту задачу решить компьютерным способом, а можно на бумаге (может, есть такие монстры, что и в уме смогут, я не из них). Я решил на бумаге, это было не очень легко и довольно приятно. Предупреждаю: если вы нашли решение и оно довольно простое, подумайте как следует, действительно ли вы учли эффект краткосрочной памяти и действительно ли любое начальное положение приходит к победе.
(что это за неслучайные числа такие, я скажу в другой теме, здесь это неважно). Требуется разбить их на две группы: 5 чисел в одной группе с суммой S' и 10 чисел в другой группе с суммой S" так, чтобы отношение S'/S" было ближайшим к 3/4. Для компьютера это пустяковая задача, поскольку необходимо просмотреть всего С(15, 5) = С(15, 10) = 3003 сочетания, ерунда. Наиточнейшим сочетанием оказывается следующее, единственное: красные числа в 1-й группе и синие во 2-й, тогда S'/S" = 20684/27595 = 0.750.
Проблема же в том, чтобы показать, что это сочетание не только наиточнейшее, но и самое вероятное.
Возможно, вы спросите: в каком смысле «самое вероятное»? Вот в этом-то и проблема!
Обратите внимание. "Мир математики" в 40 тт.
Переводная серия. По одному тому в неделю. Два первых тома уже вышли. Я купил.
Изложение элементарное, но вполне современное. 12+ matematika.deagostini.ru/
Чтобы приводить конкретные примеры, книжку надо прочитать, а я пока только пролистал. В общем и целом - занимательная математика.
Прочитал во введении, что, оказывается, обычная банковская карта имеет пропорции золотого сечения. Для меня лично золотое сечение (помимо дробей Фибоначчи) - это 0.6, 0.62, 0.618, ... . Но в случае банковской карты 85.60×53.98 мм это всего лишь 53,98/85.60 = 0.6. Немного почему-то не дотянули до чисел Фибоначчи 89×55 мм, и тогда было бы 55/89 = 0.618.
Простая она логически - не нужно сложных хитроумных рассуждений. Но мне она далась не очень легко - мне трудно себе представить действующие лица, все эти пересечения и обьединения.
"Философы", о которых писал в своё время РР, наверное не смогут её решить, даже если от этого будет зависить их жизнь - тут РР прав. Хотел написать тоже про Пиррона(что ему не сделать), но вспомнил, что он мастер по шашкам - т е он конечно способен это представить. Пиррон, попробуете решить?
Но есть у этой задачи и другой аспект - философский.
Её утверждение кажется странным - вроде никакой связи между множествами справа и слева не видно. И то что она есть - это неожиданное утверждение о Мироздании. Этот факт для чего то существует, понадобился Природе(Богу).С другой стороны - как можно было заметить, открыть этот факт? Видимо, он - деталь в какой-то общей картине,в которой он приобретает осмысленность.В чём может состоять эта картина?
Простая она логически - не нужно сложных хитроумных рассуждений.
Я похоже совсем отупел. Решил для начала рассмотреть случай непересекающихся множеств и чего то я результат этой теоремы воспроизвести не смог. Похоже постепенно превращаюсь в философа.
Вот тут я написал решение на пальцах steinkrauz.livejournal.com/326725.html#comments
Как видите, совсем просто. Вот "вьехать" в условие - тяжело было. Но меня больше интересует "философский" аспект, в частности -как можно это было заметить?
Утверждение, что элемент принадлежит множеству в левой части, равносильно утверждению, что элемент принадлежит одновременно по крайней мере k множествам из (X(i)). Утверждение, что элемент принадлежит множеству в правой части, равносильно утверждению, что элемент принадлежит хотя бы одному из любых k множеств, выбранных из (X(i)).
Если n<=2k-1, то любой элемент из множества в левой части принадлежит и множеству в правой части. Ведь если он принадлежит одновременно k множествам из (X(i)), а всего их не больше 2k-1, то при выборе любых k множеств будет попадаться хотя бы одно из тех, что содержит этот элемент.
Если n>=2k-1, то предположим, что элемент из правой части принадлежит не более чем k-1 множествам из (X(i)). Но тогда из оставшихся множеств из (X(i)) можно будет отобрать k множеств, из которых ни одно не будет содержать этот элемент. Противоречие. Значит, любой элемент из множества в правой части принадлежит по крайней мере k множествам из (X(i)) и, следовательно, принадлежит множеству из левой части.
Григорий, товарищ по Вашей ссылке не ли ошибся утверждением "объединение пересечений входит в пересечение объединений на выборке меньше половины семейства" насчёт первой, видимо, реляции сферху, когда [tex]2k \leqslant n+1[/tex]? Насколько помню, [tex]\subset[/tex] это и есть входит (является подмножеством), а [tex]\supset[/tex] должно, видимо, читаться как влючает/содержит (в качестве подмножества)
Решил для начала рассмотреть случай непересекающихся множеств и чего то я результат этой теоремы воспроизвести не смог
Это не тупость, а глюк. В этом случае всё совершенно очевидно. Нижнее совсем(слева пустота), а верхнее - очень просто. В самом деле, есть 2 множества Р1 и Р2, такие, что составляющие множества 1-ого другие, чем у 2-ого(К мало). Тогда пересечение Р1 и Р2 - пусто(т к множества все непересекающиеся)
Вот до чего доводит крамникофобия! (ради Бога, не обижайтесь )
есть у этой задачи и другой аспект - философский.
Её утверждение кажется странным - вроде никакой связи между множествами справа и слева не видно. И то что она есть - это неожиданное утверждение о Мироздании. Этот факт для чего то существует, понадобился Природе(Богу).С другой стороны - как можно было заметить, открыть этот факт? Видимо, он - деталь в какой-то общей картине,в которой он приобретает осмысленность.В чём может состоять эта картина?
почем подозреваете, Григорий, что у пересечений с объединениями должен быть какой-то глубокий смысл? Действительно симметрия некая даёт о себе знать: с ростом [tex]k[/tex] всё бОльшая часть элементов (множеств исходного семейства) переходит из объединения пересечений в пересечение объединений. При этом выравнивание убывающей части объединения (пересечений) с возрастающей частью пересечения (объединений) происходит при выборке половины исходного семейства, [tex]k \sim \frac{n}{2}[/tex]
, тогда нужно последовательность перевернуть: 110111111 
, кто бы мог подумать, что башка у него такая светленькая, назло совковым кандалам, коими стреножена 
