Лингвофорум

Дано отношение R над NxN: (a,b)R(c,d) iff a≤c & b≤d.

Нужно дать пример такого А⊆NxN, так что R полностью упорядочивает множество A, но не полностью упорядочивает любое множество В, включающее А (А⊆В⊆NxN).

Мне кажется, что {(a,b)∈NxN|a≤b} и {(a,b)∈NxN|a≥b} подходят, верно же? А есть еще такие?

Цитата: RawonaM от октября  6, 2011, 19:36
Какую можно найти биективную функцию из R в RxR (например из [0,1] в квадрат 1x1)?

Отображение — вообще легко.

Возьмём x ∈ [0, 1], x ≠ 1. Это число однозначно записывается бесконечной десятичной дробью, не оканчивающейся последовательностью девяток:

Положим


Отображение f(x) = (f₁(x), f₁(x)) будет биекцией.

Но это мы две стороны квадрата выбросили. В принципе, можно взять отрезок [0,2], полуинтервал [0,1) отобразить на квадрат без двух сторон, а отрезок [1,2] — биективно на две оставшиеся стороны.

Цитата: Квас от октября  6, 2011, 20:28
Возьмём x ∈ [0, 1], x ≠ 1. Это число однозначно записывается бесконечной десятичной дробью, не оканчивающейся последовательностью девяток:

Положим


Отображение f(x) = (f₁(x), f₁(x)) будет биекцией.

У меня была такая идея. Но как доказать, что это биекция? Как можно знать, что мы все покроем?

Цитата: Квас от октября  6, 2011, 20:28
Но это мы две стороны квадрата выбросили. В принципе, можно взять отрезок [0,2], полуинтервал [0,1) отобразить на квадрат без двух сторон, а отрезок [1,2] — биективно на две оставшиеся стороны.

Ну тогда можно просто взять [0;0.5) отобразить на квадрат без двух сторон, а [0.5,1] на две стороны.

Цитата: RawonaM от октября  6, 2011, 20:39

Цитата: Квас от октября  6, 2011, 20:28Возьмём x ∈ [0, 1], x ≠ 1. Это число однозначно записывается бесконечной десятичной дробью, не оканчивающейся последовательностью девяток:

Положим


Отображение f(x) = (f₁(x), f₁(x)) будет биекцией.

У меня была такая идея. Но как доказать, что это биекция? Как можно знать, что мы все покроем?

Так очевидно же. Инъективность вообще очевидна. Сюръективность: пара

покрывается числом

Единственное, надо иногда делать оговорки насчёт хвоста из девяток, но он нигде не появляется на самом деле.

Цитата: RawonaM от октября  6, 2011, 20:39
Ну тогда можно просто взять [0;0.5) отобразить на квадрат без двух сторон, а [0.5,1] на две стороны.

Или так.

Раз уж мы явно построили отображение [0,1)→[0,1)x[0,1), то можно сначала отрезок [0,1] вдвое растянуть, а потом задать отображение частичными отображениями.

Цитата: RawonaM от октября  6, 2011, 19:20
K_n — количество разбиений множества {1,2,3..n} так, что в каждом классе не более двух элементов.
Нужно найти рекуррентную формулу.

Цитата: RawonaM от октября  6, 2011, 20:02
Дано отношение R над NxN: (a,b)R(c,d) iff a≤c & b≤d.

Нужно дать пример такого А⊆NxN, так что R полностью упорядочивает множество A, но не полностью упорядочивает любое множество В, включающее А (А⊆В⊆NxN).

Мне кажется, что {(a,b)∈NxN|a≤b} и {(a,b)∈NxN|a≥b} подходят, верно же? А есть еще такие?

А с этими что? 

Надо подумать. Я сегодня вечером не очень в форме.

А, хорошо Это я решал экзамен, на который у меня нет ответов. Если мне такой попадется, пиши пропало. Все вопросы как на подбор очень сложные мне показались. Обычно как бы есть баланс, что одни легкие, другие тяжелые, а это прямо получился весь сложный.

Цитата: Квас от Инъективность вообще очевидна.

Цитата: RawonaM от октября  6, 2011, 19:20
K_n — количество разбиений множества {1,2,3..n} так, что в каждом классе не более двух элементов.
Нужно найти рекуррентную формулу.

Это какой-то песец вообще. Как это можно было дать на экзамене?!!

Мне кажется я нашел прямую формулу, а вот рекуррентную не получается. Из прямой рекуррентную как вывести? Хотя конечно по заданию надо вывести рекуррентную и написано что не надо находить прямую, возмжно рекуррентную проще, но я туплю.

Прямая получается так: посчитаем отдельно для каждого количества пар (классов из двух элементов), сколько есть вариантов, затем их сложим. Итого выходит:



Как думаете, верно ли?..

Давайте попробуем!

