НГУ

Форумы НГУ
Текущее время: Сб фев 16, 2019 2:03 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: задача по логике.
СообщениеДобавлено: Вт май 30, 2006 12:25 pm 
Не в сети
Начинающий автор

Зарегистрирован: Сб авг 27, 2005 6:07 am
Сообщения: 335
Откуда: Аня
По причине того, что на зачете все равно каждый раз новые задачи, а конкретно эта загрузила не только меня, но еще и весь логический мозг нашей группы, то можно все-таки поинтересоваться ответом/решением сей задачи:

Какова можность множества { f:N->N | f(x)<=f(y) при x>=y }?

_________________
Я ёжик. Я упал в реку.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: задача по логике.
СообщениеДобавлено: Вт май 30, 2006 12:28 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Вт ноя 29, 2005 6:34 pm
Сообщения: 1498
hamster писал(а):
По причине того, что на зачете все равно каждый раз новые задачи, а конкретно эта загрузила не только меня, но еще и весь логический мозг нашей группы, то можно все-таки поинтересоваться ответом/решением сей задачи:

Какова можность множества { f:N->N | f(x)<=f(y) при x>=y }?

То есть невозрастающих функций из эн в эн? Помнится, счетно.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: задача по логике.
СообщениеДобавлено: Вт май 30, 2006 12:29 pm 
Не в сети
Начинающий автор

Зарегистрирован: Сб авг 27, 2005 6:07 am
Сообщения: 335
Откуда: Аня
Akademovetz писал(а):
То есть невозрастающих функций из эн в эн? Помнится, счетно.

Ага. Т.е. до ответа я правильно додумалась. Осталось выяснить почему =)

_________________
Я ёжик. Я упал в реку.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: задача по логике.
СообщениеДобавлено: Вт май 30, 2006 12:45 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Вт янв 31, 2006 6:14 pm
Сообщения: 125
Откуда: Буров Павел
hamster писал(а):
Akademovetz писал(а):
То есть невозрастающих функций из эн в эн? Помнится, счетно.

Ага. Т.е. до ответа я правильно додумалась. Осталось выяснить почему =)

Дык берем и нумеруем все такие функции.
Первая --- диагональ.
Вторая --- 1->1, f(n) = n + 1 для остальных случаев
Третья --- f(n) = n + 1
Четвертая --- 1->1, 2->2, f(n) = n+1 для остальных случаев
Пятая --- 1->1, f(n) = n + 2 для остальных случаев
и т.д.
Т.е. бегаем от 1 до k, сдвигаемся на 1 каждый раз относительно предыдущего.

Упс... не подумал малость, написал для случая строго монотонной функции. Но для неубывающей такое же решение подойдет.

Хотя должно быть что-то проще. Склероз... болезнь молодых... все забыл:)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт май 30, 2006 12:52 pm 
Не в сети
Начинающий автор

Зарегистрирован: Сб авг 27, 2005 6:07 am
Сообщения: 335
Откуда: Аня
Честно говоря, слабо понимается как это решение можно применить к нестрого убывающим.

_________________
Я ёжик. Я упал в реку.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт май 30, 2006 1:03 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Сб сен 01, 2001 7:00 am
Сообщения: 1577
Откуда: Александр Фенстер
Да ровно так же, только начинать не от диагонали, а от постоянной f(x) = 0.

_________________
АФ


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: задача по логике.
СообщениеДобавлено: Вт май 30, 2006 1:43 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт сен 07, 2001 7:00 am
Сообщения: 2844
Откуда: Станислав Березнюк
bpa писал(а):
Хотя должно быть что-то проще. Склероз... болезнь молодых... все забыл:)


Hint: у невозрастающей функции из N в N область значений - конечна :)

_________________
Мордор жил, Мордор жив, Мордор будет жить!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: задача по логике.
СообщениеДобавлено: Вт май 30, 2006 2:14 pm 
Не в сети
Постоянный посетитель

Зарегистрирован: Вт янв 31, 2006 6:14 pm
Сообщения: 125
Откуда: Буров Павел
slb писал(а):
bpa писал(а):
Хотя должно быть что-то проще. Склероз... болезнь молодых... все забыл:)


Hint: у невозрастающей функции из N в N область значений - конечна :)

Вот блин;)
Кроме склероза еще и косоглазие наметилось:) Я-то пытался посчитать неубывающие функции, а они, падлы, невозрастающие:)
Тогда процедура подсчета сводится к вообще банальности:) Плюс, там в логике теорема была какая-то про счетное объединение счетных множеств.... а если и не было, то доказать, как два пальца об асфальт, тем же макаром, что и счетность $\mathbb{Q}$ доказывается.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт май 30, 2006 2:42 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт сен 02, 2005 12:59 pm
Сообщения: 1421
Откуда: Владимир
Пусть A - искомое множество
1) Строим на A эквивалентность по принципу: "f ~ g <=> f(x) = g(x) + c, где c - const", иначе говоря, объединяем все функции, получающиеся сдвигом вверх-вниз.
2) Каждый класс эквивалентности получается счетен (очевидно). Теперь, если мы докажем счетность фактор-множества, то все решено.
3) Проанализируем наше фактор-множество (назовем его X). Представителями классов можно взять все функции, которые некогда становятся равными нулю (очевидно, что в любом классе есть одна и только одна такая функция).
4) Построим на фактор-множестве X эквивалентность по правилу: классы эквивалентны, если их представители удовлетворяют условию: f(0) = g(0) и в ноль f и g попадают одновременно.
5) Мощность фактор-множества (назовем его Y) = N*N = N, так как каждый класс задается значением в нуле и точкой входа в ноль. Таким образом, осталось доказать не более чем счетность каждого класса.
6) Каждый класс по второй эквивалентности представляет из себя все функции, "зажатые в прямоугольник" заданного размера
/\ Y
|
|
|-------------------------------------------------|
| Все функции, графики которых............|
| проходят от верхнего левого................|
| до нижнего правого угла данного.........|
| прямоугольника являются....................|
| одним классом, характеризующимся.....|
| параметрами этого прямоугольника.......|
+--------------------------------------------------------------> X
O

(Этот прямоугольник вряд-ли будет выглядеть как прямоугольник, но надо считать, что все правые границы на одном уровне)

7) Осталось оценить мощность одного такого класса. Для каждого прямоугольника эта можность очевидно число конечное (из комбинаторики). А тогда мощность фактор-множества X равно |N|, так как X есть счетное объединение не более чем счетных множеств. А тогда можность нашего исходного множества тоже = |N|, как счетное объединение счетных классов.

_________________
А мы гуляли, пели, шли своей тропой. Мы открывали двери, хоть вход был запрещен. Мы шли в огонь.
Знай, паскуда, вольных, знай!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт май 30, 2006 3:41 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
Короткое решение: для любой функции f(x) множество всех x>0, для которых f(x-1) > f(x), конечно. Пусть это x1, ..., xn. Если мы сопоставим функции f набор
f(0), x1, f(x1), ..., xn, f (xn),
то получим инъективное отображение из множества всех функций в множество конечных послеждовательностей из N.

_________________
Не беги от снайпера - умрёшь усталым


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: задача по логике.
СообщениеДобавлено: Вт май 30, 2006 6:13 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Вт ноя 29, 2005 6:34 pm
Сообщения: 1498
bpa писал(а):
Я-то пытался посчитать неубывающие функции, а они, падлы, невозрастающие:)


А сколько тогда неубывающих функций ? (Какова мощность множества ?)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: задача по логике.
СообщениеДобавлено: Ср май 31, 2006 3:27 am 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Пт сен 02, 2005 12:59 pm
Сообщения: 1421
Откуда: Владимир
Akademovetz писал(а):
bpa писал(а):
Я-то пытался посчитать неубывающие функции, а они, падлы, невозрастающие:)


А сколько тогда неубывающих функций ? (Какова мощность множества ?)

Очевидно P(N)
1) Любая функция есть подмножество N*N - элемент P(N^2) = P(N) - оценка сверху
2) Инъекция из P(N) в {неубывающие функции} по принципу: каждое подмножество перечисляется функцией в порядке возрастания. Если подмножество конечное, то после перечисления функция остается константой.

_________________
А мы гуляли, пели, шли своей тропой. Мы открывали двери, хоть вход был запрещен. Мы шли в огонь.
Знай, паскуда, вольных, знай!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср май 31, 2006 12:38 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Группы 5133 и 5134 в семестре эти задачи в домашней работе решали. Потом разбирали у доски.

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

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: задача по логике.
СообщениеДобавлено: Чт июн 01, 2006 8:15 pm 
Не в сети
Частый гость

Зарегистрирован: Ср май 17, 2006 8:52 pm
Сообщения: 80
Откуда: Михаил
ConWor писал(а):
2) Инъекция из P(N) в {неубывающие функции} по принципу: каждое подмножество перечисляется функцией в порядке возрастания. Если подмножество конечное, то после перечисления функция остается константой.


Предлагаю другую инъекцию из всех функций в неубывающие.
f:N->N, g=F(f), F --- искомая инъекция
g(0)=а(0)
g(n+1)=g(n)+f(n+1)

монотонность g очевидна

инъективность F:

пусть g_1(n)=g_2(n) для всех n
тогда f_1(0)=g_1(0)=g_2(0)=f_2(0)
f_1(n+1)=g_1(n+1)-g_1(n)=g_2(n+1)-g_2(n)=f_2(n+1)
значит f_1(n)=f_2(n) для всех n.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Чт май 29, 2008 4:10 pm 
Не в сети
Редкий гость

Зарегистрирован: Чт май 29, 2008 4:06 pm
Сообщения: 1
Коба писал(а):
Зато есть где-то в этих группах один товарищ, который на зачете мощность множества ортогональных матриц два дня считал.

Задача сформулирована так: найти мощность множества ортогональных матриц nxn (n>1).
Вопрос: здесь имеется ввиду, что n фиксированное?


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.

Часовой пояс: UTC + 7 часов


Кто сейчас на конференции

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


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

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB