ChessPro online

Забавные задачки и головоломки

вернуться в форум

30.09.2007 | 20:54:28

Главная  -  Поговорим?  -  Наука

332

iourique

09.01.2009 | 21:28:29

все его сообщения:
за день, за месяц,
за все время
Вброшу еще задачку - она, на мой взгляд, трудная, но с удивительно простым ответом. Еще бы мне кто объяснил, почему он такой...

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

примеры:

1 шар - 0 шагов.
2 шара - 1 шаг.
3 шара - 4 шага (после первого имеем два одноцветных шара и третий другого цвета. вероятность перекрасить третий за один шаг - 1/3, соответственно в среднем нужно еще 3 шага).

Ответ в общем случае уже можно угадать . Доказать тоже можно, но ничего убедительного я не нашел.
номер сообщения: 49-2-1483

333

MikhailK

1 разряд

10.01.2009 | 22:00:10
Email

все его сообщения:
за день, за месяц,
за все время
Интересная задача. К сожалению теория вероятности не самая моя любимая область математики. Удалось перевести вопрос в область дифференциальных уравнений (уравнение на производящую функцию для совместной функции распределения)
номер сообщения: 49-2-1484

334

iourique

10.01.2009 | 22:55:06

все его сообщения:
за день, за месяц,
за все время
MikhailK: Интересная задача. К сожалению теория вероятности не самая моя любимая область математики. Удалось перевести вопрос в область дифференциальных уравнений (уравнение на производящую функцию для совместной функции распределения)


Ух ты! А совместная функция распределения чего?
номер сообщения: 49-2-1485

335

MikhailK

1 разряд

10.01.2009 | 23:13:38
Email

все его сообщения:
за день, за месяц,
за все время
iourique:
MikhailK: Интересная задача. К сожалению теория вероятности не самая моя любимая область математики. Удалось перевести вопрос в область дифференциальных уравнений (уравнение на производящую функцию для совместной функции распределения)


Ух ты! А совместная функция распределения чего?

Пусть в мешке лежит N шаров. Занумеруем цвета шаров числами от 1 до N. Пусть тогда P_k(m_1,m_2,...,m_N) - вероятность найти на k-ом шаге в мешке m_1 шаров цвета 1, m_2 шара цвета 2, ... , m_N шаров цвета N. Для функции P_k(m_1,m_2,...,m_N) несложно написать рекуррентное соотношение. Переходя к производящей функции для P_k(m_1,m_2,...,m_N) получаем дифференциальное уравнение в частных производных. Чем мне всё это поможет в решении задачи я ещё даже не думал, но уравнение уже составил.

Добавлено.

Ух! Мне даже удалось получить формальный явный ответ! Вот только вычислить его пока затруднительно, так как в знаменателе стоит дифференциальный оператор. Будем думать.
номер сообщения: 49-2-1486

336

navd

27.01.2009 | 22:19:13
Email

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



И - неожиданная связь шахмат и математики - это магический квадрат, сумма чисел в каждом ряду по горизонталям и вертикалям равна 260.
номер сообщения: 49-2-1544

337

MikhailK

1 разряд

27.01.2009 | 22:40:13
Email

все его сообщения:
за день, за месяц,
за все время
здорово!

There Are No Magic Knight's Tours on the Chessboard
номер сообщения: 49-2-1545

338

patrikey

любитель

27.01.2009 | 23:16:03

все его сообщения:
за день, за месяц,
за все время
MikhailK: здорово!
There Are No Magic Knight's Tours on the Chessboard

Другими словами, квадрат, приведенный navd, "полу-магический" - диагонали "неправильные".
Чуда не произошло. Прямой перебор не переборешь.
номер сообщения: 49-2-1546

339

MikhailK

1 разряд

27.01.2009 | 23:35:53
Email

все его сообщения:
за день, за месяц,
за все время
patrikey:
MikhailK: здорово!
There Are No Magic Knight's Tours on the Chessboard

Другими словами, квадрат, приведенный navd, "полу-магический" - диагонали "неправильные".
Чуда не произошло. Прямой перебор не переборешь.

В исходном сообщении navd про диагонали ничего и не обещал. Он просто употребил термин магический квадрат в слабом смысле.
номер сообщения: 49-2-1547

340

patrikey

любитель

28.01.2009 | 00:06:02

все его сообщения:
за день, за месяц,
за все время
MikhailK: В исходном сообщении navd про диагонали ничего и не обещал. Он просто употребил термин магический квадрат в слабом смысле.

Да, да, конечно. К авторам - никаких претензий.
Просто удивился сильно сперва: по-русски написано, что есть квадрат, а по-английски, что нету.
А за ссылку, кстати, спасибо большое!
номер сообщения: 49-2-1548

341

Grigoriy

01.02.2009 | 19:39:34