K₀ = 1. ().
K₁ = 1. (1).
K₂ = 2. (1)(2)  (12) можно оба связать с (1).
K₃ = 4. (1)(2)(3)  (13)(2)  (1)(23) можно связать с первым из предыдущих разбиений, (12)(3) со вторым.
K₄ = 10. (1)(2)(3)(4)  (14)(2)(3)  (1)(24)(3)  (1)(2)(34) из первого, (13)(2)(4)  (13)(24) из второго, (1)(23)(4)  (14)(23) из третьего, (12)(3)(4)  (12)(34) из четвёртого.

Не вижу способа учесть ограничение на два простым способом. Только если каждому разбиению сопоставлять количества одноэлементных и двуэлементных его элементов, пусть они будут s и d. (А d оказывается ненужным.)

Тогда из каждого из разбиений A_{k, n} n-элементного множества можно получить 1 + s_{k, n} разбиений (n + 1)-элементного. Притом числа s для каждого из порождённых разбиений такие: для первого s_{k, n} + 1, для остальных s_{k, n} − 1. Количество всех разбиений получим, суммируя A_{k, n} по k.

Хм. Может, пицца мне поможет.

UPD. Пицца только сказала, что запись (abc)(d)(ef) удобочитаемее, чем abc.d.ef.

Цитата: arseniiv от октября  7, 2011, 12:24
UPD. Пицца только сказала, что запись (abc)(d)(ef) удобочитаемее, чем abc.d.ef.

+1, я как раз хотел об этом сказать.

А первый вариант вы не видели, я его не показывал. В виде множеств, как обычно. Читалось похуже. Хотя лучше, чем точки.

Функция Эйлера, что она возвращает? Вроде как по определению количество числа, которые меньше данного и не делят его (а также 1), я правильно понимаю?
Тогда получается, что если к значению функции Эйлера для некоего числа прибавить количество делителей оного (без 1), должно выйти как раз заданное число, не так ли?
Но у меня рассчеты совсем не сходятся.
Допустим для 120 Эйлер возвращает 32, у 120 вроде как 15 делителей, 32+15 никак не получаются 120.

(wiki/ru) Функция_Эйлера

С вшим определением не сходится. Не все, которые не делят, взаимно просты с.

Насчёт K_n: мне очевидной кажется формула

Может быть, воспользоваться рекуррентным соотношением для биномиальных коэффициентов и получить искомое рекуррентное соотношение путём преобразования формулы?

Цитата: RawonaM от октября  6, 2011, 20:02
Дано отношение R над NxN: (a,b)R(c,d) iff a≤c & b≤d.

Нужно дать пример такого А⊆NxN, так что R полностью упорядочивает множество A, но не полностью упорядочивает любое множество В, включающее А (А⊆В⊆NxN).

Мне кажется, что {(a,b)∈NxN|a≤b} и {(a,b)∈NxN|a≥b} подходят, верно же? А есть еще такие?

Преложенные множества не подходят: например, пары (5, 10) и (6, 9) принадлежат первому множеству и несравнимы.

В качестве примера можно привести

Насчёт универсального способа построения примеров сомневаюсь.

Цитата: Квас от октября  9, 2011, 12:23
Насчёт K_n: мне очевидной кажется формула

Может пояснить?

Выбираем k элементов, которые по одному, а остальные разбиваем на пары.

Цитата: Квас от октября  9, 2011, 12:36
Выбираем k элементов, которые по одному, а остальные разбиваем на пары.

— разве это разбитие на пары?
Допустим осталось 5 разбить на пары, это вроде не С(5,2), а

Ладно, думаем дальше.

Цитата: Квас от октября  9, 2011, 12:30

Цитата: RawonaM от октября  6, 2011, 20:02Дано отношение R над NxN: (a,b)R(c,d) iff a≤c & b≤d.

Нужно дать пример такого А⊆NxN, так что R полностью упорядочивает множество A, но не полностью упорядочивает любое множество В, включающее А (А⊆В⊆NxN).

Мне кажется, что {(a,b)∈NxN|a≤b} и {(a,b)∈NxN|a≥b} подходят, верно же? А есть еще такие?

Преложенные множества не подходят: например, пары (5, 10) и (6, 9) принадлежат первому множеству и несравнимы.

В качестве примера можно привести

Насчёт универсального способа построения примеров сомневаюсь.

А точно нет надмножеств, которые тоже упорядочены?

Цитата: RawonaM от октября  9, 2011, 12:46
А точно нет надмножеств, которые тоже упорядочены?

Добавляем (c, d), тогда d > 1, и пара несравнима с (c+1,1).

Мне этот пример из каких-то геометрических соображений в голову пришёл. Можно ещё другие «кресты» рассматривать (то же самое, но фиксированные k и l вместо 1).

Я вроде как потом придумал .
Такой не пройдет?

Цитата: RawonaM от октября  9, 2011, 12:51
Я вроде как потом придумал .
Такой не пройдет?

Срабатывает тот же мой контрпример.

Нужно такое множество, что если точка (a,b) ему принадлежит, то остальные точки обязательно будут или выше и справа, или ниже и слева (равенство допускается). А у вас — точки, лежащие под прямой a=b; очевидно, они этому условию не удовлетворяют.

Эх, что-то у меня сегодня совсем голова не варит