Главная страница
Навигация по странице:

  • Основы теории целых чисел 1. Деление с остатком Определение a , b  Z

  • Дискретная математика для фрт


    Скачать 1,28 Mb.
    НазваниеДискретная математика для фрт
    АнкорDiskretnaya_matematika_dlya_FRT_5.doc
    Дата13.01.2020
    Размер1,28 Mb.
    Формат файлаdoc
    Имя файлаDiskretnaya_matematika_dlya_FRT_5.doc
    ТипРешение
    #17239
    страница1 из 83

    Подборка по базе: Билет выч математика.docx.
      1   2   3   4   5   6   7   8   9   ...   83

    Дискретная математика для ФРТ
    Содержание.
    Основы теории целых чисел - 3 лекции,

    комбинаторика - 2 лекции,

    понятие о графах (дополнительный материал)-1 лекция,

    булевы функции - 3 лекции.
    И материалы для семинаров.
    Примечание: часть материала носит ознакомительный характер! Например, если теории для некоторой задачи не было в лекциях – значит, эта задача не входит в семинары, домашние задания и экзамен, а её условие даётся как дополнительный материал для самых любознательных. Конечно, готов кратко рассказать про решения таких задач, если спросите.
    Основы теории целых чисел
    1. Деление с остатком
    Определение
    a, bZ, b> 0.
    Поделить a на b с остатком – значит найти такие числа p и q, что a = bq + r, при этом 0≤r<b.
    Примеры:

    1. (Показать на доске) 25 = 46 + 1

    2. (Решить самостоятельно) -25 = -56 + 5
    Докажем единственность деления с остатком.
    В самом деле, если

    Тогда

    Если левая часть не равна 0, то её модуль не меньше b, поскольку умножаем b на ненулевое целое число. С другой стороны, оба остатка меньше b, поэтому модуль разности в правой части меньше b.

    Противоречие!

    Поэтому левая часть равна 0, и два представления совпали.
    Пример.
    Найдутся два целых числа, составленных из одних единиц, которые дают одинаковый остаток при делении на 37.
    Решение

    Возьмём 38 чисел, составленных из одних единиц. Поскольку остатков от деления на 37 всего 37, то хотя бы у двух чисел совпадут остатки.
    Задачи.
    1. Найти остаток от деления 22000 на 3.

    Решение



    Раскрыв скобки, получим много слагаемых, кратных 3, и одно слагаемое, равное 1. Поэтому остаток равен 1.
    Ответ: 1.
    2. а) доказать, что найдутся два числа, составленные из единиц, разность которых кратна 5007.

    б) доказать, что найдётся одно число, составленное из единиц и кратное 5007.
    Решение.
    а) Возьмём 5008 чисел, составленных из одних единиц. Поскольку остатков от деления на 5007 всего 5007, то хотя бы у двух чисел совпадут остатки, следовательно, их разность будет кратна 5007.

    б) Рассмотрим эту разность. В начале её некоторое количество единиц, затем одни нули.

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

    Поэтому число из единиц делится на 5007.
      1   2   3   4   5   6   7   8   9   ...   83


    написать администратору сайта