Как решать логические и математические задачи
Решение задач на логику — отличная гимнастика для ума детей и взрослых на каждый день. На ЛогикЛайк более 3500 заданий с ответами и пояснениями, полноценный учебный комплекс для развития логики и способностей к математике.
Решаем логические задачи
Чтобы научиться решать типовые логические задачи, простые и нестандартные математические задачи, важно знать основные приемы и методы их решения. Ведь решить одну и ту же задачу и прийти к правильному ответу во многих случаях можно разными способами.
Знание и понимание различных методов решения поможет определить, какой способ подойдет лучше в каждом конкретном случае, чтобы выбрать наиболее быстрый и простой путь получения ответа.
К «классическим» логическим задачам относятся текстовые задачи, цель решения которых состоит в распознавании объектов или расположении их в определенном порядке в соответствии с заданными условиями.
Более сложными и увлекательными типами заданий являются задачи, в которых отдельные утверждения являются истинными, а другие ложными. Задачи на перемещение, перекладывание, взвешивание, переливание — самые яркие примеры широкого ряда нестандартных задач на логику.
Основные методы решения логических задач
- метод рассуждений;
- с помощью таблиц истинности;
- метод блок-схем;
- средствами алгебры логики (алгебры высказываний);
- графический (в том числе, «дерево логических условий», метод кругов Эйлера);
- метод математического бильярда.
Попробуйте занятия на сайте ЛогикЛайк!
Выберите возраст ученика для старта
15+ для себя
На платформе LogicLike.com 5500 логических заданий с ответами: ребусы, задачи, вопросы и головоломки.
Давайте рассмотрим подробнее с примерами три популярных способа решения логических задач, которые мы рекомендуем использовать в начальной школе (детям 6-12 лет):
- метод последовательных рассуждений;
- разновидность метода рассуждений — «с конца»;
- табличный способ.
Метод последовательных рассуждений
Самый простой способ решения несложных задач заключается в последовательных рассуждениях с использованием всех известных условий. Выводы из утверждений, являющихся условиями задачи, постепенно приводят к ответу на поставленный вопрос.
На столе лежат Голубой , Зеленый , Коричневый и Оранжевый карандаши.
Третьим лежит карандаш, в имени которого больше всего букв. Голубой карандаш лежит между Коричневым и Оранжевым .
Разложи карандаши в описанном порядке.
Рассуждаем. Последовательно используем условия задачи для формулирования выводов о позиции, на которой должен лежать каждый следующий карандаш.
- Больше всего букв в слове «коричневый», значит, он лежит третьим.
- Известно, что голубой карандаш лежит между коричневым и оранжевым. Справа от коричневого есть только одна позиция, значит, расположить голубой между коричневым и другим карандашом возможно только слева от коричневого.
- Следующий вывод на основе предыдущего: голубой карандаш лежит на второй позиции, а оранжевый — на первой.
- Для зеленого карандаша осталась последняя позиция — он лежит четвертым.
Метод «с конца»
Такой способ решения является разновидностью метода рассуждений и отлично подходит для задач, в которых нам известен результат совершения определенных действий, а вопрос состоит в восстановлении первоначальной картины.
Бабушка испекла для троих внуков рогалики и оставила их на столе. Коля забежал перекусить первым. Сосчитал все рогалики, взял свою долю и убежал.
Аня зашла в дом позже. Она не знала, что Коля уже взял рогалики, сосчитала их и, разделив на троих, взяла свою долю.
Третьим пришел Гена, который тоже разделил остаток выпечки на троих и взял свою долю.
На столе осталось 8 рогаликов.
Сколько рогаликов из восьми оставшихся должен съесть каждый, чтобы в результате все съели поровну?
Начинаем рассуждение «с конца».
Гена оставил для Ани и Коли 8 рогаликов (каждому по 4). Получается, и сам он съел 4 рогалика: 8 + 4 = 12.
Аня оставила для братьев 12 рогаликов (каждому по 6). Значит, и сама она съела 6 штук: 12 + 6 = 18.
Коля оставил ребятам 18 рогаликов. Значит, сам съел 9: 18 + 9 = 27.
Бабушка положила на стол 27 рогаликов, рассчитывая, что каждому достанется по 9 штук. Поскольку Коля уже съел свою долю, Аня должна съесть 3, а Гена — 5 рогаликов.
Как ЛогикЛайк может помочь родителям?
Выберите основную цель занятий
Решение логических задач с помощью таблиц истинности
Суть метода состоит в фиксации условий задачи и полученных результатов рассуждений в специально составленных под задачу таблицах. В зависимости от того, является высказывание истинным или ложным, соответствующие ячейки таблицы заполняются знаками «+» и «-» либо «1» и «0».
Три спортсмена ( красный , синий и зеленый ) играли в баскетбол.
Когда мяч оказался в корзине, красный воскликнул: «Мяч забросил синий».
Синий возразил: «Мяч забросил зеленый».
Зеленый сказал: «Я не забрасывал».
Кто забросил мяч, если только один из троих сказал неправду?
Сначала таблицу составляют: слева записывают все утверждения, которые содержатся в условии, а сверху — возможные варианты ответа.
Затем таблицу последовательно заполняют: верные утверждения отмечают знаком «+», а ложные утверждения — знаком «-«.
Рассмотрим первый вариант ответа («мяч забросил красный «), проанализируем утверждения, записанные слева, и заполним первый столбик.
Исходя из нашего предположения («мяч забросил красный «), утверждение «мяч забросил синий» — ложь. Ставим в ячейке «-«.
Утверждение «мяч забросил зеленый» также ложь. Заполняем ячейку знаком «-«.
Утверждение зеленого «Я не забрасывал» – истина. Ставим в ячейке «+».
Рассмотрим второй вариант ответа (предположим, что мяч забросил зеленый ) и заполним второй столбик.
Утверждение «мяч забросил Синий» — ложь. Ставим в ячейке «-«.
Утверждение «мяч забросил зеленый « — истина. Заполняем ячейку знаком «+».
Утверждение зеленого «Я не забрасывал» – ложь. Ставим в ячейке «-«.
И, наконец, третий вариант: предположим, что «мяч забросил синий «.
Тогда утверждение «мяч забросил синий « — истина. Ставим в ячейке «+».
Утверждение «мяч забросил зеленый» — ложь. Заполняем ячейку знаком «-«. Утверждение зеленого «Я не забрасывал» – истина. Ставим в ячейке «+».
Так как по условию лишь один из троих ребят сказал неправду, в заполненной таблице выбираем такой вариант ответа, где будет только одно ложное утверждение (в столбце один знак «-«). Подходит третий столбец.
Значит, правильный ответ – мяч забросил синий.
Метод блок-схем
Метод блок-схем считается оптимальным вариантом для решения задач на взвешивание и на переливание жидкостей. Альтернативный способ решения этого типа задач — метод перебора вариантов — не всегда является оптимальным, да и назвать его системным довольно сложно.
Порядок решения задач по методу блок-схем выглядит следующим образом:
- графически (блок-схемой) описываем последовательность выполнения операций;
- определяем порядок их выполнения;
- в таблице фиксируем текущие состояния.
Подробнее об этом и других способах решения логических задач с примерами и описанием хода решения мы рассказываем в полном Курсе ЛогикЛайк по развитию логического мышления.
Отгадывайте самые интересные загадки на логику, собранные специально для постоянных читателей нашего блога и учеников LogicLike, решайте логические задачи онлайн вместе с тысячами детей и взрослых!
Подключайтесь к ЛогикЛайк!
Учим детей 5-12 лет решать любые логические и математические задачи. Более 3500 занимательных заданий с ответами и пояснениями.
3 особенности чисел в Python, о которых вы, возможно, не знали
Если вы писали код на Python, то весьма высока вероятность того, что вы, хотя бы в одной из своих программ, пользовались числами. Например, это могли быть целые числа для указания индекса значения в списке, или числа с плавающей точкой, представляющие суммы в некоей валюте.
Но числа в Python — это гораздо больше, чем, собственно, их числовые значения. Поговорим о трёх особенностях чисел в Python, с которыми вы, возможно, не знакомы.
№1: у чисел есть методы
В Python практически всё — это объект. Один из первых объектов, о котором узнаёт тот, кто начинает изучать Python — это str , используемый для представления строк. Возможно, вы сталкивались с использованием методов строк, вроде .lower() , который возвращает новую строку, все символы которой приведены к нижнему регистру:
>>> "HELLO".lower() 'hello'Числа в Python тоже, как и строки, являются объектами. У них тоже есть методы. Например, целое число можно преобразовать в байтовую строку с помощью метода .to_bytes() :
>>> n = 255 >>> n.to_bytes(length=2, byteorder="big") b'\x00\xff'Параметр length указывает на количество байт, которые нужно использовать при составлении байтовой строки, а параметр byteorder определяет порядок байт. Например, установка параметра byteorder в значение «big» приводит к возврату байтовой строки, в которой старший байт расположен первым, а установка этого параметра в значение «little» приводит к тому, что первым идёт младший байт.
255 — это максимальное значение, которое может принимать 8-битное целое число. Поэтому в нашем случае при вызове метода .to_bytes() можно без проблем воспользоваться параметром length=1 :
>>> n.to_bytes(length=1, byteorder="big") b'\xff'А вот если записать в n число 256 и вызвать для него . to_bytes() с параметром length=1 , будет выдана ошибка OverflowError :
>>> n = 256 >>> n.to_bytes(length=1, byteorder="big") Traceback (most recent call last): File "", line 1, in OverflowError: int too big to convertПреобразовать байтовую строку в целое число можно, воспользовавшись методом .from_bytes() класса int :
>>> int.from_bytes(b'\x06\xc1', byteorder="big") 1729Методы класса вызывают, используя имя класса, а не его экземпляр. Именно поэтому в предыдущем примере метод .from_bytes() вызывают, обращаясь к int .
Любопытный факт: 1729 — это самое маленькое положительное число, которое можно представить в виде суммы кубов двух положительных чисел двумя способами. Исторический анекдот связывает это число с индийским математиком Сринивасой Рамануджаном, который рассказал о нём своему наставнику Готфри Харолду Харди.
Харди часто навещал Рамануджана, когда тот, умирая, находился в больнице в Патни. Именно в одно из таких посещений произошёл «инцидент» с номером такси. Харди приехал в Патни на такси, воспользовавшись своим излюбленным транспортным средством. Он вошёл в палату, где лежал Рамануджан. Начинать разговор Харди всегда было мучительно трудно, и он произнёс свою первую фразу: «Если не ошибаюсь, то номер такси, на котором я приехал, 1729. Мне кажется, это скучное число». На что Рамануджан тотчас же ответил: «Нет, Харди! О нет! Это очень интересное число. Это самое малое из чисел, представимых в виде суммы двух кубов двумя различными способами».
Один из способов представления числа 1729 в виде суммы двух кубов — это 1 3 + 12 3 . Можете отыскать второй способ?
У чисел с плавающей точкой тоже есть методы. Возможно, самый полезный из них — это .is_integer() . Его используют для проверки того, есть ли у числа с плавающей точкой дробная часть:
>>> n = 2.0 >>> n.is_integer() True >>> n = 3.14 >>> n.is_integer() FalseВот — интересный метод .as_integer_ratio() . Он, вызванный для числа с плавающей точкой, возвращает кортеж, содержащий числитель и знаменатель дроби, представляющей это число:
>>> n.as_integer_ratio() (1, 2)Правда, из-за ошибки представления чисел с плавающей точкой, иногда этот метод возвращает неожиданные результаты:
>>> n = 0.1 >>> n.as_integer_ratio() (3602879701896397, 36028797018963968)Если надо — можно вызывать методы на числовых литералах, заключённых в круглые скобки:
>>> (255).to_bytes(length=1, byteorder="big") b'\xff' >>> (3.14).is_integer() FalseЕсли обойтись без скобок — при попытке вызова метода на целочисленном литерале будет выдана ошибка SyntaxError . А вот при вызове метода числового литерала с плавающей точкой отсутствие скобок, что странно, не приведёт к ошибке:
>>> 255.to_bytes(length=1, byteorder="big") File "", line 1 255.to_bytes(length=1, byteorder="big") ^ SyntaxError: invalid syntax >>> 3.14.is_integer() FalseПолный список методов числовых Python-типов можно найти в документации.
№2: числа обладают иерархией
В математике числа обладают естественной иерархией. Например, все натуральные числа являются целыми, а все целые числа — рациональными. Все рациональные числа — это вещественные числа, а все вещественные числа — это комплексные числа.
Похожие рассуждения применимы и к представлению чисел в Python. Здесь «числовая башня» выражается через абстрактные типы, содержащиеся в модуле numbers .
Числовая башня
Все числа в Python являются экземплярами класса Number :
>>> from numbers import Number >>> # Целые числа являются наследниками Number >>> isinstance(1729, Number) True >>> # Числа с плавающей точкой являются наследниками Number >>> isinstance(3.14, Number) True >>> # Комплексные числа являются наследниками Number >>> isinstance(1j, Number) TrueЕсли нужно узнать о том, является ли некое Python-значение числовым, но при этом неважно то, каким именно числовым типом оно представлено, воспользуйтесь конструкцией isinstance(value, Number) .
В Python имеется четыре дополнительных абстрактных типа, иерархия которых, начиная с наиболее общего числового типа, выглядит так:
- Класс Complex используется для представления комплексных чисел. Тут имеется один встроенный конкретный тип — complex .
- Класс Real — это представление вещественных чисел. Его единственный встроенный конкретный тип — float .
- Класс Rational представляет рациональные числа. Его единственным встроенным конкретным типом является Fraction .
- Класс Integral применяют для представления целых чисел. В нём имеется два встроенных конкретных типа — int и bool .
Так, погодите, а значения типа bool — это разве числа? Да — числа. Можете это проверить, воспользовавшись REPL:
>>> import numbers >>> # Комплексные числа являются наследниками Complex >>> isinstance(1j, numbers.Complex) True >>> # Комплексные числа не являются наследниками Real >>> isinstance(1j, numbers.Real) False >>> # Числа с плавающей точкой являются наследниками Real >>> isinstance(3.14, numbers.Real) True >>> # Числа с плавающей точкой не являются наследниками Rational >>> isinstance(3.14, numbers.Rational) False >>> # Объекты Fractions - это не наследники Rational >>> from fractions import Fraction >>> isinstance(Fraction(1, 2), numbers.Rational) True >>> # Объекты Fractions - это не наследники Integral >>> isinstance(Fraction(1, 2), numbers.Integral) False >>> # Целые числа - это наследники Integral >>> isinstance(1729, numbers.Integral) True >>> # Логические значения - это наследники Integral >>> isinstance(True, numbers.Integral) True >>> True == 1 True >>> False == 0 TrueВсё это, на первый взгляд, выглядит вполне нормально. Правда, порядок несколько нарушает то, что значения типа bool являются числами.
Странность Python: так как тип bool относится к классу Integral (на самом деле он — прямой наследник int ), со значениями True и False можно вытворять довольно необычные вещи.
Например, True можно использовать в роли индекса для того чтобы получить второй элемент итерируемого объекта. А если поделить число на False — будет выдана ошибка ZeroDivisionError .
Попробуйте выполнить «False»[True] и 1 / False в REPL!
Но если присмотреться к числовым типам поближе, окажется, что в иерархии Python-чисел имеется пара своеобразных моментов.
Числа типа Decimal не укладываются в иерархию
Как уже было сказано, в «числовой башне» Python есть 4 конкретных числовых типа, соответствующих четырём абстрактным типам: complex , float , Fraction и int . Но в Python имеется и пятый числовой тип, представленный классом Decimal . Этот тип используется для точного представления десятичных чисел и для преодоления ограничений арифметических операций с плавающей точкой.
Можно предположить, что числа типа Decimal являются наследниками Real , но это, на самом деле, не так:
>>> from decimal import Decimal >>> import numbers >>> isinstance(Decimal("3.14159"), numbers.Real) FalseЕдинственный класс, наследником которого является класс Decimal — это Number :
>>> isinstance(Decimal("3.14159"), numbers.Complex) False >>> isinstance(Decimal("3.14159"), numbers.Rational) False >>> isinstance(Decimal("3.14159"), numbers.Integral) False >>> isinstance(Decimal("3.14159"), numbers.Number) TrueЛогично то, что класс Decimal не является наследником Integral . В некоторой степени смысл есть и в том, что Decimal не является наследником Rational . Но почему Decimal не является наследником Real или Complex ?
Объекты Decimal обладают всеми методами, определёнными в классе Real, но эти объекты не должны регистрироваться в виде наследников Real, так как Decimal-числа не взаимодействуют с двоичными числами с плавающей точкой (например, результат операции Decimal(‘3.14’) + 2.71828 не определён). Но ожидается, что числа, классы которых являются наследниками абстрактного класса Real, способны взаимодействовать друг с другом (то есть — R1+R2 должно вычисляться в том случае, если числа R1 и R2 представлены типами, являющимися наследниками Real).
Получается, что объяснение странностей сводится к особенностям реализации.
Числа с плавающей точкой — странные создания
А вот числа с плавающей точкой, с другой стороны, реализуют абстрактный базовый класс Real . Они используются для представления вещественных чисел. Но, из-за того, что компьютерная память не является неограниченным ресурсом, числа с плавающей точкой — это лишь конечные аппроксимации вещественных чисел. Это приводит к возможности написания «ненормальных» образцов кода вроде такого:
>>> 0.1 + 0.1 + 0.1 == 0.3 FalseЧисла с плавающей точкой хранятся в памяти в виде двоичных дробей. Это приводит к появлению некоторых проблем. Например, у дроби 1/3 нет конечного десятичного представления (после десятичной точки идёт бесконечное множество троек). А у дроби 1/10 нет конечного представления в виде двоичной дроби.
Другими словами, в компьютере нельзя совершенно точно представить число 0,1 — если только этот компьютер не обладает бесконечной памятью.
Со строго математической точки зрения все числа с плавающей точкой — это рациональные числа, за исключением float(«inf») и float(«nan») . Но программисты используют их в роли аппроксимаций вещественных чисел и воспринимают их, по большей части, как вещественные числа.
Странность Python: float(«nan») — это особое значение с плавающей точкой, представляющее собой «не число». Такие значения часто обозначают как NaN . Но, так как float — это числовой тип, isinstance(float(«nan»), Number) возвращает True .
Получается, что «не числа» — это числа.
В общем, числа с плавающей точкой — странные создания.
№3: набор числовых типов Python можно расширять
Абстрактный числовой базовый тип Python позволяет программисту создавать собственные абстрактные и конкретные числовые типы.
В качестве примера рассмотрим класс ExtendedInteger , который реализует числа в форме a+b√p, где a и b — целые числа, а p — простое число (обратите внимание: класс не обеспечивает то, что число p является простым):
import math import numbers class ExtendedInteger(numbers.Real): def init(self, a, b, p = 2) -> None: self.a = a self.b = b self.p = p self._val = a + (b * math.sqrt(p)) def repr(self): return f"(, , )" def str(self): return f" + √" def trunc(self): return int(self._val) def float(self): return float(self._val) def hash(self): return hash(float(self._val)) def floor(self): return math.floor(self._val) def ceil(self): return math.ceil(self._val) def round(self, ndigits=None): return round(self._val, ndigits=ndigits) def abs(self): return abs(self._val) def floordiv(self, other): return self._val // other def rfloordiv(self, other): return other // self._val def truediv(self, other): return self._val / other def rtruediv(self, other): return other / self._val def mod(self, other): return self._val % other def rmod(self, other): return other % self._val def lt(self, other): return self._val < other def le(self, other): return self._val Для того чтобы обеспечить правильность реализации интерфейса Real конкретным типом — нужно создать реализации множества методов, в именах которых есть два символа подчёркивания. Ещё нужно поразмыслить о том, как методы вроде .add() и .mul() взаимодействуют с другими типами, являющимися наследниками Real .
Обратите внимание: вышеприведённый пример не создавался в расчёте на его полноту или абсолютную правильность. Его цель — продемонстрировать читателю возможности работы с числами.
При наличии реализации ExtendedInteger можно заниматься следующими вычислениями:
>>> a = ExtendedInteger(1, 2) >>> b = ExtendedInteger(2, 3) >>> a ExtendedInteger(1, 2, 2) >>> # Проверяем то, что a - это наследник Number >>> isinstance(a, numbers.Number) True >>> # Проверяем то, что a - это наследник Real >>> isinstance(a, numbers.Real) True >>> print(a) 1 + 2√2 >>> a * b ExtendedInteger(14, 7, 2) >>> print(a * b) 14 + 7√2 >>> float(a) 3.8284271247461903Иерархия числовых типов в Python — довольно гибкая структура. Но, конечно, всегда стоит очень внимательно относиться к реализации типов, являющихся наследниками встроенных абстрактных базовых типов Python. Нужно обеспечить их корректную работу друг с другом.
В документации по Python можно найти несколько советов по реализации собственных типов, которые стоит прочесть тому, кто решит заняться созданием собственных числовых типов. Такому человеку ещё полезно будет ознакомиться с реализацией Fraction .
Итоги
Вот — те три особенности Python-чисел, которые мы здесь обсуждали:
- У чисел есть методы, как и у практически всех остальных объектов в Python.
- Числа обладают иерархией, даже несмотря на то, что их чёткие взаимоотношения несколько портит наличие типов Decimal и float .
- Программисты могут создавать собственные числовые типы, которые вписываются в иерархию числовых типов Python.
Может быть, вы узнали из этого материала не только об этих особенностях чисел, но и ещё о чём-нибудь, что вам пригодится.
О, а приходите к нам работать? ��
Мы в wunderfund.io занимаемся высокочастотной алготорговлей с 2014 года. Высокочастотная торговля — это непрерывное соревнование лучших программистов и математиков всего мира. Присоединившись к нам, вы станете частью этой увлекательной схватки.
Мы предлагаем интересные и сложные задачи по анализу данных и low latency разработке для увлеченных исследователей и программистов. Гибкий график и никакой бюрократии, решения быстро принимаются и воплощаются в жизнь.
Сейчас мы ищем плюсовиков, питонистов, дата-инженеров и мл-рисерчеров.
РЕШЕНИЕ ОЛИМПИАДНЫХ ЗАДАЧ СРЕДСТВАМИ ДИСКРЕТНОЙ МАТЕМАТИКИ Текст научной статьи по специальности «Математика»
Аннотация научной статьи по математике, автор научной работы — Воистинова Г.Х., Хасанова Г.З.
В статье рассматривается использование элементов дискретной математики при решении олимпиадных задач. Описываются преимущества использования формул дискретной математики, приводятся приемы решения олимпиадных задач и даются рекомендации по подготовке учащихся к решению олимпиадных задач .The article discusses the use of discrete mathematics in solving Olympiad problems. The advantages are described and the necessary methods and techniques of solving are listed, as well as recommendations for preparing students for solving Olympiad problems are given.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Похожие темы научных работ по математике , автор научной работы — Воистинова Г.Х., Хасанова Г.З.
РЕШЕНИЕ ОЛИМПИАДНЫХ ЗАДАЧ МЕТОДАМИ ДИСКРЕТНОЙ МАТЕМАТИКИ
ПРИЕМЫ РЕШЕНИЯ ОЛИМПИАДНЫХ ЗАДАЧ КОМБИНАТОРНОГО ХАРАКТЕРА
Решение логических задач как основа развития мышления
ИНТЕГРАЦИЯ МАТЕМАТИКИ И ИНФОРМАТИКИ В РАМКАХ ПРОФИЛЬНОЙ СМЕНЫ КАК ФАКТОР ОПТИМИЗАЦИИ ПОДГОТОВКИ ШКОЛЬНИКОВ К ПРЕДМЕТНЫМ ОЛИМПИАДАМ
ВОПРОСЫ ПОДГОТОВКИ УЧИТЕЛЕЙ МАТЕМАТИКИ К ОРГАНИЗАЦИИ ОЛИМПИАД ДЛЯ ШКОЛЬНИКОВ
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Текст научной работы на тему «РЕШЕНИЕ ОЛИМПИАДНЫХ ЗАДАЧ СРЕДСТВАМИ ДИСКРЕТНОЙ МАТЕМАТИКИ»
Воистинова Гузель Хамитовна, доцент педагогических наук, СФ УУНиТ, г. Стерлитамак Хасанова Гульнара Зинуровна, студент, СФ УУНиТ, г. Стерлитамак
РЕШЕНИЕ ОЛИМПИАДНЫХ ЗАДАЧ СРЕДСТВАМИ ДИСКРЕТНОЙ
Аннотация: В статье рассматривается использование элементов дискретной математики при решении олимпиадных задач. Описываются преимущества использования формул дискретной математики, приводятся приемы решения олимпиадных задач и даются рекомендации по подготовке учащихся к решению олимпиадных задач.
Ключевые слова: дискретная математика, олимпиадные задачи, комбинаторика.
Annotation: The article discusses the use of discrete mathematics in solving Olympiad problems. The advantages are described and the necessary methods and techniques of solving are listed, as well as recommendations for preparing students for solving Olympiad problems are given.
Keywords: Discretemathematics, Olympiadtasks, skills, group.
Знание правил и формул дискретной математики дает преимущества при решении олимпиадных задач, экономит время на их решение. Поэтому знакомство школьников с элементами дискретной математики позволит повысить их шансы при решении нестандартных задач.
Дискретная математика может быть использована для решения многих задач, включая:
1. Комбинаторные задачи, такие как подсчет числа перестановок, сочетаний и размещений.
2. Задачи на графах, такие как поиск кратчайшего пути между двумя вершинами, определение наличия цикла в графе и т.д.
3. Задачи на теорию чисел, такие как поиск наибольшего общего делителя двух чисел, определение простых чисел и т.д.
4. Задачи на логику и алгоритмы, такие как построение алгоритмов сортировки, поиска и т.д.
5. Задачи на теорию вероятностей, такие как определение вероятности наступления события и т.д.
6. Задачи на теорию информации, такие как определение энтропии и кодирования информации.
7. Задачи на теорию игр, такие как определение оптимальной стратегии в игре.
8. Задачи на теорию групп и алгебры, такие как определение свойств групп и алгебраических структур.
9. Задачи, решаемые использованием принципа Дирихле.
Дискретная математика играет важную роль на олимпиаде по математике,
так как решения многих задач по математике, представленных на олимпиадах, основываются на принципах дискретной математики.
Олимпиадные задачи из разных областей знаний могут быть решены с помощью различных методов дискретной математики. Некоторые примеры решений задач:
Задача о максимальной разности - дано множество целых чисел, необходимо определить максимальную разницу между любыми двумя из них. Решение: отсортировать множество чисел по возрастанию, затем вычислить разницу между последним и первым элементами.
Задача о графах - дан граф и необходимо определить, является ли он деревом. Решение: применить теорему об эйлеровом пути и цикле - если граф связный и у него нет циклов, то он является деревом.
Задача по комбинаторике - дано множество объектов и необходимо определить количество способов выбрать из него подмножество определенного размера. Решение: применить формулу сочетаний, которая гласит, что количество способов выбрать k элементов из п равно ^/(^^-^1).
Задача на поиск максимального потока в графе - дан ориентированный граф, в котором некоторые ребра имеют ограничения на пропускную способность. Необходимо определить максимальный поток из истока в сток. Решение: применить алгоритм Форда-Фалкерсона для нахождения максимального потока.
Задача на криптографию - даны зашифрованные сообщения, необходимо расшифровать их. Решение: применять методы анализа частотности символов в сообщении, основанные на том, что в некоторых языках некоторые буквы встречаются чаще, чем другие.
Это лишь некоторые примеры решений задач средствами дискретной математики. Результаты могут быть достигнуты с использованием различных методов, иногда требующих использования нескольких методов в комбинации.
Такие задачи может решить каждый школьник, но знание элементов дискретной математики облегчит решение в несколько раз.
В школе элементы дискретной математики обычно изучаются в рамках курса математики или информатики. Основные разделы, которые рассматриваются в школе:
- Теория множеств и логика. В этой части курса ученики знакомятся с основными понятиями теории множеств и логики, такими как множество, подмножество, отношение, функция, аксиомы, доказательство и т.д.
- Комбинаторика. Здесь рассматриваются различные задачи на перестановки, сочетания, размещения, бинарные строки и т.д.
- Теория графов. Эта часть курса посвящена изучению графов и их свойств, таких как связность, циклы, деревья и т.д.
- Теория алгоритмов. Здесь ученики знакомятся с основными понятиями алгоритма, сложности алгоритмов, сортировкой и поиском данных.
В помощь учителю математики можно рекомендовать, например, следующие пособия: «Дискретная математика для школьников и студентов» [5], «Дискретная математика. Учебное пособие для старшеклассников и абитуриентов» [1].
Приведем упражнения, которые будут полезны при подготовке школьников к олимпиадам:
1. Сколькими способами можно разбить группу на команды, если в каждой должно быть определенное количество человек?
Полезным будет разбиение множества на подмножества.
2. Какие области связности есть в графе?
Полезным будет использование элементов теории графов.
3. Дано несколько утверждений, какие из них верны, а какие ложны?
Знание элементов математической логики поможет решать такие задачи.
4. Сколько операций требуется для выполнения алгоритма?
Определение сложности алгоритма позволит эффективно решать задачи
По мнению С.В. Клименко [4], преимущества использования элементов дискретной математики на олимпиадах в школе следующие:
•Ясность формулировок задач. В отличие от некоторых других предметов, у дискретной математики задачи выражены ясно и понятно, без лишних условностей и неопределенностей.
•Логика мышления. Решение задач дискретной математики требует аналитического и логического мышления, что благоприятно влияет на развитие соответствующих навыков.
•Независимость от региональных особенностей. В отличие от других школьных предметов, где особенности региона могут сильно влиять на успех учеников, задачи дискретной математики формулируются достаточно универсально и не зависят от конкретных региональных условий.
•Гибкость. Дискретная математика позволяет ученикам проявить свои творческие способности и искать нестандартные решения задач.
• Подготовка к будущей профессиональной деятельности. Отличное знание дискретной математики позволит в дальнейшем проектировать сложные системы, создавать алгоритмы и программы.
По мнению Г.Х. Воистиновой и А.А. Тарасова [2, с. 195-201], олимпиадные задачи с помощью элементов дискретной математики решаются достаточно легко, что экономит большое количество времени на решение объемных и сложных задач.
Приведем рекомендации по подготовке школьников к олимпиадам:
1. Следует использовать комбинаторику для подсчета количества возможных вариантов. Например, если задача требует подсчета количества перестановок или сочетаний, то комбинаторика позволит сэкономить время на ее решение.
2. Используйте приемы теории графов. Графы могут быть полезны для представления объектов и связей между ними, что может помочь в понимании условия сложных задач.
3. Полезно пользоваться теорией чисел для выявления математических закономерностей и свойств чисел. Такой прием может помочь в решении задач, связанных с простыми числами, делимостью и т.д.
4. Следует использовать логическое мышление и алгоритмы для решения задач, связанных с логическими высказываниями, комбинаторными задачами и т.д. А также можно применить симметрию и взаимосвязь задач. Некоторые задачи можно решать, исходя из того, что они имеют схожий вид с другими, уже решенными задачами.
5. В решении задач может помочь индукция для доказательства формул и свойств. Это уместно при доказательстве теорем и формул, которые являются основой для решения некоторых задач.
6. Наконец, не стоит забывать о варианте «обратного решения». Иногда начать решение задачи с его требования (заключения), а затем пройти в обратную сторону, чтобы прийти к исходной задаче.
Приведем примеры нестандартных задач, при решении которых полезно
знание элементов дискретной математики [3]:
Задача 1. Количество различных способов размещения 8 учеников по 4 в каждой группе.
Задача 2. Какое наименьшее количество цифр должно быть в числе, чтобы его произведение на 2 было полным квадратом?
Задача 3. Есть 7 красных, 5 синих и 3 зеленых шариков в корзине. Сколько различных комбинаций, чтобы вытащить 2 красных и 3 синих шарика?
Задача 4. Ученики в классе хотят выбрать свой лозунг по буквам. В классе 25 учеников, каждый из которых выбирает одну букву. Какое количество различных лозунгов может быть выбрано, если использовать все буквы алфавита?
Задача 5. Сколько существует разных парсеров для языка программирования, на котором написано 2000 строк кода? Каждый парсер может получить любой из 2000 возможных токенов.
Задача 6. Имеется 4 листочка бумаги, на каждом из которых написано одно из чисел от 1 до 4. Сколько существует различных расстановок листочков бумаги?
Задача 7. Какова вероятность выбрать две карты, которые образуют пару (например, две королевы), из стандартной колоды из 52 карт?
Задача 8. Сколько различных неубывающих 3-значных чисел можно получить из цифр ?
Задача 9. Сколько есть способов для 8 человек сесть за круглый стол?
Задача 10. Какое наименьшее количество граней должно быть у выпуклого многогранника, чтобы его можно было разрезать на 20 тетраэдров?
Задача 11. Представьте, что вы занимаетесь разработкой компьютерной игры, в которой игроку нужно пройти лабиринт. Лабиринт задается в виде графа, где узлы - это перекрестки, а ребра - это дороги между перекрестками. Игрок находится в начальном узле, а цель - добраться до конечного узла. Но есть одна особенность: на каждом перекрестке игрок может выбрать только один путь, и он не может вернуться назад. Таким образом, задача игрока -
найти кратчайший путь до конечного узла. Как вы можете использовать алгоритм Дейкстры для решения этой задачи?
Задача 12. Рассмотрим граф, в котором каждое ребро имеет вес. Предположим, что мы выбрали некоторое подмножество ребер и хотим найти кратчайший путь между двумя заданными узлами, используя только ребра из этого подмножества. Как решить эту задачу?
Задача 13. Предположим, что у вас есть два графа, и вы хотите проверить, являются ли они изоморфными. Какой алгоритм вы можете использовать для решения этой задачи? Можно ли улучшить этот алгоритм, если известно, что графы являются регулярными?
Задача 14. Рассмотрим граф, в котором каждое ребро имеет вес. Предположим, что мы хотим найти путь между двумя заданными узлами, который проходит через ровно k ребер. Как решить эту задачу?
Задача 15. Рассмотрим граф, в котором каждое ребро имеет вес. Предположим, что мы хотим найти кратчайший путь, проходящий через заданный набор узлов. Как решить эту задачу?
Задача 16. Предположим, что у вас есть две кучки камней, содержащие суммарно 100 камней. Вы можете брать из каждой кучки любое количество камней (но не больше, чем есть в кучке). Какое минимальное количество операций вы должны сделать, чтобы обе кучки содержали одинаковое количество камней?
Задача 17. Предположим, что у вас есть волшебный квадрат 3 на 3, в котором каждое число от 1 до 9 встречается ровно один раз, и сумма чисел в каждой строке, каждом столбце и каждой диагонали равна 15. Какое минимальное количество чисел вы должны поменять местами, чтобы нарушить это свойство?
Задача 18. Предположим, что у вас есть бесконечный лист бумаги, на котором нарисованы две точки. Какое минимальное количество прямых вы должны провести, чтобы точки были разделены на две отдельные области?
Задача 19. Предположим, что у вас есть неограниченный запас монет
достоинством 1, 2, 5, 10, 20 и 50 копеек. Какое минимальное количество монет вы должны использовать, чтобы набрать сумму в 99 копеек?
Задача 20. Предположим, что у вас есть две монеты, одна из которых выпадает орлом с вероятностью 1/3, а другая - с вероятностью 2/3. Выбирается случайная монета и подкидывается два раза. Если выпадает два орла, то выигрываете 1 рубль. Какую монету выбрать, чтобы максимизировать ваш шанс на выигрыш?
Задача 21. У какого наименьшего натурального числа сумма цифр равна
Задача 22. В какой последовательности нужно расставить цифры от 1 до 9, чтобы получилось наибольшее число?
Задача 23. Есть 100 монет, среди которых только 1 фальшивая. Как за одно взвешивание на чашечных весах определить, где находится фальшивая монета?
Задача 24. Есть 3 ведра объемом 3, 5 и 8 литров. Как с помощью этих ведер получить 4 литра воды?
Задача 25. Есть шахматная доска 8х8 и 32 фишки. Можно ли покрыть все клетки доски фишками так, чтобы каждая фишка занимала только одну клетку и не было свободных клеток?
Задача 26. У трех друзей есть по 2 ключа. Как им обменяться ключами так, чтобы каждый оставил хотя бы 1 свой ключ, но никто не получил ни свой ключ, ни ключ другого друга?
Задача 27. Какое минимальное количество цифр нужно записать на доске, чтобы каждая из цифр от 0 до 9 встретилась хотя бы один раз?
Задача 28. Есть 7 золотых монет, одна из которых фальшивая и легче остальных. Как определить фальшивую монету за два взвешивания на чашечных весах?
Задача 29. В какой последовательности нужно перемножать числа от 1 до 10, чтобы получить наименьшее возможное произведение?
Задача 30. Есть 5 мешков с конфетами разного веса, но неизвестно, какой
мешок весит меньше остальных. Как за 2 взвешивания на чашечных весах определить самый легкий мешок с конфетами?
Задача 31. Как расставить 8 матросов на 3 маленьких лодках без опрокидывания ни одной из лодок?
Задача 32. Можно ли разрезать квадрат на нечетное количество равных треугольников?
Задача 33. Есть 9 монет, одна из которых фальшивая - она легче на 1 грамм, чем настоящие. Как за две взвешивания на чашечных весах определить фальшивую монету?
Задача 34. На обочине дороги лежат два куска металла, один из которых стоит 40 рублей, а другой - 60. Однако, при обмене этих кусков между двумя людьми каждый получит то, что стоит меньше. Как это объяснить?
Задача 35. В бочке было 30 литров воды. Кто-то выпил из бочки 4 литра воды и затем добавил в бочку 5 литров воды. Сколько литров воды осталось в бочке?
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
Задача 36. Вероятность дождя на завтра - 50%. Вероятность того, что купальник забудут - 20%. Вероятность, что будет дождь и купальник забудут -5%. Какова вероятность того, что будет дождь или купальник забудут?
Задача 37. В 7-местном автобусе ехали 7 человек. На следующей остановке вышло 4 человека, а на остановке после этого в автобус село 2 человека. Сколько человек осталось в автобусе?
Задача 38. Папа и сын вместе наблюдают на часы: "Сколько времени?" Сын отвечает: "10 минут назад было дважды столько, сколько будет через 25 минут." Который час на часах?
Таким образом, дискретная математика поможет школьникам развивать свои математические навыки и подготовиться к решению олимпиадных задач, а также будет полезным при изучении других школьных предметов, помогает ученикам лучше понимать мир вокруг себя, развивает умственные способности, а также может стать полезным при подготовке к вступительным экзаменам в университет. Дискретная математика - важный раздел для подготовки будущих
математиков, программистов, инженеров и ученых. В целом, дискретная математика может быть использована для решения широкого спектра задач в различных областях, включая информатику, экономику, физику, биологию и т.д.
1. Белоусов А.В., Белоусова Е.А. Дискретная математика. Учебное пособие для старшеклассников и абитуриентов. - М.: Экзамен, 2009. - 301 с.
2. Воистинова Г.Х., Тарасов А.А. Комбинаторные задачи как средство формирования теоретического мышления // Математическое моделирование процессов и систем: Материалы XII Межд. молодежн. науч.-практ. конф. Часть 2, 17-19 ноября 2022 г., г. Стерлитамак / отв. ред. С.В. Викторов. -Стерлитамак: Стерлитамакский филиал УУНиТ, 2022. - С. 195-201.
3. Корн Г., Корн Т. Математический анализ и дискретная математика. М.: Мир, 2007.
4. Клименко С.В., Клименко Ю.С. Дискретная математика. Учебное пособие для студентов вузов. - М.: Лань, 2010. - 425 с.
5. Шевляков Г.Л., Шевлякова Н.Г. Дискретная математика для школьников и студентов. - М.: Физматлит, 2009. - 216 с.
Искусство умножения двузначных чисел в уме
Люди всегда стремились найти лучшие способы выполнения вычислений. Чем стремительнее развивается прогресс, тем более актуальными становятся высокие математические способности. Даже тот человек, карьера которого не предполагает работу с цифрами, ежедневно вынужден прибегать к счету в уме. Походы за покупками, оплата коммунальных счетов, планирование семейного бюджета – все это требует большого количество подсчетов. Конечно, можно полагаться на технику, ведь в каждом современном смартфоне присутствует калькулятор. Но все же стоит помнить, что умение быстро считать – это возможность существенно оптимизировать свои собственные ресурсы, поэтому развивать такие навыки важно.
Умножение в уме
В современном мире цифры окружают нас везде. Ежедневно мы не задумываясь выполняем десятки и даже сотни простых арифметических действий, но, стоит только столкнуться с более сложными числовыми операциями, и большинство людей машинально потянется к калькулятору. Мало кто хочет тратить время на сложные подсчеты в уме, когда с помощью информационных технологий произвести их можно за считанные секунды. Но что делать, если смартфона, калькулятора или листа бумаги с ручкой нет, а что-то посчитать нужно срочно? На помощь приходят методы счета в уме.
Складывать и вычитать устно – этому человек учится еще в школе. Со временем, удается научиться без труда производить вычисления даже с большими значениями. Конечно, это утверждение справедливо только для простых операций, таких как сложение и вычитание, а вот умножение освоить уже не так легко. В школе от детей требуется научиться умножать только на множитель от одного до десяти, а более сложные подсчеты допустимо производить на бумаге. Таким образом, ученикам не прививается умение выполнять умножение больших чисел в уме, этим навыкам можно обучиться только дополнительно.
Умение быстро считать очень полезно, так как оно используется ежедневно. Поэтому сегодня придумано множество подходов к счету. Чаще всего люди используют различные математические приемы, которые позволяют производить умножение устно. Они имеют свои плюсы и минусы, но все же позволяют получить правильный ответ без использования подручных средств. Чтобы определить, насколько эти способы эффективны и продуктивны в повседневных реалиях, нужно рассмотреть каждый из них отдельно.
Популярные методы устного умножения
Сегодня существует сразу несколько способов умножения в уме. Они не универсальны, но позволяют достаточно успешно производить операции с двузначными числами. Чтобы подобрать для себя оптимальный, лучше ознакомиться с самыми популярными из них:
Вариант 1. Умножение в столбик
Этот вариант отлично подходит тем, кто способен хорошо запоминать и удерживать в памяти сразу несколько промежуточных результатов вычислений. Благодаря этому подходу можно легко производить операции между двузначными числами. Рассмотрим данный вид счета на примере выражения 34*63.
Сначала необходимо умножить 34 на единицы второго числа: 34*3=102. Запоминаем это значение. Затем повторяем операцию уже с десятками множителя: 34*60=2040. Теперь требуется просто сложить результаты наших вычислений: 102+2040=2142
Вариант 2. Умножение с разложением на десятки и единицы
Этот вариант также требует хорошей памяти. Рассмотрим его на примере прошлого выражения 34*63.
Сначала требуется разложить числа на десятки и единицы, у нас получится: (30+4)*(60+3). Далее мы перемножаем между собой десятки: 30*60=1800. Запоминаем этот результат. Затем необходимо умножить десятки первого значения на единицы второго и наоборот: (30*3)+(60*4)=330. Теперь наступает самая сложная часть, главное – не сбиться. Нам нужно сложить результаты наших первых двух примеров и прибавить к ним произведение единиц перемножаемых чисел. Получится следующее выражение: 1800+330+4*3=2142.
Вариант 3. Умножение с большими числами
Этот вид вычислений больше подходит для тех двузначных чисел, которые близки к 100. Рассмотрим этот способ на примере выражения 88*95.
Сначала нужно представить каждое из этих значений как разность 100 и другого числа: 100-a=88 и 100-b=95, a=12, b=5. Так у нас получится (100-12)*(100-5). Теперь нужно произвести следующие вычисления: 88-b и 95-a, 88-5 и 95-12, получится 83 в обоих случаях. Это значение нужно запомнить. Теперь нам нужно найти a*b=12*5=60. Наш итоговый ответ будет состоять из четырех цифр от полученных ранее ответов: 83 и 60, получается 8360.
Иногда в результате подсчетов получается, что второе итоговое значение имеет три знака, а не два. Допустим, у нас получились числа 12 и 345. В этом случае нужно сложить вторую и третью цифру так, чтобы получилось 1545.
Это основные методы устного умножения. Но можно ли их назвать простыми? Несмотря на то, что при усердных тренировках удастся освоить любой из этих подходов, все же они будут требовать хорошей памяти и высокой концентрации. К тому же, не всегда допустимо проводить операции с многозначными числами с помощью данных методов. Лучше постараться найти для себя другие, более простые способы счета.
Быстрое умножение в уме больших чисел
Математики всех времен искали простые методы быстрого устного счета. Умножение и деление, в отличие от сложения и вычитания, являются более сложными операциями. Поэтому производить такие подсчеты в уме без должной подготовки сложно, тем более когда речь идет о многозначных числах. Проблема устного умножения в том, что не существует какого-либо универсального способа, который бы подходил вне зависимости от ситуации.
Мозг обычного человека не способен работать также быстро, как калькулятор. Мы склонны терять концентрацию, сбиваться, забывать результаты промежуточных операций. Поэтому стандартные способы устного умножения мало пригодны для повседневных задач. Они скорее являются хорошей разминкой для мозга, чем удобным инструментом. Но что делать, если быстро считать без подручных средств все же хочется?
Благодаря интернету можно найти немало информации по этому вопросу. Сегодня существует множество методик, позволяющих научиться складывать, вычитать, умножать и даже делить с моментальной скоростью. Но самым популярным направлением устного счета является ментальная арифметика. Ее неоспоримым плюсом является то, что она дается детям даже легче, чем взрослым.
Лучший способ научиться устному счету
Ментальная арифметика – это не только уникальный способ счета без подручных средств. В основе этой методики лежит равнозначное развитие как левого полушария мозга, отвечающего за логику и анализ, так и правого, которое контролирует работу воображения и фантазии. Несмотря на то, что освоить ментальную арифметику может любой желающий, она все же больше подходит для изучения в раннем возрасте. Именно в детстве можно приобрести навыки, которые не забудутся со временем и сохранятся на всю жизнь.
Обучение ментальной арифметике – длительный процесс, который требует усидчивости и нацеленности на результат. Пройдет немало времени, пока ребенок сможет полностью освоить программу и научиться не только складывать и вычитать, но и умножать и делить многозначные числа. Родителям не всегда удается контролировать периодичность занятий своего ребенка, а также следить за тем, чтобы он выполнял все необходимые упражнения. Этим обусловлен рост популярности групповых занятий ментальной арифметикой в центрах дополнительного развития детей.
Ученики, обучающиеся по этому направлению, сначала осваивают вычисления на древних счетах – абакусе. Когда базовые навыки закрепятся, наступает время для перехода к следующему, более сложному этапу. Теперь ученик постепенно привыкает представлять абакус в своем воображении и производить подсчеты уже на нем. Именно так и удается развить навык быстрого счета.
Благодаря занятиям ментальной арифметикой ребенок повышает успеваемость в школе, ведь теперь ему доступны не только простые вычисления в уме, но и быстрое умножение и деление. Количество времени, которое он тратит на выполнение домашних заданий, также сокращается. Так удается добиться большей продуктивности образовательного процесса в школе и дома. Навыки, приобретенные благодаря ментальной арифметике, сохранятся навсегда, что очень пригодится во взрослой жизни.