[Архив!] Чистая математика, физика, химия и т.п.: задачки для тренировки мозгов, никак не связанные с торговлей - страница 292

Хорошо когда есть выбор, чем тренировать

Ну давай. Попробуем добиться обратного.
Для этого минимизируем количество мужчин.
Для чего, в свою очередь, предположим, что множество мужчин бывших в первом походе 100%-но совпадает с множеством мужчин во втором.
Т.е. X1*0.60 = X2*0.75 // X1 и X2 - количество народу в походах, первом и втором соответственно
Отностиельно женщин предположим обратное, что те кто были в первом - во втором не были, и наоборот. // Так мы их потенциально максимизируем.
Т.е. число женщин = X1*0.4+X2*0.25, или что то же самое X1*0.4 + (X1*0.6 / 0.75)*0.25 = X1*0.6, что в точности равно минимальному числу мужчин
Поскольку это минимальный случай для мужчин и максимальный для женщин, то женщин может быть только меньше, а мужчин только больше.
Доказано.
--
Пример рассмотренного расклада: X1 = 3M +2Ж; X2 = 3М + 1Ж

// Вапче задачка для третьего класса вроде. :)

Не. Так, мне кааца, не пойдёт. Слабоватое условие.

Нужно доказать, что каковы бы не были заранее заданные начальные и конечные пары "семья/квартира" в множестве меняющихся, обмен всегда возможен за два хода.

Т.е. недостаточно их расселить куда попадя. Нужно точно туда, куда прицелились. Причём во всех вариантах прицеливания.

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

Ага, набросились. Ну ладно, третий так третий. Спекуляция на минимальностях и максимальностях еще должна быть обоснована, но это уже технические детали.
Задачка с корнем - это, надеюсь, не выше четвертого, т.е. и не стоит того, чтобы решать?А я говорил, что куда попадя? Ну ОК, пусть будет как ты хочешь, это все равно ничего по сути не меняет. Ну тогда - еще одна попытка формализации задачи.
В любом случае окончательные номера квартир после разменов будут транспозицией относительно упорядоченного множества К = (1, 2, ..., n). Обозначим элементарный размен межу i и j как i<->j. Любой сложный представим в виде произведения элементарных.
Тогда, т.к. этот сложный размен полностью обратим, получается так: любую транспозицию Т(К) можно превратить в К с помощью произведения конечного числа элементарных так, что любой конкретный номер i встречается в произведении не более чем 2 раза.
Само количество элементарных обменов может быть каким угодно, т.к. квадрат элементарной транспозиции все равно равен тождественному элементу.

Я решил.

Для начала обратим внимание, что любой сложный размен, состоящий только из парных, с необходимостью либо является циклической цепочкой, либо распадается на несколько циклических цепочек.

Поэтому достаточно, хотя и необходимо, решить задачку для циклической цепочки произвольной длины.

Решаю методом прямого указания стратегии, приводящей к нужному результату.

Запишем начальную цепочку в виде цепочки цифр, где цифра означает семью, а номер позиции в записи - квартиру. В конечной цепочке все семьи должны сместиться по позициям вправо, при этом последняя цифра переходит в начало цепочки. Т.е. например для цепочки из 4 семей запись будет выглядеть так: (1234)->(4123). Тогда для цепочки произвольной длины алгоритм обмена может быть следующим: // распишу на примере цепочек из восьми (чёт) и девяти [нечёт] семей

1) меняем между собой жителей равноудалённых от концов цепочки квартир (12345678)->(87654321), [123456789]->[987654321]

2) отделяем первый элемент получившейся цепи, а с остатком повторяем фишку (87654321)->(81234567), [987654321]->[912345678].

Всё.

Наблюдение насчет цикличности верное, так оно и есть. Осталось аккуратно завершить доказательство.
Ты не указал, как ты будешь делать расчлененку произвольной транспозиции на циклические.
Во-вторых, алгоритм обработки циклической указан только для частного случая. Скажем, есть и такой: (78123456). Ты с ним не показал.
Ну и вообще - покажи, скажем, на примере (12345678) -> (63814257), как ты циклы выделяешь.

[1] Такого нет. То, что ты написал распадается на две цепочки (одна для четных, другая для нечётных).

И вапче, нумерация и фиксирование позиций при записи происходят после составления цепочек. Т.е. сначала составляем цепочки, потом нумеруем. Это снимает все сложности.

Алгоритм цепочкообразования: Берём карту сего тоталитарного города (можно воспользоваться GoogleMap). Обводим кружочками квартиры с угнетёнными квартирообменщиками.

Начиная с произвольного кружочка соединяем исходные квартиры стрелочками с целевыми квартирами. Если приходим в исходную точку и при этом остались неохваченные квартиры - повторяем процедуру начав с любой неохваченной квартиры. И т.д. до полного охвата.

Имеем сформированные выделенные подцепочки либо одну длинную.

Осталось пронумеровать каждую квартиру в цепочке по направлению переезда и перейти к процедуре из предыдущего поста.

Хитер, черт. ОК, уговорил, а в фирме-риэлторе работают математики, знающие теорию транспозиций.

Да и при том жулики. Берут взятки с тех кто желает переехать за один раз (в каждой цепочке таких двое). Впрочем, не буду повторяться - на митинге об этом много говорилось.