Д. Ушинского Элементы дискретной математики



страница9/14
Дата21.10.2016
Размер1,67 Mb.
1   ...   6   7   8   9   10   11   12   13   14

Рекуррентные соотношения.


  1. Подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом.

  2. Посылка бандероли стоит 18 рублей, а на почте имеются марки по 4, 6 и 10 рублей. Сколькими разными способами можно наклеить на бандероль марки, на нужную сумму?

  3. Имеется возможность передавать 4 разных сигнала А, Б, В, Г, причем их передача занимает соответственно Т1, Т2 Т3, Т4 (целые) единиц времени. Сколько различных сообщений может быть передано за время Т (тоже целое)?

  4. Абитуриент сдает в вуз 4 экзамена по 5-балльной системе и хочет набрать не менее 17 баллов. Сколькими способами он может это сделать.

  5. Сколькими способами можно разбить натуральное число М на К простых слагаемых, где способы разбиения, отличающиеся порядком слагаемых, считаются разными? Например при М=10 и К=2 ответом будет 3, так как 10=3+7=5+5=7+3.

  6. В лототроне имеются бочонки с номерами от 1 до К. Последовательно вынимают по одному бочонку, записывают его номер и считают сумму записанных чисел. Сколькими способами может получиться сумма М?

  7. В лототроне имеются бочонки с номерами от 1 до К. Последовательно вынимают по одному бочонку, записывают его номер и считают сумму записанных чисел, после записывания номера бочонок возвращается обратно в лототрон. Сколькими способами может получиться сумма М?

  8. На единственной улице в деревне стоят К домов с известными координатами. Требуется соединить их телефонными проводами минимальной суммарной длины так, чтобы житель каждого дома мог пообщаться хотя бы с одним жителем другого дома.

  9. В пригородном автобусе кондуктор следил за тем, чтобы все покупали билеты и отмечал, сколько билетов (ki,j) куплено с i–й остановки до j–й. По известной матрице ki,j нужно найти промежуток времени, когда в автобусе было максимальное количество пассажиров и чему оно равно.

  10. Прямоугольная таблица размерами МхК произвольно заполнена цифрами от 0 до 9. Найти путь из левого нижнего угла в правый верхний с максимальной суммой цифр в клетках пути (разрешается на каждом шаге переходить вверх или вправо).

  11. В романе N глав, причем р-я глава состоит из Ар страниц. Роман нужно разбить на К томов, причем главы должны идти по порядку и главы нельзя разбивать в разные тома. Какова может быть минимальная толщина самого толстого тома при этом?

  12. Для последовательности с f(1)=5 и f(2)=13, удовлетворяющей рекуррентному соотношению f(к+2)=5f(к+1)-6f(к), выписать формулу общего члена.

  13. Для последовательности с f(0)=6 и f(1)=24, удовлетворяющей рекуррентному соотношению f(к+2)=6f(к+1)-9f(к), выписать формулу общего члена.

  14. Для последовательности с f(0)=4, f(1)=-7 и f(2)=15, удовлетворяющей рекуррентному соотношению f(к+3)=-6f(к+2)-11f(k+1)-6f(к), выписать формулу общего члена.

  15. Найдите общее решение рекуррентных соотношений:

a) аn+2-7an+1+12an=0;

b) аn+2+3an+1-10an=0;

c) аn+2+9an=0 ;

d) аn+2+4an+1+4an=0.



  1. Найдите решение рекуррентного соотношения:

  1. аn+2-5an+1+6an=0, а1=1, а2=-7;

  2. аn+2-4an+1+4an=0, а1=2, а2=4.

Задачи по теории графов

Основные определения и примеры графов.


  1. В шахматном турнире по круговой системе участвуют семь студентов. Известно, что Ваня сыграл шесть партий, Толя – пять, Леша и Дима –по три, Семен и Илья – по две, Женя - одну. С кем сыграл Леша?

  2. Покажите, что следующие объекты можно рассматривать как графы:

  • вершины и ребра многогранника;

  • план лабиринта;

  • дружеские отношения в группе студентов;

  • генеалогическое дерево;

  • теннисный турнир;

  • страны на карте.

  1. На рисунке изображены молекулы этилена и бензола; через С и Н обозначены атомы углерода и водорода соответственно. Можно ли считать эти диаграммы графами? Если да, то что будет являться необходимым условием, для того чтобы граф представлял собой молекулу какого-либо углеводорода?




С


  1. Могут ли степени вершины в простом графе быть равны:

  • 8, 6, 5, 4, 4, 3, 2, 2;

  • 7, 7, 6, 5, 4, 2, 2, 1;

  • 6, 6, 6, 5, 5, 3, 2, 2.

  1. Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно.

  2. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

  3. Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?

  4. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими?

  5. В группе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этой группе), 11 - по 4 друга, а 10 - по 5 друзей?

  6. В некоторой стране 19 регионов. Может ли оказаться так, что у каждого региона 1, 5 или 9 соседних регионов?

  7. В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?

  8. Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

  9. В розыгрыше первенства по футболу участвуют 20 команд. Какое наименьшее число игр должно быть сыграно, чтобы среди любых трех команд нашлись две, уже сыгравшие между собой?

  10. Нарисуйте полный граф с n вершинами, если:

а) n = 2 б) n = 3 в) n = 5

  1. Какова степень каждой вершины полного графа, у которого n вершин?

  2. Спортивные соревнования проводятся по круговой системе. Это означает, что каждая пара игроков встречается между собой ровно один раз. В соревновании с двенадцатью участниками провели все встречи. Сколько было сыграно встреч?

  3. Может ли полный граф иметь 7, 8, 9, или 10 ребер?

  4. В некотором государстве система авиалиний устроена так, что любой город соединен авиалиниями не более чем с тремя другими и из любого города в любой другой можно перелететь, сделав не боле одной пересадки. Какое наибольшее число городов может быть в этом государстве?

  5. Какие из предложенных графов являются регулярными?




  1. В некоторой компании любые два знакомых не имеют общих знакомых, а любые два незнакомых имеют ровно двух общих знакомых. Докажите, что в этой компании все имеют одинаковое число знакомых.

  2. Известно, что в компании каждый человек знаком не менее, чем с половиной присутствующих. Докажите, что можно выбрать из компании четырех человек и рассадить их за круглым столом так, что при этом каждый будет сидеть рядом со своими знакомыми.

  3. Спортивные соревнования проводятся по круговой системе. Это означает, что каждая пара игроков встречается между собой ровно один раз. Докажите, что в любой момент времени найдутся хотя бы два игрока, проведшие одинаковое число встреч.

  4. Докажите, что в любом графе найдутся по крайней мере две вершины одинаковой степени

  5. В футбольном турнире 20 команд сыграли 8 туров: каждая команда сыграла с 8 разными командами. Докажите, что найдутся три команды, не сыгравшие между собой пока ни одного матча.

  6. Про некоторую компанию известно, что каждый человек знаком в ней ровно с шестью людьми и для любой группы из шести человек найдется член компании, знакомый с каждым из этой шестерки. Сколько человек в компании?

  7. Докажите, что среди любых шести человек есть либо трое попарно знакомых, либо трое попарно незнакомых.

  8. В международном фестивале участвовало несколько сотен делегатов из разных стран мира. Выяснилось, что из любых трех делегатов по крайней мере двое смогут объясниться между собой на каком-то языке. Докажите, что найдется тройка делегатов, в которой каждый может объясниться с каждым.



Поделитесь с Вашими друзьями:
1   ...   6   7   8   9   10   11   12   13   14


База данных защищена авторским правом ©grazit.ru 2019
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал