Доказывать я не мастак, а вот как именно я буду выбирать пирожные, могу рассказать.
Вот процедура, которую я буду повторять 20 раз:
1. Для каждого из ещё не выбранных сортов я посчитаю, по скольким ящикам он разложен.
2. Выберу тот сорт, который разложен по наименьшему количеству ящиков.
3. Возьму пирожное этого сорта из того ящика, в котором пирожных этого сорта больше всего.
И действительно Не работают мои эвристики. И даже чуть более хитрые эвристики отказываются работать.
В то, что задача NP-complete верить пока не хочется.
Слова Вы какие учёные знаете! Но задача то совсем простая, ну, для 5 класса максимум :-)
Решение проведём индукцией по числу к пирожных каждого сорта(одинаковое для всех сортов).
Для к = 2 решение просто. https://niktoinikak.livejournal.com/1573785.html Пусть теперь к > 2 и для всех меньших чем к утверждение доказано.
Возьмём какое-нибудь размещение, для которого утверждение верно, и вытащим соответствующую "нить" (т е по одному пирожному из каждого ящика при том все разных сортов). Тогда для получившегося после этого размещения верно предположение индукции, и, следовательно, можем вытащить ещё одну нить, после этого эщё одну - всего к нитей - при том больше 2-х.
Теперь поменяем местами 2 любых пирожных из разных ящиков. Поскольку при этом мы заденем 1 или 2 нити - останется нетронутая нить. Т е свойсво "можно вытянуть нить" при таком перемещении не нарушится.
Осталось осознать, что любое размещение м б такими перемещениями получено из любого другого. Задача решена.
Да, получилось ровно 10 строчек - хотя я нисколько не экономил :-).
Может, в 5-м классе я бы и понял. И даже на втором курсе. Но сейчас так быстро не соображаю.
А по поводу учёных слов, так я в этом момент решал другую задачу. То было не доказательство того, что решение существует, а попытка найти это существующее решение не перебирая 2432902008176640000 вариантов.
Другое изложение:
1. Существует размещение пирожных по ящикам, при котором можно вытащить по одному пирожному из каждого ящика и все они разных сортов. Это очевидно. Такой выбор назовём "нитью".
2. Существует операция, изменяющая расположение пирожных в ящиках, при которой свойство "можно выбрать нить" сохраняется(описание операции - отдельно, тут это неважно).
3. Посредством нескольких таких операций можно получить из любого первоначально выбранного расположения любое другое. Т к на каждом шагу свойство "можно выбрать нить" сохраняется и существует раcпределение для которого оно выполняется - оно выполняется для любого другого.
4. Эта операция - переложение любых 2-х пирожных. Замечание: индукция используется только в п 2 - что данная операция сохраняет нужное свойство.
Пока понял только, что если удаётся доказать, что всегда существует одно решение, то из этого следует, что всегда существует не менее 10 различных решений.
Вроде понял.
И вроде понял, как использовать это доказательство, чтобы построить алгоритм поиска решения, в котором задача поиска вида (20,10) сводится к примерно 200 поискам вида (20,2).
История ... Обычная. Война всех против всех. Большинство абхазов(больше 60%) в конце 19 века переселилось в Турцию, и большинство населения стали грузины, в советское время - преобладающее большинство, так что Грузия правомерно рассматривала Абхазию как свою часть. Но видимо почти все грузины бежали, так что теперь это неверно.
О Господи. Никакие территории - кроме родного пятачка - не стоят ни одной жизни.
О люди, жалкий род, достойный слёз и смеха.
И с отвращением читая жизнь мою ...
Читaл 1612 год Скрынникова. В частности, описание зверств и ужасов.Узнавая о которых понимаешь, что известный эпизод - повешение 3-летнего сына Мнишек - нормальное для того времени зверство, где посажения на кол, дробление суставов, жарение заживо - постоянно(по всему миру, если читать историю не только России).
Но всегда есть и другие. Вот наткнулся случайно(он описал один из видов молочая) на грандиозного(хотя и малоизвестного видимо - я например, о нём раньше не слыхал) человека - Бернардино де Саагуна Напомнил великого Беду
https://niktoinikak.livejournal.com/608002.html
Grigoriy И Вам не хворать. Изучайте современное искусство в обществе салюки и Кати Дёготь. Наслаждайтесь. И не забывайте совмещать это увлекательное занятие с изучением текстов Лотмана, Хайдеггера и Ортеги-и-Гассета.
Кстати, какие научные открытия совершил Лотман, каков его вклад в науку?
pirron Лотман? Ну, тут надо вспомнить ту роль, которую играла в жизни советской гуманитарной интеллигенции сама Тартуская школа. В СССР, как вы сами понимаете, не могло быть никакого иного литературоведения, кроме марксистского. Формальная школа, объединявшая таких талантливых людей, как Шкловский, Якобсон, Эйхенбаум и др, фактически была запрещена. Якобсон эмигрировал, другие приспособились и жили неплохо, но теоретизированием больше не занимались, заменив его безобидными историко-литературными исследованиями.И вот в Тарту - не случайно не в Москве и не в Питере, а в провинциальном прибалтийском университете - появилась школа, фактически открыто поднявшая знамя не-марксистской теории, Это был нормальный европейский структурализм, опиравшийся как на западные источники - де Соссюра в основном - так и на вот эту формальную школу, в том числе и на те исследования Якобсона, которыми тот занимался уже в эмиграции.Вклад этой группы заключался в первую очередь в том, что она открыла настежь дверь, через которую в советские гуманитарные науки потекли идеи, марксизмом не предусмотренные. Не то чтобы совсем уж чуждые, но не совпадавшие с генеральной линией.В мировом масштабе эта группа не сформировала каких-то революционных. Вклад ее заключался в конкретных исследованиях структуры художественных текстов - главным образом в демонстрации того, что в художественном тексте смыслосодержащими являются такие элементы, которые в повседневном или научном языке таковыми не являются.Извините, должен сейчас убегать - сына надо встречать...
Grigoriy В переводе на русский - Лотман славен тем, что находясь на содержании у власти, показывал ей фигу в кармане. И мастерски сосал "гуманитарной интеллигенции" - т е сословию проституток, недовольных как самим фактом своей проституции, так и недостаточной, по их мнению, оплате их миньетов. Я так примерно и представлял(не научные заслуги Лотмана, о коих я, как и Вы, не в курсе), а почему Вы его имя произносите с пиететом.
