Докажите, что при любом целом $%n\geqslant 3$% квадрат можно разрезать на треугольник и $%n$% энугольников.

задан 7 Сен 0:13

1

@Казвертеночка, можно ли, например, для четных n поступить так: 1) отрезаем от одно стороны квадрата узкий прямоугольный треугольник, 2) разбиваем оставшийся четырехугольник на n прямыми (можно параллельными), 3) каждый из полученных четырехугольников разбиваем ломаной линией с нужным числом отрезков?

(7 Сен 22:52) Urt
1

@Urt: в пункте 2 тогда, наверное, на n/2 частей разбиваем?

(7 Сен 23:29) falcao
1

@falcao, да я подразумевал удвоение, но вопрос в принципе. Если так делить можно, то с нечетным n тоже нет проблем: при n=3 очевидно, при n=5, 7,... сначала отрезаем от квадрата прямоугольник и делим его на два треугольника, затем один треугольник разбиваем на три и ломаем стороны, чтобы в сумме в каждом получилось нужное число сторон, затем оставшийся прямоугольник делим на прямоугольники, каждый из которых разрезаем ломаными линиями на нужные многоугольники.

(7 Сен 23:46) Urt
1

@Urt: да, наверное всё должно работать.

Я сам задачи на разрезание чаще всего даже не пытаюсь решать.

(7 Сен 23:54) falcao
2

@falcao, бывает так, что после случайного ознакомления с задачей от нее уже не отделаться. Так у меня произошло с задачей @EdwardTurJ "Условное неравенство" - много вариантов, которые "почти" доводят до решения. Только что увидел еще весьма красивую здесь. Получается довольно интересный результат. Иногда приходится прикладывать усилия, чтобы приостановить этот процесс.

(8 Сен 0:22) Urt
2

@Urt: конечно, бывает, когда задача сильно увлекает, но я имел в виду, что если задачу на разрезание не решил сразу, то мне обычно не хочется дальше её решать.

Вероятностная задача интересная. Там рекуррентные формулы выписываются, но закономерность получается сложная. Я составил программу, и по ней видно, когда надо останавливаться, и каково матожидание для случаев m и n карт того и другого вида. При игре 50:50 оно примерно равно 3,65. И при соотношении 43:50 выгодно было бы карты брать.

(8 Сен 2:15) falcao
1

@falcao, по-видимому, у нас одинаковые рекуррентные соотношения. Для сверки: минимальное число k(n) "хороших" карт, с которого нужно входить в игру, для n=10, 100, 1000 соответственно равно 4, 47, 487. А суммарный выигрыш при наличии половины "хороших" карт для этих значений n в среднем составит: 1,12, 3,66, 11,66. Т. е. преимущество этого игрока с ростом n сокращается (в среднем на один ход).

(8 Сен 2:43) Urt
1

@Urt: да, числа совпали. Правда, до 1000 у меня компьютер долго считал -- там таблица из миллиона чисел!

Я так понимаю, есть статьи, где асимптотика уже исследована, и там получается sqrt(n) с точностью до какого-то точно подсчитанного коэффициента. Так-то из общих соображений было ясно, что ответ порядка корня -- закон повторного логарифма и всё такое.

(8 Сен 20:20) falcao
1

@falcao, скорость расчетов, мне кажется, в значительной степени определяется системой программирования. Я использую VBA с выводом данных при необходимости в файл или лист Excel в виде таблицы. У меня эти расчеты до n=1000 заняли не более секунды. По задачке: из сообщения я понял, что автор делает предположение относительно O(n) на основе моделирования (simulation) и хочет получить оценку в аналитическом виде.

(8 Сен 22:25) Urt
2

@Urt: я знаю, что в других системах скорость вычисления намного выше, но сам использую только Maple, если это не принципиально. Идея в том, то пишется всё очень быстро. И до 1000 я стал считать только чтобы с Вашими цифрами сравнить -- всё совпало досконально.

На stackexchange есть ссылка на работу, где это всё уже сделано в аналитическом виде. Там не только доказано O(sqrt(n)), но и найдено значение константы C для Csqrt(n).

(8 Сен 22:57) falcao
1

@falcao, большое спасибо!

(8 Сен 23:10) Urt

@falcao, @Urt, большое спасибо!

(9 Сен 0:56) Казвертеночка
показано 5 из 12 показать еще 7
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,130
×50
×47
×4
×1

задан
7 Сен 0:13

показан
68 раз

обновлен
9 Сен 0:56

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru