Регистрация    Вход    Форум    Поиск    FAQ   alexlarin.net

Список форумов » Интересные задачки




 Страница 1 из 2 [ Сообщений: 11 ] На страницу 1, 2  След.



Автор Сообщение
 Заголовок сообщения: А без компа слабо?!
 Сообщение Добавлено: 28 июн 2016, 23:07 
Не в сети

Зарегистрирован: 16 фев 2011, 14:13
Сообщений: 1395
К хозяйке придет 7, 8 или 9 гостей. На какое минимальное количество частей (не обязательно равных) надо разрезать торт, чтобы всех накормить поровну. (хозяйка торт не ест :) )

a) N>=16 (просто);
б) N<=22 (тоже просто);
в) построить пример, где N = 19 (понятия не имею, как бы это сделать быстро и вручную, ответ есть, могу потом выложить;
г) найти минимум (также понятия не имею, как это разумно сделать руками)

Задача с diofant.ru, так что, возможно, у нее и нет разумного некомпьютерного решения.

У кого какие идеи?


Вернуться наверх 
 Заголовок сообщения: Re: А без компа слабо?!
 Сообщение Добавлено: 29 июн 2016, 07:33 
Не в сети

Зарегистрирован: 08 май 2013, 17:36
Сообщений: 993
А зачем строить пример для 19, если это не минимум?

Пришлось основательно порыться в записях - давно это было, да и сюжет был другой, не торт разрезался.
Но не суть. А по сути:

1. У меня есть доказательство (разумное и некомпьютерное) минимальности .
2. У меня есть следующий из этого доказательства пример разрезания.
3. На diofant.ru долгое время засчитывался вообще весьма далекий от истины ответ. И решивших было гораздо больше, чем теперь.

_________________
Да, я зануда


Вернуться наверх 
 Заголовок сообщения: Re: А без компа слабо?!
 Сообщение Добавлено: 29 июн 2016, 10:33 
Не в сети

Зарегистрирован: 16 фев 2011, 14:13
Сообщений: 1395
Ischo_Tatiana писал(а):
А зачем строить пример для 19, если это не минимум?

Пришлось основательно порыться в записях - давно это было, да и сюжет был другой, не торт разрезался.
Но не суть. А по сути:

1. У меня есть доказательство (разумное и некомпьютерное) минимальности .
2. У меня есть следующий из этого доказательства пример разрезания.
3. На diofant.ru долгое время засчитывался вообще весьма далекий от истины ответ. И решивших было гораздо больше, чем теперь.


Может 19 и не минимум, но уже пример с 19 непонятно как строить без существенного перебора.(разумеется, если кому-то известен минимальный/меньший пример, то любой неминимальный/больший строится тривиально :) )

Сколько, кстати, минимум? И как это разумно доказать?

Лучше в ЛС, так как тут кто-то еще хочет сам подумать.

UPD. diofant ссылается на Шарыгина. Не поленился, посмотрел, у него есть похожая задача с другими входными данными и неверным решением :)

UPD2. Кстати, Ваше доказательство универсальное или существенно зависит от входных данных?


Вернуться наверх 
 Заголовок сообщения: Re: А без компа слабо?!
 Сообщение Добавлено: 17 мар 2017, 22:25 
Не в сети
Аватар пользователя

Зарегистрирован: 27 дек 2015, 11:32
Сообщений: 373
Откуда: г. Октябрьск
Три часа вспоминал - откуда решал похожую задачу :confusion-shrug:
Вспомнил, наконец то - задачник "Кванта". Там были взаимно простые p и q.
Склерозззз.

_________________
Придет Серенький, волчок - и укусит за бочок.


Вернуться наверх 
 Заголовок сообщения: Re: А без компа слабо?!
 Сообщение Добавлено: 18 мар 2017, 17:36 
Не в сети
Аватар пользователя

Зарегистрирован: 09 апр 2011, 14:49
Сообщений: 4633
Откуда: Москва
Подробности:
WWS писал(а):
Три часа вспоминал - откуда решал похожую задачу :confusion-shrug:
Вспомнил, наконец то - задачник "Кванта". Там были взаимно простые p и q.
Склерозззз.

1. ТЫЦ.
2.
Подробности:
Вложение:
90_12-22 23.pdf [260.32 KIB]
Скачиваний: 398

_________________
Никуда не тороплюсь!


Вернуться наверх 
 Заголовок сообщения: Re: А без компа слабо?!
 Сообщение Добавлено: 18 мар 2017, 23:52 
Не в сети

Зарегистрирован: 16 фев 2011, 14:13
Сообщений: 1395
OlG писал(а):
Подробности:
WWS писал(а):
Три часа вспоминал - откуда решал похожую задачу :confusion-shrug:
Вспомнил, наконец то - задачник "Кванта". Там были взаимно простые p и q.
Склерозззз.

1. ТЫЦ.
2.
Подробности:
Вложение:
90_12-22 23.pdf


Беда, уважаемый OIG, с Вашими подробностями.

1. Задачка про p и q так просто не обобщается до задачки про p,q и r. Просто обобщение дало бы 22, а минимум, как указано выше, меньше 19-ти.

2. Задачка из "Кванта" намного проще. Непонятно, как она вообще в задачник "Кванта" попала - не тот уровень.

Так что "подробности" имеют к исходной задаче очень отдаленное отношение.


Вернуться наверх 
 Заголовок сообщения: Re: А без компа слабо?!
 Сообщение Добавлено: 20 мар 2017, 15:52 
Не в сети
Аватар пользователя

Зарегистрирован: 09 апр 2011, 14:49
Сообщений: 4633
Откуда: Москва
Подробности:
alex123 писал(а):
Беда, уважаемый OIG, с Вашими подробностями.

1. Задачка про p и q так просто не обобщается до задачки про p,q и r. Просто обобщение дало бы 22, а минимум, как указано выше, меньше 19-ти.

2. Задачка из "Кванта" намного проще. Непонятно, как она вообще в задачник "Кванта" попала - не тот уровень.

Так что "подробности" имеют к исходной задаче очень отдаленное отношение.

3. С Вами тоже беда, уважаемый alex123, с Вашей версией
Моих подробностей.

Ссылку на Квант еще 28 июня нашел примерно за пару минут,
поэтому показалось странным вспоминать эту задачу, имеющую
отдаленное отношение к обсуждаемой, три часа.

_________________
Никуда не тороплюсь!


Вернуться наверх 
 Заголовок сообщения: Re: А без компа слабо?!
 Сообщение Добавлено: 14 апр 2017, 09:18 
Не в сети

Зарегистрирован: 02 сен 2014, 21:14
Сообщений: 84
Откуда: Санкт-Петербург
alex123 писал(а):
2. Задачка из "Кванта" намного проще. Непонятно, как она вообще в задачник "Кванта" попала - не тот уровень.



Ну у Вас и мерки, alex123. Так, на всякий случай -- в задачник Кванта она попала из варианта ленинградского отбора на Всесоюзную олимпиаду. Где её никто (включая нескольких будущих медалистов IMO) не решил.


Вернуться наверх 
 Заголовок сообщения: Re: А без компа слабо?!
 Сообщение Добавлено: 14 апр 2017, 13:34 
Не в сети

Зарегистрирован: 16 фев 2011, 14:13
Сообщений: 1395
mr.maarius писал(а):
alex123 писал(а):
2. Задачка из "Кванта" намного проще. Непонятно, как она вообще в задачник "Кванта" попала - не тот уровень.



Ну у Вас и мерки, alex123. Так, на всякий случай -- в задачник Кванта она попала из варианта ленинградского отбора на Всесоюзную олимпиаду. Где её никто (включая нескольких будущих медалистов IMO) не решил.


1. Можно пруф линк? На происхождение задачи, год [чем год мохнатее, тем проще найти очень простую задачу], и то, что ее никто не решил.

2. Правда настаиваете на том, что исходная задача поста такого же уровня сложности, как из "Кванта"?


Вернуться наверх 
 Заголовок сообщения: Re: А без компа слабо?!
 Сообщение Добавлено: 14 апр 2017, 19:01 
Не в сети

Зарегистрирован: 02 сен 2014, 21:14
Сообщений: 84
Откуда: Санкт-Петербург
2. Нет, я этого и не утверждаю - понятно, что для трёх количеств задача качественно сложнее, возможно даже, что в общем виде ответ на неё неизвестен, можно это попробовать выяснить. В варианте "7,8,9" она впрочем, скорее несравнима с той - наверняка помогают очень конкретные оценки и перебор, пусть и громоздкий (но вот, например, случай p,p+1 гораздо проще общего случая p,q, там не нужно того рассуждения с двудольным графом).

1. 1990 год, отборочный тур, 9 класс, задача 7. Пруфлинков не приведу - сканера дома нет сейчас и в гугле не любят, но вариант есть, например, в широко известной книжке Д.В.Фомина Санкт-Петербургские математические олимпиады. Там, правда, нет статистики (кажется, она есть в менее доступной брошюре Фомина-Кириченко), так что Вам скорее придется поверить мне (или не поверить) на слово. Да, сейчас бы, вероятно, эту задачку на олимпиаде решили, но вряд ли массово. Проверить это проблематично, т.к. она с тех пор стала кружковским фольклором, впрочем и на кружках дети (сильные) её решают не очень (а несильные не решают). Хотя, да, с точки зрения опытного человека тут технически несложное и естественное рассуждение, но это можно сказать про многие "гробы" для школьников.:)

(да, то что это задачка с питерского отбора, можно проверить и не ища книжку Фомина - об этом написано в том номере Кванта, где опубликовано условие задачи)


Вернуться наверх 
Показать сообщения за:  Сортировать по:  
 
 Страница 1 из 2 [ Сообщений: 11 ] На страницу 1, 2  След.





Кто сейчас на форуме

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

 
 

 
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти: