Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Февраль 2010   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Дискретная математика


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный платный хостинг на базе Windows 2008

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Чемпионы рейтинга экспертов в этой рассылке

Гордиенко Андрей Владимирович
Статус: Профессор
Рейтинг: 4672
∙ повысить рейтинг » 		Гаряка Асмик
Статус: Бакалавр
Рейтинг: 2286
∙ повысить рейтинг » 		_Ayl_
Статус: Студент
Рейтинг: 1621
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Дискретная математика

Номер выпуска:170
Дата выхода:23.02.2010, 17:30
Администратор рассылки:Alexey G. Gladenyuk, Управляющий
Подписчиков / экспертов:104 / 47
Вопросов / ответов:1 / 3

Вопрос № 176767: Здравствуйте, эксперты. Как решить эти 2 задачи: Задача 1: Выбирается 38 четных положительных чисел меньше 1000. Доказать, что найдется 2 числа таких, что их разница будет максимум 26. Задача 2: ...

Вопрос № 176767:

Здравствуйте, эксперты.

Как решить эти 2 задачи:

Задача 1:

Выбирается 38 четных положительных чисел меньше 1000.
Доказать, что найдется 2 числа таких, что их разница будет
максимум 26.

Задача 2:

В классе учатся только мальчики. Известно, что:

* а мальчиков любят шахматы
* b - любят футбол
* c - езду на велоcипеде
* d - езду на лошадях
* x - кол-во мальчиков, играющих и в футбол, и в шахматы
* y мальчиков любят шахматы и велосипед
* z - шахматы и езду на лошадях
* u - футбол и велосипед
* v - футбол и езду на лошадях
* w - кол-во мальчиков, которым нравится езда на велосипеде и
езда на лошади.

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

2.2 Докажите, что основываясь на исходных данных, мы можем
сделать вывод, что количество мальчиков в классе меньше, ч ем
a + b + c + d и больше, чем a + b + c + d - x - y - z - u - v - w.

Заранее спасибо.

Отправлен: 18.02.2010, 17:17
Вопрос задал: Иванов Андрей Владимирович, 6-й класс
Всего ответов: 3
Страница вопроса »

Отвечает Galinab222, 5-й класс :
Здравствуйте, Иванов Андрей Владимирович.
первую задачу можно решить "от противного". Пусть нет двух чисел, разница между которыми не больше 26, т.е. разница между всеми числами a>=27. Упорядочим числа по возрастанию Первое число x1>=2. Тогда второе x2>=x1+27>=2+27, третье x3>=x2+27>=x1+2*27>=2+2*27 и т.д. Последнее x38>=x1+37*27>=2+37*27=1001, что противоречит условию задачи. Следовательно, предположение, что нет двух чисел, разница между которыми не больше 26, не верно.
Во второй задаче - 2.1. - на какой вопрос ответить нельзя?

Ответ отправил: Galinab222, 5-й класс
Ответ отправлен: 18.02.2010, 17:29
Номер ответа: 259560

Оценка ответа: 5

Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 259560 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Отвечает Гаряка Асмик, Бакалавр :
    Здравствуйте, Иванов Андрей Владимирович.

    Предположим обратное, то есть разница всех чисел больше 27. Отсортируем их по порядку.
    a1>=1, a2>1+27...... a38>1+27*37=1000
    А по условию все числа меньше 1000. Противоречие.

    2. a+b+c+d - Общее количество увлечений у мальчиков. Так как некоторые мальчики имеют больше одного увлечения, это число больше числа мальчиков.
    a + b + c + d - x - y - z - u - v - w.- из общей суммы вычитается число парных увлечений. Но есть мальчики, у которых 3 увлечения и больше. Тогда их вычли дважды.
    -----
    Я ни от чего, ни от кого не завишу.

    Ответ отправил: Гаряка Асмик, Бакалавр
    Ответ отправлен: 18.02.2010, 17:31
    Номер ответа: 259561

    Оценка ответа: 5

    Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 259561 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Отвечает _Ayl_, Студент :
    Здравствуйте, Иванов Андрей Владимирович.

    1. Допустим, что для любых двух чисел из выборки (числа предполагаем различными, т.к. если есть равные, то их разность будет 0 < 26) разность между ними больше 26.
    Т.к. числа четные, то и разность четная, т.е. минимально возможная разность, большая 26, равна 28.
    Проверим, можем ли мы набрать 38 чисел с такой разностью:
    Первое число 2 (наименьшее из четных положительных). Следующее - 2+28=30. Далее: 58, 86 и т.д. 36-е равно 982 - и все. Больше чисел не набрать.
    А надо еще 2. Т.е. мы не можем набрать 38 чисел с разностью не меньше 28.
    Покажем, что мы можем выбрать 38 чисел с разностью 26:
    2, 28, 54, 80, 106, 132, 158, 184, 210, 236, 262, 288, 314, 340, 366, 392, 418, 444, 470, 496, 522, 548, 574, 600, 626, 652, 678, 704, 730, 756, 782, 808, 834, 860, 886, 912, 938, 964.

    2.
    Возьмем 16 мальчиков: 8 любят футбол, 8 - шахматы, 8 - велосипед, 8 - лошадей. 4 - футбол и шахматы, 4 - футбол и велосипед, 4 - футбол и лошадей, 4 - шахматы и велосипед, 4 - шахматы и лошадей, 4 - велосипед и лошадей.
    Это все данные по задачи.
    Добавлю еще, что по 2 мальчика любят по 3 вида в разных сочетаниях (Ф+Ш+В, Ф+Ш+Л, Ф+В+Л, Ш+В+Л) и один - все 4 вида. Кроме этого один лентяй ничего не любит.

    А теперь уберем из класса вот этого лентяя. В результате состояние остальных останется ровно таким же, а общее число мальчиков в классе станет 15.

    Соответственно, по исходным данным задачи мы не можем определить количество мальчиков в классе (видимо, это и есть неуказанный вопрос) однозначно.
    Более того, в данном случае и утверждение в п.2.2. неверно, т.к. мы можем добавить в этот класс любое число лентяев, в результате чего их станет гарантировано больше, нежели занимающихся спортом.

    Поэтому для определения общего числа мальчиков нам нужно знать количество лентяев.

    Предположим, что у нас лентяев нет.
    При этом все равно однозначно определить число мальчиков нел ьзя.
    Рассмотрим вот такие 2 класса:
    К1: ШФ, ШВ, ШЛ, ФВ, ФЛ, ВЛ - всего 6 мальчиков, каждый занимается 2-мя видами. Тогда каждым видом занимается по 3 мальчика, и по 1 мальчику каждой парой видов.
    К2: ШФВЛ, 2Ш, 2Ф, 2В, 2Л - всего 9 мальчиков, из которых один универсал (все виды) и по 2 мальчика-специалиста на каждый вид, занимающихся только им. В результате мы также имеем по 3 мальчика на каждый вид и одного мальчика на каждую пару (универсал считается для каждой пары).

    Соответственно, мы никогда не сможем по исходным данным выбрать между этими двумя классами.

    Что же нужно для определения числа мальчиков.
    Рассмотрим сначала только тех, кто занимается шахматами или футболом (Ш и Ф).
    Тогда этих мальчиков всего будет Ш+Ф-ШФ (сумма тех, кто занимается этими видами минус те, кто занимается обоими видами, т.к. они были учтены дважды).
    Итак, обозначим число шахматисто-футболистов как А (А = Ш+Ф-ШФ).
    Добавим к ним велосипедистов (В). Теперь число ма льчиков станет равно А+В-АВ = Ш+Ф-ШФ+В-(Ш+Ф-ШФ)В = Ш+Ф-ШФ+В-ШВ-ФВ+ШФВ.
    Данная формула обозначает, что мы считаем всех по каждому виду, не учитываем тех, кто занимается парой видов (т.к. они учитываются дважды), но добавляем тех, кто занимается всеми тремя видами (т.к. мы их лишний раз выкинули при учете пар).
    Ну и по аналогии, добавляя лошадников (Л) получаем, что общее число мальчиков есть (обохначим Ш+Ф-ШФ+В-ШВ-ФВ+ШФВ как Б) Б+Л-БЛ = Ш+Ф-ШФ+В-ШВ-ФВ+ШФВ+Л-(Ш+Ф-ШФ+В-ШВ-ФВ+ШФВ)Л = Ш+Ф-ШФ+В-ШВ-ФВ+ШФВ+Л-ШЛ-ФЛ+ШФЛ-ВЛ+ШВЛ+ФВЛ-ШФВЛ. Опять же, из общей суммы убираем тех, кто занимается двумя видами, добавляем тех, кто занимается тремя видами и убираем универсалов-четырехвидовиков.

    Далее аналогично: суммируются все те, кто занимается нечетным числом видов и вычитаются те, кто занимается четным числом.

    Соответственно, в п.2.1 для вычисления числа мальчиков должны быть дополнительно заданы количества тех, кто занимается тремя видами и тех, кто занимается всеми четы рьмя.
    По п.2.2
    Т.к. пересечение не может быть больше минимального из множеств, то:
    Ш+Ф+В+Л не меньше общего числа мальчиков, т.к. лентяев нет.
    Т.к. сумма тех, кто занимается тремя видами, не меньше тех, кто занимается 4-мя (последнее суть подмножество объединения первых), то их разность не меньше 0. А т.к. эту разность нужно прибавить к заданному выражению, то общее число мальчиков будет не меньше указанного выражения.

    Ответ отправил: _Ayl_, Студент
    Ответ отправлен: 18.02.2010, 18:52
    Номер ответа: 259564

    Вам помог ответ? Пожалуйста, поблагодарите эксперта за это!
    Как сказать этому эксперту "спасибо"?
  • Отправить SMS #thank 259564 на номер 1151 (Россия) | Еще номера »
  • Отправить WebMoney:

    • Оценить выпуск »
    Нам очень важно Ваше мнение об этом выпуске рассылки!

    Задать вопрос экспертам этой рассылки »

    Скажите "спасибо" эксперту, который помог Вам!

    Отправьте СМС-сообщение с тестом #thank НОМЕР_ОТВЕТА
    на короткий номер 1151 (Россия)
    Номер ответа и конкретный текст СМС указан внизу каждого ответа.

    Полный список номеров »

    * Стоимость одного СМС-сообщения от 7.15 руб. и зависит от оператора сотовой связи. (полный список тарифов)
    ** При ошибочном вводе номера ответа или текста #thank услуга считается оказанной, денежные средства не возвращаются.
    *** Сумма выплаты эксперту-автору ответа расчитывается из суммы перечислений на портал от биллинговой компании.

    © 2001-2010, Портал RFpro.ru, Россия
    Авторское право: ООО "Мастер-Эксперт Про"
    Автор: Калашников О.А. | Программирование: Гладенюк А.Г.
    Хостинг: Компания "Московский хостер"
    Версия системы: 2010.6.14 от 03.02.2010
    В избранное