0
1

Сколькими способами отношение делимости на множестве натуральных чисел {1,2,3,4,5,6,12,24,120} МОЖНО дополнить до отношения полного порядка

задан 18 Июн '17 8:09

изменен 18 Июн '17 23:17

10|600 символов нужно символов осталось
1

Ясно, что 1 идёт в самом начале, а 120 в самом конце. Между этими значениями на произвольное место можно будет вставить 5 после того, как все остальные числа расставили по местам. Поэтому далее 5 учитывать не будем.

Перед 120 идёт 24, а перед ним 12. Между 1 и 12 пойдут числа 2, 3, 6 -- либо в таком порядке, либо как 3, 2, 6. Число 4 можно ставить на любое место между 2 и 12. Для первого варианта годятся 3 способа, для второго 2 -- итого 5. К каждому из таких 5 способов можно 6 способами вписать число 5. Итого получается 30 линейных порядков, продолжающих частичный.

ссылка

отвечен 18 Июн '17 19:58

А по какому принципу расставляются числа? 1 в начале потому что он на все делится, а 120 в конце потому что он ни на что не делится? Что такое полный порядок?

(18 Июн '17 21:23) GiBi
1

@GiBi: принцип именно такой, то есть мы продолжает отношение "быть делителем". Под "полным" (лучше говорить "линейным") понимается такой порядок, когда любые два элемента сравнимы. То есть один считается "больше" другого, а второй "меньше". Но не обязательно по величине. Изначально требуется только то, что если x делит y, то x должно быть меньше y. Числа 2 и 3 могут располагаться как угодно, так как ни одно из них не делит другое. То есть они как бы равноправны, а исходный порядок по этой причине "полным" не будет, и его мы разными способами продолжаем.

Вообще, тут надо прочитать определения.

(18 Июн '17 23:49) falcao

Не понятно, почему "число 4 можно ставить на любое место между 2 и 12", ведь число отношений для 4 равно двум (с числами '1' и '2'), что однозначно определяет его место между 6 (3 отношения - '1', '2', '3') и 3|2 (одно отношение у каждого - с единицей). И поясните, пожалуйста, более подробно про число '5'.

(25 Июн '17 19:22) log0

@log0: число 5 простое, оно делит только 120. С остальными числами оно взаимно просто. Если его поставить куда угодно (например, между 24 и 120), то получится продолжение рассматриваемого частичного порядка. Важно, чтобы не было противоречий с делимостью.

То, что Вы написали про число 4, я не понял. Скажем, я могу взять такой порядок: 2 3 6 4 12. Он продолжает частичный порядок |. Вывод о том, что если 2 идёт перед 3, то после умножения на два, число 4 пойдёт перед 6, неверен, так как таких правил здесь нет. Новый порядок продолжает старый iff числа со свойством d1 | d2 идут именно так.

(25 Июн '17 20:02) falcao

Возможно, у меня неправильное понимание отношений и порядка, но вот мои рассуждения. Определим вес числа x как кол-во пар x, y : xRy и x != y, где R <=> делится на. Тогда вес числа '120' = 8, '24' = 6, '12' = 5, '6' = 3, '5' = 1, '4' = 2, '3' = 1, '2' = 1, '1' = 0. Отсортируем числа согласно их весу, например, от большего к меньшему. Получим: {120, 24, 12, 6, 4, 5|3|2, 1}. Получается, что имеем 3 * 2 * 1 = 6 комбинаций/способов достроить до полного порядка.

(25 Июн '17 20:19) log0

@log0: ниоткуда не следует, что всякий полный порядок получается из частичного с использованием функции веса. В частности, если мы все числа списка кроме 5 упорядочим по величине, а потом поставим 5 между 24 и 120, то получится линейный порядок, продолжающий частичный. Здесь надо исходить из определения. Порядок R2 продолжаем R1, если из условия x R1 y следует x R2 y. Проверьте, что мой пример этим свойством обладает. Нужно только одно: если x делит y, то нельзя в списке ставить y раньше, чем x. Никаких других ограничений нет.

(25 Июн '17 21:02) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×1,481
×627

задан
18 Июн '17 8:09

показан
988 раз

обновлен
25 Июн '17 21:02

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

по почте:

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

по RSS:

Ответы

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

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