все его сообщения:
за день, за месяц,
за все время
Трудная задача :-)
Можно ли в единичный квадрат насыпать 1965 точек так, что любой прямоугольник площадью более 1/200 со сторонами , параллельными сторонам квадрата и находящийся целиком внутри его, содержал хотя бы одну из этих точек?
номер сообщения: 49-2-1562

342

MikhailK

1 разряд

02.02.2009 | 19:20:37
Email

все его сообщения:
за день, за месяц,
за все время
Grigoriy: Трудная задача :-)
Можно ли в единичный квадрат насыпать 1965 точек так, что любой прямоугольник площадью более 1/200 со сторонами , параллельными сторонам квадрата и находящийся целиком внутри его, содержал хотя бы одну из этих точек?
Помилосердствуйте! Я до сих пор по ночам вздрагиваю, всё кажется, что удалось разгрызть задачу iourique. А с Вашей задачей совсем сон потеряю.
номер сообщения: 49-2-1563

343

Grigoriy

02.02.2009 | 20:32:34

все его сообщения:
за день, за месяц,
за все время
Задача не моя :-) Я её не решил, олимпиадники в 1965(как легко догадаться) видимо тоже - в сборнике она помечена звёздочкой. А конструкция мне показалась весьма остроумной :-) Если хотите, могу послать в личку :-)
Кстати, судя по отсутствию реакций - она и обьективно нелегка.
номер сообщения: 49-2-1564

344

MikhailK

1 разряд

03.02.2009 | 10:45:12
Email

все его сообщения:
за день, за месяц,
за все время
Grigoriy: Задача не моя :-) Я её не решил, олимпиадники в 1965(как легко догадаться) видимо тоже - в сборнике она помечена звёздочкой. А конструкция мне показалась весьма остроумной :-) Если хотите, могу послать в личку :-)
Кстати, судя по отсутствию реакций - она и обьективно нелегка.

Стойте, стойте! Ответов пока не надо. У меня появилось пару суперидей.

Добавлено

Суперидеи оказались не столь хороши. Вот если бы точек было около 3000, то у меня есть решение.
номер сообщения: 49-2-1566

345

iourique

03.02.2009 | 15:14:22

все его сообщения:
за день, за месяц,
за все время
MikhailK: Вот если бы точек было около 3000, то у меня есть решение.


Вы, кажется, хотите взять каждую 14-ую точку решетки, а вроде бы хватает каждой 28-ой. Проверять лень.
номер сообщения: 49-2-1567

346

Grigoriy

03.02.2009 | 18:23:17

все его сообщения:
за день, за месяц,
за все время
Равномерная выборка по решётке не работает - во всяком случае, у меня не получилось - нужно слишком много точек. Конструкция мне известная - другая.
номер сообщения: 49-2-1568

347

iourique

03.02.2009 | 18:41:41

все его сообщения:
за день, за месяц,
за все время
Grigoriy: Равномерная выборка по решётке не работает - во всяком случае, у меня не получилось - нужно слишком много точек. Конструкция мне известная - другая.


Разве? Берем решетку 201х201 (с границей для верности), отмечаем все точки типа (х/200, у/200), где х-у=0(25). Не вижу как туда положить что-то с большей площадью, чем 169/40000. А отмеченных точек около 1600.

Это, правда, как-то слишком просто - наверно, вру где-то.
номер сообщения: 49-2-1569

348

Grigoriy

03.02.2009 | 18:48:00

все его сообщения:
за день, за месяц,
за все время
Ничего не понял. Что значит х-у=0(25)?
номер сообщения: 49-2-1570

349

MikhailK

1 разряд

03.02.2009 | 18:54:34
Email

все его сообщения:
за день, за месяц,
за все время
Grigoriy: Ничего не понял. Что значит х-у=0(25)?


возможно 0 mod 25

Тогда всё похоже сводится к наклоненной квадратной решетке для которой у меня получилась оценка в 3000 точек.

Интересно, а какая оценка получается в случае паркета Пенроуза? Какого максимального размера можно вписать прямоугольник вот в такую решетку?
номер сообщения: 49-2-1571

350

iourique

03.02.2009 | 19:37:12

все его сообщения:
за день, за месяц,
за все время
MikhailK:
Grigoriy: Ничего не понял. Что значит х-у=0(25)?
возможно 0 mod 25

Угу.
номер сообщения: 49-2-1572

351

Grigoriy

03.02.2009 | 20:53:25

все его сообщения:
за день, за месяц,
за все время
Юрик, мне лень смотреть и считать. Конструкция в моей книжке - и придуманная самостоятельно РР в параллельном мире(тема "Задачки. Морковкин, скучаем") обладает тем преимуществом, что её удовлетворительность видна сразу (там тоже получается около 1500 точек; 1965, как уже сказано - случайное число :-) )
Но тем же недостатком что и Ваша - она даёт некую оценку сверху, но ничего не говорит о точности этой оценки.
номер сообщения: 49-2-1573

352

Grigoriy

13.02.2009 | 17:05:43

все его сообщения:
за день, за месяц,
за все время
Крыс:
Grigoriy: Чич, что ты несёшь?! Красота в математике везде! Что м б красивей совсем простенькой теоремки: медиана проведённая к гипотенузе равна её половине. И я таких совершенно элементарных по понятиям и методам д-ва и в то же время потрясающей красоты накидаю десятки.
ну ещё к примеру:
1. В любом разбиении куба на конечное число кубов найдётся пара равных кубов.

А сколько минимальное количество равных квадратов при разбиении квадрата на конечное число квадратов (а доказать?)? А при соотв. разбиении 5-мерного "куба"? А красивую общую формулу min числа одинаковых "кубов" при разбиении "куба" размерности N?
Уж любоваться математикой, так любоваться...


1. Квадрат можно разбить на неравные квадраты.
2. Формулы меня совсем не интересуют. Если Вам интересно - в тему приведите красивые :-)
номер сообщения: 49-2-1600

353

Крыс

одноглазый любитель

14.02.2009 | 00:57:49

все его сообщения:
за день, за месяц,
за все время
Grigoriy:
1. Квадрат можно разбить на неравные квадраты.
Опа! А пример можно? Видимо у меня с фантазией не все так хорошо, как некоторые здесь думают.

2. Формулы меня совсем не интересуют. Если Вам интересно - в тему приведите красивые :-)

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


__________________________
бэз примэчаний
номер сообщения: 49-2-1601

354

Roger

14.02.2009 | 01:07:27

все его сообщения:
за день, за месяц,
за все время
Крыс:
Grigoriy:
1. Квадрат можно разбить на неравные квадраты.
Опа! А пример можно? Видимо у меня с фантазией не все так хорошо, как некоторые здесь думают.

Неравный квадрат - это квадрат с неравными сторонами.
номер сообщения: 49-2-1602

355

iourique

14.02.2009 | 01:08:00

все его сообщения:
за день, за месяц,
за все время
Крыс:
Grigoriy:
1. Квадрат можно разбить на неравные квадраты.
Опа! А пример можно? Видимо у меня с фантазией не все так хорошо, как некоторые здесь думают.


номер сообщения: 49-2-1603

356

Grigoriy

14.02.2009 | 01:15:41

все его сообщения:
за день, за месяц,
за все время
Крыс:
Grigoriy:
1. Квадрат можно разбить на неравные квадраты.
Опа! А пример можно? Видимо у меня с фантазией не все так хорошо, как некоторые здесь думают.

2. Формулы меня совсем не интересуют. Если Вам интересно - в тему приведите красивые :-)

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


Да я вроде ответил по существу. Формулы же меня действительно совсем не интересуют.
Добавлю ещё, что задача о разбиении квадрата пришла из электротехники. Имеет ли к ней отношение задача о кубах или вопрос возник по аналогии - не в курсе. Это работа А. Стоуна(паракомпактность метрических пространств), кажется в соавторстве с кем-то.
номер сообщения: 49-2-1604

357

iourique

14.02.2009 | 01:40:24

все его сообщения:
за день, за месяц,
за все время
iourique:
Крыс:
Grigoriy:
1. Квадрат можно разбить на неравные квадраты.
Опа! А пример можно? Видимо у меня с фантазией не все так хорошо, как некоторые здесь думают.




Упс. Виноват. Вот:

номер сообщения: 49-2-1605

358

Grigoriy

14.02.2009 | 04:57:49

все его сообщения:
за день, за месяц,
за все время
Ага. То-то я удивился. У Литлвуда написано, что простейший пример очень сложен, а тут ... :-)
номер сообщения: 49-2-1606

359

Roger

14.02.2009 | 05:56:44

все его сообщения:
за день, за месяц,
за все время
Grigoriy: Ага. То-то я удивился. У Литлвуда написано, что простейший пример очень сложен, а тут ... :-)

А тут как раз был описанный мною случай:
Roger: Неравный квадрат - это квадрат с неравными сторонами.
номер сообщения: 49-2-1607

360

iourique

14.02.2009 | 06:48:52

все его сообщения:
за день, за месяц,
за все время
Roger:
Grigoriy: Ага. То-то я удивился. У Литлвуда написано, что простейший пример очень сложен, а тут ... :-)

А тут как раз был описанный мною случай:
Roger: Неравный квадрат - это квадрат с неравными сторонами.

Хорош придираться - почти квадрат был...
номер сообщения: 49-2-1608

361

MikhailK

1 разряд

14.02.2009 | 08:24:48
Email

все его сообщения:
за день, за месяц,
за все время
Зачем прятать красивые задачки в политзоне?

Если интересно, то можно открыть отдельную тему о преподавании в школе.
номер сообщения: 49-2-1609