Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

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

Лучшие эксперты по данной тематике

Асмик Гаряка Статус: Советник Рейтинг: 10653 ∙ повысить рейтинг »

Коцюрбенко Алексей aka Жерар Статус: Советник Рейтинг: 3992 ∙ повысить рейтинг »

CradleA Статус: Бакалавр Рейтинг: 2059 ∙ повысить рейтинг »

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

Номер выпуска:	321
Дата выхода:	20.12.2013, 22:30
Администратор рассылки:	Асмик Гаряка (Советник)
Подписчиков / экспертов:	19 / 30
Вопросов / ответов:	3 / 8

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

Консультация # 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
Вопрос задал: Иванов Андрей Владимирович
Всего ответов: 3
Страница онлайн-консультации »

Консультирует Galinab222:

Здравствуйте, Иванов Андрей Владимирович.
первую задачу можно решить "от противного". Пусть нет двух чисел, разница между которыми не больше 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 Дата отправки: 18.02.2010, 17:29 5 нет комментария ----- Дата оценки: 18.02.2010, 19:32

Рейтинг ответа: +1 поблагодарить эксперта

Консультирует Асмик Гаряка (Советник):

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

Предположим обратное, то есть разница всех чисел больше 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 5 нет комментария ----- Дата оценки: 18.02.2010, 19:32

Рейтинг ответа: +1 поблагодарить эксперта

Консультирует Абаянцев Юрий Леонидович aka 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. А т.к. эту разность нужно прибавить к заданному выражению, то общее число мальчиков будет не меньше указанного выражения.

Консультировал: Абаянцев Юрий Леонидович aka Ayl (Профессионал) Дата отправки: 18.02.2010, 18:52

Рейтинг ответа: +1 поблагодарить эксперта

Консультация # 174679:

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

Помогите доказать выводимость формулы в ИВ через аксиомы.

(A→B)→((¬А→С)→(¬В→С))

Аксиомы ИВ:
A₁: (A→(В→A))
A₂: ((A→(В→C))→((A→В)→(A→C)))
A₃: ((¬В→¬A)→((¬В→A)→В))

Спасибо!

Дата отправки: 29.11.2009, 17:54
Вопрос задал: Степан Иванов
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Kvitenol:

Здравствуйте, Степан Иванов.
Математическая логика, учебник
Учебник, часть 3
3. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ
http://djvu-student.narod.ru/02-matematicheskaya-logika/metodichka/metoda_matlogika_i_teor_algoritm_g3.html

Лекция 4: АКСИОМАТИЧЕСКАЯ СИСТЕМА ЛОГИЧЕСКОГО ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
http://arent.blog.net.ua/2009/11/26/lektsiya-4/

О.А. Солодухин. Учебник по логике
http://sophia.nau.edu.ua/library/textbook/log_sol.html

Математическая логика
Методические указания по курсу лекций
Вуз Санкт-Петербургский государственный электротехнический университет
http://www.studfiles.ru/dir/cat14/subj266/file3194/view4507/page2.html

ФУНКЦИИ АЛГЕБРЫ ЛОГИКИ_ОПРЕДЕЛЕНИЕ_СПОСОБЫ ЗАДАНИЯ_ПРИМЕРЫ
http://files.powt.ru/incoming/roman/tmp/%D0%94%D0%B8%D1%81%D0%BA%D1%80%D0%B5%D1%82%D0%BD%D0%B0%D1%8F%20%D0%9C%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0/%D0%94%D0%98%D0%A1%D0%9A%D0%A0%D0%95~1/ALL.TXT

Консультировал: Kvitenol Дата отправки: 04.12.2009, 10:11

Рейтинг ответа: 0 поблагодарить эксперта

Консультация # 187278:

Здравствуйте! Прошу помощи в следующем вопросе: распишите пожалуйста ход решения чтобы понять

1. Найти полные системы наименьших неотрицательных и абсолютно наименьших вычетов по модулям 6,11.
2. Найти две последние цифры числа 17^61.
3. Разложить рациональное число 153/24 в цепную (непрерывную дробь), составить таблицу ее подходящих дробей, найти подходящую дробь второго порядка.
4. Решить сравнения:
2х ≡3(mod5)
21х≡35(mod77)
5. Найти количество целых положительных чисел, не превосходящих 300 и не делящихся ни на одно из простых чисел 2, 13, 19.

Дата отправки: 13.04.2013, 17:31
Вопрос задал: Посетитель - 356695 (Посетитель)
Всего ответов: 4
Страница онлайн-консультации »

Консультирует Александр Чекменёв (Академик):

Здравствуйте, Посетитель - 356695!

4.
2x = 3 mod 5
Можно сказать, что надо найти такие целые неотрицательные x не больше 5, что
2x = 3 + 5k,
где k тоже целое.
Заметим, что так как 2 и 5 взаимно просты, интересующее нас решение, если оно есть, единственно. Действительно, пусть x' и k' -- другое решение. Тогда
3 = 2x - 5k = 2x' - 5k',
2(x - x') = 5(k - k').
Значит x-x' кратно 5, а значит x отличается от x' на кратное 5. Т.е. эти решения одинаковы, по модулю 5.
Итак, показано, что решение, если есть, единственно. Но легко видеть, что x=4 -- решение.

21х = 35 mod 77
Снова -- ищем 0<=x<77 такое, что
21x = 35 + 77k.
Поделим на 7.
3x = 5 + 11k.
3 и 11 взаимно просты, поэтому решение, если есть, единственно. А x=9 -- решение.

Консультировал: Александр Чекменёв (Академик) Дата отправки: 13.04.2013, 18:42 5 нет комментария ----- Дата оценки: 15.04.2013, 07:51

Рейтинг ответа: 0 поблагодарить эксперта

Консультирует асяня (Профессор):

Здравствуйте, Посетитель - 356695!
1.
Перечислим все возможные классы вычетов по модулю 6:
[0]={...-12, -6, 0, 6, 12,...} (это числа при делении на 6 дающие остаток 0),
[1]={...-11, -5, 1, 7, 13,...} (это числа при делении на 6 дающие остаток 1),
[2]={...-10, -4, 2, 8, 14,...} (это числа при делении на 6 дающие остаток 2),
[3]={...-9, -3, 3, 9, 15,...} (это числа при делении на 6 дающие остаток 3),
[4]={...-8, -2, 4, 10, 16,...} (это числа при делении на 6 дающие остаток 4),
[5]={...-7, -1, 5, 11, 18,...} (это числа при делении на 6 дающие остаток 5).
Полные системы наименьших неотрицательных и абсолютно наименьших вычетов составляются следующим образом: из каждого класса вычетов берется соответственно наименьшее неотрицательное число и наименьшее по модулю число.
Полная система наименьших неотрицательных вычетов по модулю 6 имеет вид: {0, 1, 2, 3, 4, 5}.
Полная система абсолютно наименьших вычетов по модулю 6 имеет вид: {-2, -1 , 0, 1, 2, 3}.

Теперь для модуля 11:
полная система наименьших неотрицательных вычетов по модулю 11: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10},
полная система абсолютно наименьших вычетов по модулю 11: {-5,-4, -3, -2, -1, 0, 1, 2, 3, 4, 5}.

Консультировал: асяня (Профессор) Дата отправки: 13.04.2013, 20:00 5 нет комментария ----- Дата оценки: 15.04.2013, 07:51

Рейтинг ответа: 0 поблагодарить эксперта

Консультирует SFResid (Модератор):

Здравствуйте, Посетитель - 356695!
№ 2. Ответ: Mod(17⁶¹,100) = 17
Доказательство:
17⁶¹ = (7 + 10)⁶¹(бином Ньютона), или:
17⁶¹ = 7⁶¹ + 61*7⁶⁰*10 + ∑₃⁶¹B_k*7^(62-k)*10^(k-1) = 7⁶¹ + 61*7⁶⁰*10 + 100*∑₃⁶¹B_k*7^(62-k)*10^(k-3) (1), где B_k - "биномиальный коэффициент" k-го члена ряда; отсюда Mod(17⁶¹,100) = Mod((17⁶¹ + 61*7⁶⁰*10),100) (2). С другой стороны, справедлива закономерность: Mod(7^4*m,100) = 1 (3), Mod(7^(4*m+1,100) = 7 (3а), где m - произвольное целое. Подставив (3) и (3а), при m = 15 в (2), получаем: Mod(17⁶¹,100) = 17, ЧТД.

Консультировал: SFResid (Модератор) Дата отправки: 14.04.2013, 23:59 5 нет комментария ----- Дата оценки: 15.04.2013, 07:50

Рейтинг ответа: 0 поблагодарить эксперта

Консультирует Гордиенко Андрей Владимирович (Модератор):

Здравствуйте, Посетитель - 356695!

5. В задаче рассматривается множество натуральных чисел от 1 до 300. Это множество состоит из 300 элементов. Среди них насчитывается 150 нечётных чисел (они не делятся на 2). Среди нечётных чисел, в свою очередь, насчитывается 12 чисел, которые делятся на 13, и 8 чисел, которые делятся на 19. Одно число (13 * 19 = 247) делится и на 13, и на 19. Значит, насчитывается 150 - 12 - 8 + 1 = 131 число, которое не делится ни на 2, ни на 13, ни на 19.

Наверное, наибольшие сложности вызывает подсчёт количества чисел, кратных тому или иному числу. Например, количество чисел, которые делятся на 13, можно найти так: наименьшее такое число равно 13, а наибольшее - 299; так как 13 : 13 = 1, а 299 : 13 = 23, то получаем 12 нечётных чисел (1, 3, 5, ..., 23), являющихся множителями числа 13 и дающих нечётные числа, которые делятся на 13...

С уважением.

Консультировал: Гордиенко Андрей Владимирович (Модератор) Дата отправки: 15.04.2013, 08:13 5 нет комментария ----- Дата оценки: 15.04.2013, 08:22

Рейтинг ответа: 0 поблагодарить эксперта

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль