Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 4 ] 
Автор Сообщение
 Заголовок сообщения: Задачи по дискретной математике
СообщениеДобавлено: 23 июн 2014, 23:12 
Не в сети
Начинающий
Аватара пользователя
Зарегистрирован:
22 июн 2014, 19:15
Сообщений: 14
Cпасибо сказано: 8
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
Здравствуйте.

Готовлюсь к экзамену по дискретной математике.
Объясните, как решить несколько задач, пожалуйста :

1. С помощью комбинаторных размышлений доказать, что количество разбиений числа n на попарно различные слагаемые = количеству разбиений числа n на нечётные слагаемые.

2. Доказать, что для счётного универсума множество всех подмножеств с конечным дополнением является счётным.

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

4. Доказать, что множество всех бесконечных подмножеств конечного множества является континуальным.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задачи по дискретной математике
СообщениеДобавлено: 24 июн 2014, 02:20 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
1. Доказательство взято из Lectures on Integer Partitions by Herbert S. Wilf (документ PDF).

Построим биекцию, которая разбиения на попарно различные слагаемые отображает в разбиения на нечетные слагаемые. Пусть [math]n=d_1+\dots+d_k[/math], где все [math]d_i[/math] различны. Каждое [math]d_i[/math] представляется в виде [math]2^{k_i}m_i[/math], где [math]m_i[/math] нечетное число. Сгруппируем слагаемые с одинаковыми [math]m_i[/math]:

[math]\begin{align*} n&= (2^{\alpha_1}+2^{\alpha_2}+\dots)\cdot1+ (2^{\beta_1}+2^{\beta_2}+\dots)\cdot 3+ (2^{\gamma_1}+2^{\gamma_2}+\dots)\cdot5+\dots\\ &=\mu_1\cdot1+\mu_3\cdot2 +\mu_5\cdot5+\dots\end{align*}[/math]

Таким образом, [math]n[/math] есть сумма [math]\mu_1[/math] единиц, [math]\mu_3[/math] троек и т.д.

Осталось показать, что это отображение инъективно и сюръективно. Сюръективность: пусть дано разбиение [math]n[/math] на нечетные слагаемые

[math]n=\mu_1\cdot1+\mu_3\cdot2 +\mu_5\cdot5+\dots[/math].

Напишем каждое [math]\mu_i[/math] (здесь [math]i[/math] нечетно) в двоичной системе: [math]\mu_i=2^{\rho_1}+2^{\rho_2}+\dots[/math], где все [math]\rho_j[/math] различны. Из них получатся слагаемые [math]2^{\rho_1}i+2^{\rho_2}i+\dots[/math] Они отличаются как между собой, так и от слагаемых, соответствующих другим [math]\mu_{i'}[/math]. То есть прообраз действительно есть разбиение на различные слагаемые. Инъективность оставлю в качестве задачи.

Есть более простое доказательство с помощью производящих функций.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю 3D Homer "Спасибо" сказали:
Cocoa Lapin
 Заголовок сообщения: Re: Задачи по дискретной математике
СообщениеДобавлено: 24 июн 2014, 23:15 
Не в сети
Начинающий
Аватара пользователя
Зарегистрирован:
22 июн 2014, 19:15
Сообщений: 14
Cпасибо сказано: 8
Спасибо получено:
1 раз в 1 сообщении
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
Еще несколько задач, с которыми я не могу разобраться...

5. На карусели по кругу размещено n разных детей. Сколькими способами можно переставить детей так, чтоб перед каждым был размещен другой ребёнок, чем прежде ?

6. Сколькими способами на трехугольной шахматной доске со стороной q можно расставить k тур, чтоб ни одна тура не била другую? ( с аналитическим ответом )

7. Какую мощность имеет множество всех замкнутых подмножеств множества действительных чисел R ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задачи по дискретной математике
СообщениеДобавлено: 24 июн 2014, 23:29 
Не в сети
Последняя инстанция
Зарегистрирован:
06 июн 2013, 16:17
Сообщений: 2590
Cпасибо сказано: 104
Спасибо получено:
746 раз в 701 сообщениях
Очков репутации: 158

Добавить очки репутацииУменьшить очки репутации
Подсказка для № 7 есть в этой теме. Насчет остальных, я думаю, лучше начать новую тему. У вас больше шансов получить ответ, потому что люди с большей вероятностью просматривают темы без ответов, чем темы, уже содержащие несколько сообщений.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю 3D Homer "Спасибо" сказали:
Cocoa Lapin
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 4 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Задачи по дискретной математике

в форуме Дискретная математика, Теория множеств и Логика

Lucky721

7

782

07 июн 2014, 12:51

Задачи по дискретной математике

в форуме Дискретная математика, Теория множеств и Логика

Glog

1

211

26 дек 2019, 19:08

Решить задачи по дискретной математике

в форуме Дискретная математика, Теория множеств и Логика

Lorf12

1

125

29 июн 2022, 00:11

Задания по дискретной математике

в форуме Дискретная математика, Теория множеств и Логика

lemni

1

383

24 авг 2017, 20:48

Задание по дискретной математике

в форуме Дискретная математика, Теория множеств и Логика

AB96

1

383

27 янв 2015, 21:46

Учебники по дискретной математике

в форуме Литература и Онлайн-ресурсы по математике

sfanter

6

827

11 ноя 2015, 19:29

Экзамен по дискретной математике

в форуме Дискретная математика, Теория множеств и Логика

Alamarius

1

119

18 июн 2022, 22:30

Задача по дискретной математике

в форуме Дискретная математика, Теория множеств и Логика

gfsfjiejksjdflksdf

1

111

24 дек 2023, 17:15

Где скачать книжку по дискретной математике?

в форуме Дискретная математика, Теория множеств и Логика

sfanter

2

233

20 май 2016, 20:49

Задача по дискретной математике (1 курс

в форуме Дискретная математика, Теория множеств и Логика

atdqueeng13

7

618

02 ноя 2020, 21:12


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved