|
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
| azur: В свое время одна (не математическая, но весьма даже шахматная) проблема привела к необходимости посчитать количество неизоморфных "латинских" матриц mxn. Помучался сам день-другой и .. полез в инет. И хоть дело прояснилось только для случая 2хn, зато в процессе поисков познакомился с несколькими интересными математиками, работающими в области комбинаторики .. :-) |
azur, поделитесь, что такое латинские матрицы, а то я только латинские квадраты знаю..  |
|
|
| номер сообщения: 49-2-1288 |
|
|
|
|
| iourique:... я нигде не говорил, что колпаки надеваются случайно и равновероятно. Предположим, что организаторы игр - те еще жуки, и, увидев, что мудрецы пользуются определенной стратегией, начинают ей противодействовать, например, чаще надевая на всех мудрецов колпаки одного цвета. Если мудрецы могут передоговариваться перед каждым раундом, смогут ли они все равно обеспечить себе выигрыш с вероятностью 3/4? |
Правильно ли я понимаю, что мудрецы знают, с какой вероятностью организаторы решают выбрать колпаки одного цвета? Если да, и эта вероятность достаточна велика (больше 3/4 по прикидкам), то можно получить 3/4. Но я не уверен, что правильно понимаю условие. |
|
|
| номер сообщения: 49-2-1289 |
|
|
|
|
iourique: | jenya: Трем мудрецам я бы посоветовал такую стратегию: говорить пас, если на двух собратьях колпаки разных цветов. Если же на них колпаки одного цвета, надо записать на бумажку другой цвет. Стратегия не работает, если на всех мудрецах колпаки одного цвета. То есть, вероятность выигрыша - три четверти. |
Это, конечно, правильно. |
А можно ли строго доказать, что три четверти - максимальная вероятность?
__________________________
Audiatur et altera pars |
|
|
| номер сообщения: 49-2-1290 |
|
|
|
|
| iourique: Это, конечно, правильно. За 7 возьметесь? |
Построенная аналогичным образом стратегия для 7 (не работающая при раскладах 0-7 и 2-5; работающая при 1-6 и 3-4) оказывается хуже, чем для 3. Так же обстоит дело и с другими n>3.
То есть, по-моему, n-3 заранее выбранных должны всегда пасовать, а 3 остальных - писать в соответствии со вышеописанной стратегией "на троих", невзирая на цвет остальных. В итоге вероятность выжить всегда будет 3/4.
| iourique: Если нет, давайте я еще схитрю: я нигде не говорил, что колпаки надеваются случайно и равновероятно. Предположим, что организаторы игр - те еще жуки, и, увидев, что мудрецы пользуются определенной стратегией, начинают ей противодействовать, например, чаще надевая на всех мудрецов колпаки одного цвета. Если мудрецы могут передоговариваться перед каждым раундом, смогут ли они все равно обеспечить себе выигрыш с вероятностью 3/4? |
Ну, это просто. Перед началом раунда мудрецы проводят "randomizing" - каждому из них (достаточно для 2 из 3) случайным образом назначается, быть ему позитивом или негативом. Во втором случае цвет колпака в глазах других инвертируется. |
|
|
| номер сообщения: 49-2-1291 |
|
|
|
|
| jenya:Правильно ли я понимаю, что мудрецы знают, с какой вероятностью организаторы решают выбрать колпаки одного цвета? |
Давайте сделаем задачку реалистичной: мудрецы понимают, что организаторы могут выбирать колпаки неслучайно, но у них нет никаких идей, как именно организаторы будут это делать.
P.S. Roger уже все сделал... |
|
|
| номер сообщения: 49-2-1292 |
|
|
|
|
Roger: | iourique: Это, конечно, правильно. За 7 возьметесь? |
Построенная аналогичным образом стратегия для 7 (не работающая при раскладах 0-7 и 2-5; работающая при 1-6 и 3-4) оказывается хуже, чем для 3. Так же обстоит дело и с другими n>3.
То есть, по-моему, n-3 заранее выбранных должны всегда пасовать, а 3 остальных - писать в соответствии со вышеописанной стратегией "на троих", невзирая на цвет остальных. В итоге вероятность выжить всегда будет 3/4. |
Можно лучше.
| iourique: Если нет, давайте я еще схитрю: я нигде не говорил, что колпаки надеваются случайно и равновероятно. Предположим, что организаторы игр - те еще жуки, и, увидев, что мудрецы пользуются определенной стратегией, начинают ей противодействовать, например, чаще надевая на всех мудрецов колпаки одного цвета. Если мудрецы могут передоговариваться перед каждым раундом, смогут ли они все равно обеспечить себе выигрыш с вероятностью 3/4? |
Ну, это просто. Перед началом раунда мудрецы проводят "randomizing" - каждому из них (достаточно для 2 из 3) случайным образом назначается, быть ему позитивом или негативом. Во втором случае цвет колпака в глазах других инвертируется. |
Здорово! |
|
|
| номер сообщения: 49-2-1293 |
|
|
|
|
Quantrinas:
А можно ли строго доказать, что три четверти - максимальная вероятность?
|
Да. А как - пока не скажу. |
|
|
| номер сообщения: 49-2-1294 |
|
|
|
|
iourique: | azur: В свое время одна (не математическая, но весьма даже шахматная) проблема привела к необходимости посчитать количество неизоморфных "латинских" матриц mxn. Помучался сам день-другой и .. полез в инет. И хоть дело прояснилось только для случая 2хn, зато в процессе поисков познакомился с несколькими интересными математиками, работающими в области комбинаторики .. :-) |
azur, поделитесь, что такое латинские матрицы, а то я только латинские квадраты знаю.. |
Это квадраты и прямоугольники, где в каждой строке и в каждом столбце нет повторяющихся элементов
m x n - m строк и n столбцов
если m <= n, значит, в каждой строке те же самые n элементов, все по одному разу
если m > n, наоборот, в каждом столбце m различных элементов
Термин "латинские матрицы" необщепринятый (поэтому и кавычки), но изредка применяется (когда берут числа в качестве элементов) |
|
|
| номер сообщения: 49-2-1295 |
|
|
|
|
azur: | iourique: azur, поделитесь, что такое латинские матрицы, а то я только латинские квадраты знаю.. |
Это квадраты и прямоугольники, где в каждой строке и в каждом столбце нет повторяющихся элементов
m x n - m строк и n столбцов
если m <= n, значит, в каждой строке те же самые n элементов, все по одному разу
если m > n, наоборот, в каждом столбце m различных элементов. |
А что про n х 3 правда ничего неизвестно? Случай n х 2 вроде простой - n!/е. Или я неправильно понимаю, что такое изоморфизм? |
|
|
| номер сообщения: 49-2-1300 |
|
|
|
|
iourique:
А что про n х 3 правда ничего неизвестно? Случай n х 2 вроде простой - n!/е. Или я неправильно понимаю, что такое изоморфизм? |
Они будут изоморфными при перестановках строк, столбцов или переименовании символов.
Для 2 х n знаю лишь рекурсивную формулу и производящую функцию (считать неизоморфные прямоугольники в этом случае то же самое, что искать количество способов представить n в виде суммы слагаемых, отличных от единицы)
Для всех остальных случаев, похоже, есть только грубые приближения .. |
|
|
| номер сообщения: 49-2-1301 |
|
|
|
|
azur: iourique:
А что про n х 3 правда ничего неизвестно? Случай n х 2 вроде простой - n!/е. Или я неправильно понимаю, что такое изоморфизм? |
Они будут изоморфными при перестановках строк, столбцов или переименовании символов.
Для 2 х n знаю лишь рекурсивную формулу и производящую функцию (считать неизоморфные прямоугольники в этом случае то же самое, что искать количество способов представить n в виде суммы слагаемых, отличных от единицы)
Для всех остальных случаев, похоже, есть только грубые приближения .. |
О, понял наконец  . Для случая 2 х n надо считать число сопряженных классов перестановок без фиксированных точек. Для случая 3 х n приходится считать число сопряженных классов пар таких перестановок с доп. условием, что их произведение тоже не имеет фиксированных точек... И впрямь непонятно, как такое считать... |
|
|
| номер сообщения: 49-2-1302 |
|
|
|
|
Странно, что никто кроме Юрика не откликнулся на задачу о пятне. Правда, для математика она в сущности автоматическая :-), но ведь не все здесь математики, а звучит имхо чрезвычайно завлекательно. И судя по упоминанию ограниченности - решение самого Donkey не автоматическое :-)
А я подсел на задачку о степенях. Думать не мог - не было времени(сегодня начал), но всё другое закрыло :-) Впрочем, задачки с вероятностями и с лат матрицами мне не интересны, а про машины и тетраэдр я решал раньше.. Впрочем, про тетраэдр мне кажется тривиальной - вроде решение с максимальной стороной должно приходить сразу. |
|
|
| номер сообщения: 49-2-1304 |
|
|
|
|
Grigoriy: Странно, что никто кроме Юрика не откликнулся на задачу о пятне. Правда, для математика она в сущности автоматическая :-), но ведь не все здесь математики, а звучит имхо чрезвычайно завлекательно. И судя по упоминанию ограниченности - решение самого Donkey не автоматическое :-)
А я подсел на задачку о степенях. Думать не мог - не было времени(сегодня начал), но всё другое закрыло :-) Впрочем, задачки с вероятностями и с лат матрицами мне не интересны, а про машины и тетраэдр я решал раньше.. Впрочем, про тетраэдр мне кажется тривиальной - вроде решение с максимальной стороной должно приходить сразу. |
Я слышал такое решение (к которому, при желании, можно придраться, я думаю).
Накладываем кальку как-нибудь. Разрезаем на квадратики и складывем их стопочкой. "Прокалываем иголкой" всю стопку так, чтобы иголка ни на одном квадратике не задела фрагмента пятна. Раскладываем, с сохранением порядка. Сдвигаем на вектор "левый верхний угол - прокол"... Претензии - ни ко мне... |
|
|
| номер сообщения: 49-2-1306 |
|
|
|
|
А про тетраэдр задачка - хорошая. Я говорил, почему именно. Бывают задачи "геометрические", которые можно решить при помощи каких-то выкладок... (Грубо говоря, при помощи теоремы Пифагора.)
А эту как решить при помощи выкладок?...
А вот это - известная задачка, наверное.
В треугольнике найти точку, сумма расстояний от которой до вершин треугольника - минимальна... |
|
|
| номер сообщения: 49-2-1307 |
|
|
|
|
"Автоматическое" профессиональное решение в сущности такое же. Пусть наша область - А. Снесём её в единичный квадрат, т е рассмотрим преобразование., которое любую точку В переводит в точку единичного квадрата с координатами - дробными частями координат В - иначе, отнимаем от координат их целые части. Поскольку площадь А < 1, существует точка Е не в образе. Тогда если к Е прибавить любой вектор с целыми координатами, то получившаяся точка не м б никакой точкой В из А. В самом деле, пусть есть точка В в А. Если отнять от неё вектор с её целыми частями - это не б Е по построению, а если любой другой целый - то даже не попадём в единичный квадрат, где расположена Е.
А про минимум решение просто очевидно - центр описанной окружности
Точнее, сразу получается автоматом. |
|
|
| номер сообщения: 49-2-1308 |
|
|
|
|
| Не. Насчёт задачи с суммой расстояний у меня был глюк. |
|
|
| номер сообщения: 49-2-1309 |
|
|
|
|
| Grigoriy: Не. Насчёт задачи с суммой расстояний у меня был глюк. |
Точка, из которой стороны видны под углом в 120 градусов. Только я доказывать не умею, если треугольник не равнобедренный....
p.s. придумал: пусть O - точка, реализующая минимум для треугольника ABC. Пошевелим O так, что сумма OA+OB остается постоянной, а OC, как следствие, увеличивается. Тогда О движется по эллипсу с фокусами в А и В, а ОС - перпендикулярно касательной к эллипсу. Следовательно, угол АОС равен углу ВОС. Приплыли. |
|
|
| номер сообщения: 49-2-1310 |
|
|
|
|
iourique: | Grigoriy: Не. Насчёт задачи с суммой расстояний у меня был глюк. |
Точка, из которой стороны видны под углом в 120 градусов. Только я доказывать не умею, если треугольник не равнобедренный....
p.s. придумал: пусть O - точка, реализующая минимум для треугольника ABC. Пошевелим O так, что сумма OA+OB остается постоянной, а OC, как следствие, увеличивается. Тогда О движется по эллипсу с фокусами в А и В, а ОС - перпендикулярно касательной к эллипсу. Следовательно, угол АОС равен углу ВОС. Приплыли. |
Я знаю такое красивое рассуждение, отстаивать которое не могу и не буду.
Пусть на горизонтальной плоской поверхности изображен треугольник. Свяжен узлом три веревочки и проденем их (по одной) через отверстия, проделанные в точках - вершинах треугольника. На концы привяжем одинаковые грузы. Эта "система" придет в стабильное положение, в соответствии с принципом "минимума энергии". При этом, сумма длин веревок "под столом" будет максимальна, а "на столе" - минимальна. Сумма трех, равных по модулю, векторов, равна нулю, когда углы 120 градусов... |
|
|
| номер сообщения: 49-2-1312 |
|
|
|
|
iourique: | Grigoriy: Не. Насчёт задачи с суммой расстояний у меня был глюк. |
Точка, из которой стороны видны под углом в 120 градусов. Только я доказывать не умею, если треугольник не равнобедренный....
p.s. придумал: пусть O - точка, реализующая минимум для треугольника ABC. Пошевелим O так, что сумма OA+OB остается постоянной, а OC, как следствие, увеличивается. Тогда О движется по эллипсу с фокусами в А и В, а ОС - перпендикулярно касательной к эллипсу. Следовательно, угол АОС равен углу ВОС. Приплыли. |
Мне очень нравится, как вы рассуждаете. Но (мне) хотелось бы услышать более четкое изложение вашего решения этой задачи... |
|
|
| номер сообщения: 49-2-1313 |
|
|
|
|
| Sad_Donkey: Но (мне) хотелось бы услышать более четкое изложение вашего решения этой задачи... |
Извольте. 4 факта:
1. Эллипс - это множество точек, таких, что сумма расстояний от них до фокусов постоянна.
2. Если О - ближайшая к некоторой точке А точка эллипса (гладкой кривой), то ОА перпендикулярно касательной к эллипсу в точке О.
3. Луч, выпущенный из фокуса эллипса, отразившись от поверхности эллипса, приходит в другой фокус.
4. Угол падения равен углу отражения.
Таким образом, если О - такая точка, что ОА+ОВ равно константе, а ОС - минимально, то углы АОС и ВОС равны. Если О минимизирует ОА+ОВ+ОС, то все три угла при О равны. |
|
|
| номер сообщения: 49-2-1314 |
|
|
|
|
iourique: | Sad_Donkey: Но (мне) хотелось бы услышать более четкое изложение вашего решения этой задачи... |
Извольте. 4 факта:....
|
Спасибо!..
Позволю себе заметить, что при таком уровне подробностей, уместно было бы сделать еще пару замечаний... Ну, это если на конкурс.... |
|
|
| номер сообщения: 49-2-1315 |
|
|
|
|
Sad_Donkey: А вот это - известная задачка, наверное.
В треугольнике найти точку, сумма расстояний от которой до вершин треугольника - минимальна... |
Она называется "точкой Торричелли" или "Первой точкой Ферма"
http://en.wikipedia.org/wiki/Fermat_point
http://mathworld.wolfram.com/FirstFermatPoint.html
В случае, когда треугольник имеет угол >= 120°, точка совпадает с вершиной этого угла.
Если такого угла нет, то точка находится внутри треугольника. Проще всего ее построить с помощью внешних равносторонних треугольников .. |
|
|
| номер сообщения: 49-2-1316 |
|
|
|
|
azur: Sad_Donkey: А вот это - известная задачка, наверное.
В треугольнике найти точку, сумма расстояний от которой до вершин треугольника - минимальна... |
Она называется "точкой Торричелли" или "Первой точкой Ферма"
http://en.wikipedia.org/wiki/Fermat_point
http://mathworld.wolfram.com/FirstFermatPoint.html
В случае, когда треугольник имеет угол >= 120°, точка совпадает с вершиной этого угла.
Если такого угла нет, то точка находится внутри треугольника. Проще всего ее построить с помощью внешних равносторонних треугольников .. |
Спасибо! Я когда-то услышал это как задачу.... Так и рассказал. Мне очень понравилось, как рассуждал Юрик-Йорик (как правильно?)... |
|
|
| номер сообщения: 49-2-1317 |
|
|
|
|
| Sad_Donkey: Мне очень понравилось, как рассуждал Юрик-Йорик (как правильно?)... |
Спасибо. Правильно - Юрик. |
|
|
| номер сообщения: 49-2-1318 |
|
|
|
|
| Надо бы эту тему закрыть, а всех ее авторов - забанить. А то собрались тут какие-то яйцеголовые интеллектуалы, рассуждают совершенно непонятно о чем, навязывают только комплекс неполноценности честным сайтовским гуманитарям... |
|
|
| номер сообщения: 49-2-1319 |
|
|
|
|
| Pirron: Надо бы эту тему закрыть, а всех ее авторов - забанить. А то собрались тут какие-то яйцеголовые интеллектуалы, рассуждают совершенно непонятно о чем, навязывают только комплекс неполноценности честным сайтовским гуманитарям... |
Не только эту... И не только эти... И не только этим...
"Яйцеголовые"...
Когда-то, много-много лет назад, сидел я в командировке на озере Балхаш. Ни один сидел, было нас - тьма... интеллектуалов. Понагнали из Москвы, на всякий случай... Делать было нечего. Одним из дежурных развлечений было разгадывание кроссвордов. Благо была в наличии подшивка журнала "Огонек" за пару лет... Разгадывали, в целом, успешно. Но случались и казусы. Как-то надо было отгадать название морского животного: восемь букв, третья "ю", пятая - "о".
Никто не знал; но синтезировали - "брюхоног". Ведущим у нас был будущий член-корреспондент и директор крупного института. Взял он номер журнала за следующий месяц, стал глазками читать ответы. И вдруг дико расхохотался. "Ты чего, Гена?" - спросили мы.
Гена ответил: "Дураки вы! Никакой это не "брюхоног", а "клюворыл!""... Такие были наши "яйцеголовые" забавы... |
|
|
| номер сообщения: 49-2-1320 |
|
|
|
|
Маленькая забавная задачка.
Выпуклый многоугольник ABCD. Доказать, что его площадь меньше или равна величине:
(AB*CD + BC*DA) / 2 |
|
|
| номер сообщения: 49-2-1321 |
|
|
|
|
Sad_Donkey: Маленькая забавная задачка.
Выпуклый многоугольник ABCD. Доказать, что его площадь меньше или равна величине:
(AB*CD + BC*DA) / 2 |
Здорово! Для решения понадобились ножницы. |
|
|
| номер сообщения: 49-2-1322 |
|
|
|
|
| Возвращаясь к задаче о трех мудрецах в черно-белых колпаках. Решение ясно, хотя мне не очевидна его оптимальность. Мне интересен немного другой момент. Может ли кто-нибудь ясно и коротко объяснить, какая информация позволяет мудрецам повысить вероятность успеха до 3/4? |
|
|
| номер сообщения: 49-2-1323 |
|
|
|
|
MikhailK: Sad_Donkey: Маленькая забавная задачка.
Выпуклый многоугольник ABCD. Доказать, что его площадь меньше или равна величине:
(AB*CD + BC*DA) / 2 |
Здорово! Для решения понадобились ножницы. |
Да... |
|
|
| номер сообщения: 49-2-1324 |
|
|
| |
|
|
|
|
|
|
|
| Copyright chesspro.ru 2004-2024 гг. |
|
|
|
