Что такое узлы сетки лежащие на окружности

Существует замечательная формула, которая позволяет считать площадь многоугольника на координатной сетке почти без ошибок. Это даже не формула, а настоящая теорема. На первый взгляд, она может показаться сложной. Но достаточно решить пару задач — и вы поймете, насколько это крутая фишка. Так что вперед!

Для начала введем новое определение:

— это любая точка, лежащая на пересечении вертикальных и горизонтальных линий этой сетки.

На первой картинке узлы вообще не обозначены. На второй обозначены 4 узла. Наконец, на третьей картинке обозначены все 16 узлов.

Какое отношение это имеет к задаче B5? Дело в том, что вершины многоугольника в таких задачах всегда лежат в узлах сетки. Как следствие, для них работает следующая теорема:

Теорема. Рассмотрим многоугольник на координатной сетке, вершины которого лежат в узлах этой сетки. Тогда площадь многоугольника равна:

где n — число узлов внутри данного многоугольника, число узлов, которые лежат на его границе (граничных узлов).

В качестве примера рассмотрим обычный треугольник на координатной сетке и попробуем отметить внутренние и граничные узлы.

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

Возможно, многим читателям непонятно, как считать числа Начните с внутренних узлов. Тут все очевидно: закрашиваем треугольник карандашом и смотрим, сколько узлов попало под закраску.

С граничными узлами чуть сложнее. Граница многоугольника — замкнутая ломаная, которая пересекает координатную сетку во многих точках. Проще всего отметить какую-нибудь «стартовую» точку, а затем обойти остальные.

Граничными узлами будут только те точки на ломаной, в которых одновременно пересекаются

1. Собственно, ломаная;
2. Горизонтальная линия координатной сетки;
3. Вертикальная линия.

Посмотрим, как все это работает в настоящих задачах.

Задача. Найдите площадь треугольника, если размер клетки равен 1 x 1 см:

Для начала отметим узлы, которые лежат внутри треугольника, а также на его границе:

Получается, что внутренний узел всего один: Граничных узлов — целых шесть: три совпадают с вершинами треугольника, а еще три лежат на сторонах.

Теперь считаем площадь по формуле:

Вот и все! Задача решена.

Задача. Найдите площадь четырехугольника, изображенного на клетчатой бумаге с размером клетки 1 см на 1 см. Ответ дайте в квадратных сантиметрах.

Снова отмечаем внутренние и граничные узлы. Внутренних узлов всего Граничных узлов: из которых 4 являются вершинами четырехугольника, а еще 3 лежат на сторонах.

Остается подставить числа в формулу площади:

Обратите внимание на последний пример. Эту задачу реально предлагали на диагностической работе в 2012 году. Если работать по стандартной схеме, придется делать много дополнительных построений. А методом узлов все решается практически устно.

Видео:Финкий узел для сетки .Скачать

Важное замечание по площадям

Но формула — это еще не все. Давайте немного перепишем формулу, приведя слагаемые в правой части к общему знаменателю. Получим:

Числа n и k — это количество узлов, они всегда целые. Значит, весь числитель тоже целый. Мы делим его на 2, из чего следует важный факт:

Площадь всегда выражается целым числом или дробью. Причем в конце дроби всегда стоит «пять десятых»: 10,5; 17,5 и т.д.

Таким образом, площадь в задаче B5 всегда выражается целым числом или дробью Если ответ получается другим, значит, где-то допущена ошибка. Помните об этом, когда будете сдавать настоящий ЕГЭ по математике!

Видео:ТОП 10 УЗЛОВ для ПОВСЕДНЕВНОЙ ЖИЗНИСкачать

Что такое узлы сетки окружности

Видео:КАК ВЯЗАТЬ УЗЛЫ для рыболовных сетей .Пособие для начинающего браконьера.Скачать

Метод узлов в задаче B5

Существует замечательная формула, которая позволяет считать площадь многоугольника на координатной сетке почти без ошибок. Это даже не формула, а настоящая теорема. На первый взгляд, она может показаться сложной. Но достаточно решить пару задач — и вы поймете, насколько это крутая фишка. Так что вперед!

Для начала введем новое определение:

— это любая точка, лежащая на пересечении вертикальных и горизонтальных линий этой сетки.

На первой картинке узлы вообще не обозначены. На второй обозначены 4 узла. Наконец, на третьей картинке обозначены все 16 узлов.

Какое отношение это имеет к задаче B5? Дело в том, что вершины многоугольника в таких задачах всегда лежат в узлах сетки. Как следствие, для них работает следующая теорема:

Теорема. Рассмотрим многоугольник на координатной сетке, вершины которого лежат в узлах этой сетки. Тогда площадь многоугольника равна:

где n — число узлов внутри данного многоугольника, число узлов, которые лежат на его границе (граничных узлов).

В качестве примера рассмотрим обычный треугольник на координатной сетке и попробуем отметить внутренние и граничные узлы.

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

Возможно, многим читателям непонятно, как считать числа Начните с внутренних узлов. Тут все очевидно: закрашиваем треугольник карандашом и смотрим, сколько узлов попало под закраску.

С граничными узлами чуть сложнее. Граница многоугольника — замкнутая ломаная, которая пересекает координатную сетку во многих точках. Проще всего отметить какую-нибудь «стартовую» точку, а затем обойти остальные.

Граничными узлами будут только те точки на ломаной, в которых одновременно пересекаются

1. Собственно, ломаная;
2. Горизонтальная линия координатной сетки;
3. Вертикальная линия.

Посмотрим, как все это работает в настоящих задачах.

Задача. Найдите площадь треугольника, если размер клетки равен 1 x 1 см:

Для начала отметим узлы, которые лежат внутри треугольника, а также на его границе:

Получается, что внутренний узел всего один: Граничных узлов — целых шесть: три совпадают с вершинами треугольника, а еще три лежат на сторонах.

Теперь считаем площадь по формуле:

Вот и все! Задача решена.

Задача. Найдите площадь четырехугольника, изображенного на клетчатой бумаге с размером клетки 1 см на 1 см. Ответ дайте в квадратных сантиметрах.

Снова отмечаем внутренние и граничные узлы. Внутренних узлов всего Граничных узлов: из которых 4 являются вершинами четырехугольника, а еще 3 лежат на сторонах.

Остается подставить числа в формулу площади:

Обратите внимание на последний пример. Эту задачу реально предлагали на диагностической работе в 2012 году. Если работать по стандартной схеме, придется делать много дополнительных построений. А методом узлов все решается практически устно.

Видео:Узлы для вязания сетей.Скачать

Важное замечание по площадям

Но формула — это еще не все. Давайте немного перепишем формулу, приведя слагаемые в правой части к общему знаменателю. Получим:

Числа n и k — это количество узлов, они всегда целые. Значит, весь числитель тоже целый. Мы делим его на 2, из чего следует важный факт:

Площадь всегда выражается целым числом или дробью. Причем в конце дроби всегда стоит «пять десятых»: 10,5; 17,5 и т.д.

Таким образом, площадь в задаче B5 всегда выражается целым числом или дробью Если ответ получается другим, значит, где-то допущена ошибка. Помните об этом, когда будете сдавать настоящий ЕГЭ по математике!

Видео:Как связать угол тента и затеняющей сетки. Навыки вязания узлов.Скачать

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

О чем эта статья:

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

Видео:Жесткие, шарнирные узлы. Податливость и жесткость стальных узлов.Скачать

Теория графов

В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа.

Теория графов — обширный раздел дискретной математики, в котором системно изучают свойства графов.

Теория графов широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и в других областях.

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

Давайте на примере.

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

Число знакомых у одних людей может отличаться от числа знакомых у других людей, некоторые могут вовсе не быть знакомы (такие элементы будут точками, не соединёнными ни с какой другой). Так получился граф:

В данном случае точки — это вершины графа, а связки — рёбра графа.

Теория графов не учитывает конкретную природу множеств A и B. Существует большое количество разных задач, при решении которых можно временно забыть о содержании множеств и их элементов. Эта специфика не отражается на ходе решения задачи.

Например, вопрос в задаче стоит так: можно ли из точки A добраться до точки E, если двигаться только по соединяющим точки линиям. Когда задача решена, мы получаем решение, верное для любого содержания, которое можно смоделировать в виде графа.

Не удивительно, что теория графов — один из самых востребованных инструментов при создании искусственного интеллекта: ведь искусственный интеллект может обсудить с человеком вопросы отношений, географии или музыки, решения различных задач.

Графом называется система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов.

Пусть V — (непустое) множество вершин, элементы v ∈ V — вершины. Граф G = G(V) с множеством вершин V есть некоторое семейство пар вида: e = (a, b), где a, b ∈ V, указывающих, какие вершины остаются соединёнными. Каждая пара e = (a, b) — ребро графа. Множество U — множество ребер e графа. Вершины a и b — концевые точки ребра e.

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

Линейные структуры данных особенны тем, что связывают элементы отношениями по типу «простого соседства». Линейными структурами данных можно назвать массивы, таблицы, списки, очереди, стеки, строки. В нелинейных структурах данных элементы располагаются на различных уровнях иерархии и подразделяются на три вида: исходные, порожденные и подобные.

Курсы обучения математике помогут подтянуть оценки, подготовиться к контрольным, ВПР и экзаменам.

Видео:Как вязать узлы. 10 самых нужных узлов.Скачать

Основные понятия теории графов

Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. Точки называют вершинами графа, а линии — ребрами.

• Два ребра называются смежными, если у них есть общая вершина.
• Два ребра называются кратными, если они соединяют одну и ту же пару вершин.
• Ребро называется петлей, если его концы совпадают.
• Степенью вершины называют количество ребер, для которых она является концевой (при этом петли считают дважды).
• Вершина называется изолированной, если она не является концом ни для одного ребра.
• Вершина называется висячей, если из неё выходит ровно одно ребро.
• Граф без кратных ребер и петель называется обыкновенным.

Лемма о рукопожатиях

В любом графе сумма степеней всех вершин равна удвоенному числу ребер.

Доказательство леммы о рукопожатиях

Если ребро соединяет две различные вершины графа, то при подсчете суммы степеней вершин мы учтем это ребро дважды.

Если же ребро является петлей — при подсчете суммы степеней вершин мы также учтем его дважды (по определению степени вершины).

Из леммы о рукопожатиях следует: в любом графе число вершин нечетной степени — четно.

Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные.

Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.

Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых.

Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3.

Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.

Видео:Математика | 5 ЗАДАЧ НА ТЕМУ ОКРУЖНОСТИ. Касательная к окружности задачиСкачать

Путь и цепь в графе

Путем или цепью в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.

Циклом называют путь, в котором первая и последняя вершины совпадают.

Путь или цикл называют простым, если ребра в нем не повторяются.

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

Можно рассмотреть такое подмножество вершин графа, что каждые две вершины этого подмножества соединены путем, а никакая другая вершина не соединена ни с какой вершиной этого подмножества.

Каждое такое подмножество, вместе со всеми ребрами исходного графа, соединяющими вершины этого подмножества, называется компонентой связности.

Один и тот же граф можно нарисовать разными способами. Вот, например, два изображения одного и того же графа, которые различаются кривизной:

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

Граф H, множество вершин V’ которого является подмножеством вершин V данного графа G и множество рёбер которого является подмножеством рёбер графа G соединяющими вершины из V’ называется подграфом графа G.

Видео:Надежный узел для вязания сети который не поедетСкачать

Визуализация графовых моделей

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

Графы — и есть помощники в этом деле. Они помогают представить любую информацию, которую можно промоделировать в виде объектов и связей между ними.

Граф можно нарисовать на плоскости или в трехмерном пространстве. Его можно изобразить целиком, частично или иерархически.

Изобразительное соглашение — одно из основных правил, которому должно удовлетворять изображение графа, чтобы быть допустимым. Например, при изображении блок-схемы программы можно использовать соглашение о том, что все вершины должны изображаться прямоугольниками, а дуги — ломаными линиями с вертикальными и горизонтальными звеньями. При этом, конкретный вид соглашения может быть достаточно сложен и включать много деталей.

Виды изобразительных соглашений:

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

Видео:Самый простой из самых надежных узлов.Скачать

Виды графов

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

Видео:Самый Известный и Надежный Узел: Где и в Каком Спорте? @Popular_KnotsСкачать

Ориентированные и неориентированные графы

Графы, в которых все ребра являются звеньями, то есть порядок двух концов ребра графа не существенен, называются неориентированными.

Графы, в которых все ребра являются дугами, то есть порядок двух концов ребра графа существенен, называются ориентированными графами или орграфами.

Неориентированный граф можно представить в виде ориентированного графа, если каждое его звено заменить на две дуги с противоположным направлением.

Графы с петлями, смешанные графы, пустые графы, мультиграфы, обыкновенные графы, полные графы

Если граф содержит петли — это обстоятельство важно озвучивать и добавлять к основной характеристике графа уточнение «с петлями». Если граф не содержит петель, то добавляют «без петель».

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

Пустой граф — это тот, что состоит только из голых вершин.

Мультиграфом — такой граф, в котором пары вершин соединены более, чем одним ребром. То есть есть кратные рёбра, но нет петель.

Граф без дуг, то есть неориентированный, без петель и кратных ребер называется обыкновенным.

Граф называют полным, если он содержит все возможные для этого типа рёбра при неизменном множестве вершин. Так, в полном обыкновенном графе каждая пара различных вершин соединена ровно одним звеном.

Двудольный граф

Граф называется двудольным, если множество его вершин можно разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества.

Например, полный двудольный граф состоит из двух множеств вершин и из всевозможных звеньев, которые соединяют вершины одного множества с вершинами другого множества.

Видео:Обзор схватывающих узлов. Все про схватывающие узлы.Скачать

Эйлеров граф

Эйлеров граф отличен тем, что в нем можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер.

Пример. Является ли полный граф с одинаковым числом n рёбер, которым инцидентна каждая вершина, эйлеровым графом?

Ответ. Если n — нечётное число, то каждая вершина инцидентна n — 1 ребрам. В таком случае наш граф — эйлеровый.

Видео:Лекция 1 | Теория узлов | Обзор одного снаСкачать

Регулярный граф

Регулярным графом называется связный граф, все вершины которого имеют одинаковую степень k.

Число вершин регулярного графа k-й степени не может быть меньше k + 1. У регулярного графа нечётной степени может быть лишь чётное число вершин.

Пример. Построить регулярный граф, в котором самый короткий цикл имеет длину 4.

Чтобы длина цикла соответствовала заданному условию, нужно чтобы число вершин графа было кратно четырем. Если число вершин равно четырём — получится регулярный граф, в котором самый короткий цикл имеет длину 3.

Увеличим число вершин до восьми (следующее кратное четырем число). Соединим вершины ребрами так, чтобы степени вершин были равны трём. Получаем следующий граф, удовлетворяющий условиям задачи:

Видео:Ещё раз разбираем как делать узел на рыболовных сетях и рыболовных мережах. Посадка рыболовной сети.Скачать

Гамильтонов граф

Гамильтоновым графом называется граф, содержащий гамильтонов цикл.

Гамильтоновым циклом называется простой цикл, который проходит через все вершины рассматриваемого графа.

Говоря проще, гамильтонов граф — это такой граф, в котором можно обойти все вершины, и каждая вершина при обходе повторяется лишь один раз.

Видео:Узлы для рыболовной сети | Netting knotsСкачать

Взвешенный граф

Взвешенным графом называется граф, вершинам и/или ребрам которого присвоены «весы» — обычно некоторые числа. Пример взвешенного графа — транспортная сеть, в которой ребрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг.

Видео:Интуитивная теория узлов | примеры нетривиальных узлов, задачи теории узлов, операция связной суммы.Скачать

Графы-деревья

Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом.

Число q ребер графа находится из соотношения q = n — 1, где n — число вершин дерева.

Приведенное соотношение выражает критическое значение числа рёбер дерева, так как, если мы присоединим к дереву ещё одно ребро — будет создан цикл. А если уберем одно ребро, то граф-дерево разделится на две компоненты. Граф, состоящий из компонент дерева, называется лесом.

Видео:Правильные узлы для сетки из лески. часть 2.Скачать

Определение дерева

Деревом называется связный граф, который не содержит циклов.

Таким образом, в дереве невозможно вернуться в исходную вершину, перемещаясь по ребрам и не проходя по одному ребру два или более раз.

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

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

Легко проверить, что дерево — это граф, в котором любые две вершины соединены ровно одним простым путем. Если выкинуть любое ребро из дерева, то граф станет несвязным. Поэтому:

Дерево — минимальный по числу рёбер связный граф.

Висячей вершиной называется вершина, из которой выходит ровно одно ребро.

Определения дерева:

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

Очень часто в дереве выделяется одна вершина, которая называется корнем дерева. Дерево с выделенным корнем называют корневым или подвешенным деревом. Пример: генеалогическое дерево.

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

Например, при соглашении включения (рис. 1) вершины корневого дерева изображают прямоугольниками, а соглашение — опрокидывания (рис. 2) подобно классическому соглашению нисходящего плоского изображения корневого дерева. Вот так могут выглядеть разные изображения одного дерева:

Теоремы дерева и их доказательства

В дереве с более чем одной вершиной есть висячая вершина.

Доказательство первой теоремы:

Пойдем из какой-нибудь вершины по ребрам. Так как в дереве нет циклов, то мы не вернемся в вершину, в которой уже побывали. Если у каждой вершины степень больше 1, то найдется ребро, по которому можно уйти из неё после того, как мы пришли в нее.

Но поскольку количество вершин в дереве конечно, когда-нибудь мы остановимся в некоторой вершине. Противоречие. Значит, когда-нибудь мы дойдём в висячую вершину. Если же начать идти из неё, то мы найдём вторую висячую вершину.

В дереве число вершин на 1 больше числа ребер.

Доказательство второй теоремы:

Докажем по индукции по количеству вершин в дереве n. Если в дерево одна вершина, то факт верен. Предположим, что для всех n

У любого связного графа есть остовное дерево.

Доказательство третьей теоремы:

Чтобы найти остовное дерево графа G, можно найти цикл в графе G и выкинуть одно ребро цикла — потом повторить. И так пока в графе не останется циклов. Полученный граф будет связным, так как мы выкидывали рёбра, не нарушая связность, но в нём не будет циклов. Значит, он будет деревом.

Теория графов и современные прикладные задачи

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

Графы и задача о потоках

Система водопроводных труб в виде графа выглядит так:

Каждая дуга графа отображает трубу. Числа над дугами (весы) — пропускная способность труб. Узлы — места соединения труб. Вода течёт по трубам только в одном направлении. Узел S — источник воды, узел T — сток.

Задача: максимизировать объём воды, протекающей от источника к стоку.

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

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

Задачу успешно применяют в различных распределенных системах: система электроснабжения, коммуникационная сеть, система железных дорог.

Графы и сетевое планирование

В задачах планирования сложных процессов, где много разных параллельных и последовательных работ, часто используют взвешенные графы. Их еще называют сетью ПЕРТ (PERT).

PERT (Program (Project) Evaluation and Review Technique) — техника оценки и анализа программ (проектов), которую используют при управлении проектами.

Сеть ПЕРТ — взвешенный ациклический ориентированный граф, в котором каждая дуга представляет работу (действие, операцию), а вес дуги — время, которое нужно на ее выполнение.

Если в сети есть дуги (a, b) и (b, c), то работа, представленная дугой (a, b), должна быть завершена до начала выполнения работы, представленной дугой (b, c). Каждая вершина (vi) представляет момент времени, к которому должны быть завершены все работы, задаваемые дугами, оканчивающимися в вершине (vi).

• одна вершина, у которой нет предшественников, определяет время начала работы
• одна вершина без последователей соответствует моменту завершения комплекса работ.

Путь максимальной длины между этими вершинами графа называется критическим путем. Чтобы выполнить всю работу быстрее, нужно найти задачи на критическом пути и придумать, как их выполнить быстрее. Например, нанять больше людей, перепридумать процесс или ввести новые технологии.

Видео:Разновидности узлов для сетевязания (часть 7)Скачать

«Задачи на клетчатой бумаге»

Главная > Реферат

Глава 2. Сколько узлов на отрезке?

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

Сделаем сначала небольшое наблюдение. Пусть А и В – узлы сетки. Обозначим через С первый узел, встречавшиеся после А на отрезке АВ (значит, между А и С больше нет узлов). Построим прямоугольный треугольник А СD с гипотенузой А С и катетами, лежащими на линиях сетки (рис.1).

Если С ≠ В, то сместим этот треугольник вдоль

отрезка АВ на расстояние А С. Получим равный

ему треугольник ССD.

Следовательно, С – узел, и между С и Снет узлов. Ясно,

что если эту процедуру продолжить, мы когда-нибудь

получим в качестве очередной точки С точку В – узел

сетки. Рассматривая большой прямоугольный треугольник

ARB с гипотенузой АВ, приходим к равенствам: Рис. 1

AR = (k+1) · AD,

BR = (k+1) · СD , (1)

AB = (k+1) · A С ‌

Теперь мы можем выяснить, сколько узлов Рис. 2. лежит между точками А и В(конечно, мы считаем, что А и В не лежат на одной линии сетки). Построим прямоугольный треугольник ARB с вершинами в узлах сетки и с гипотенузой АВ (рис.2).

Пусть AR = р, BR = q. Понятно, что р и q – целые положительные числа.

Теорема. Если р и q взаимно просты, то между А и В на отрезке АВ нет узлов сетки. Если же наибольший общий делитель р и q равен n , где n > 1 (НОД (р, q ) = n > 1), то на отрезке АВ между точками А и В расположены ровно ( n – 1) узлов сетки.

Доказательство. 1) Пусть числа p и q взаимно просты. Если между А и В были k узлов (k ≥ 1), то, взяв ближайший к А узел С, мы получим по формулам (1): p =(k+1) · AD, q = (k +1) · СD, то есть р и q имеют общий делитель k + 1, больший 1. Но ведь они взаимно просты!

2)Пусть НОД (р,q) = n > 1. Поделив отрезки AR и BR на n равных частей, мы опять приходим к рис.1, где С, С, …, С – какие-то узлы сетки и k=n – 1. Таким образом, в этом случае между точками А и В есть хотя бы n – 1 узел. Почему их не может быть больше, чем n – 1? В этом случае между узлами А и С были бы и другие узлы. Пусть С – ближайший к А узел. Тогда АС´ Задача 1. [11] В прямоугольнике 4×7, нарисованном на клетчатой бумаге, провели диагональ. Сколько клеточек она разрезала?

Задача 2. В прямоугольнике размером 200×300, нарисованном на клетчатой бумаге, провели диагональ. Сколько клеточек она разрезала на две части?

Задача 3. В прямоугольнике 1000×1003, нарисованном на клетчатой бумаге, провели диагональ. Сколько клеточек она разрезала?

Задачу 1 легко решить, просто «водя пальцем по картинке»

Для решения задачи 2 полезно вспомнить наши разговоры о количестве узлов на отрезке и обсуждение

рис.1: ясно, что вдоль диагонали прямоугольника 200×300 можно расположить 100 прямоугольников 2×3, и в каждом из них, очевидно, диагональ будет рассекать по 4 клетки. Поэтому ответ к задаче 2 – четыреста клеток.

В задаче 3 такие соображения, увы, не помогают: числа 1000 и 1003 взаимно не просты. Сформулируем эту задачу в общем виде:

Сколько клеток рассекает на две части диагональ прямоугольника m×n, где m и n – взаимно простые числа?

Заметим, что диагональ такого прямоугольника не проходит через узлы. Будем считать, что диагональ идёт из левого нижнего угла прямоугольника. Самой первой она рассекает левую нижнюю угловую клетку (клетку № 1), потом она попадёт в клетку № 2 (рис.4), и так далее. Пусть диагональ уже пересекла k клеток. Так как она ни разу не проходит через узел, то всегда можно однозначно указать, какую клетку она рассечёт после клетки с номером k.

Итак, мы получили «цепочку», идущую из левого нижнего угла в правый верхний. Нам надо понять,

Рис. 4 чему равно число клеток в этой цепочке. Дадим каждой клетке адрес (t, s), если она расположена в горизонтальном ряду с номером t и вертикальном ряду с номером s. Левый нижний угол получает адрес (1,1), а правый верхний – (m,n). Теперь остаётся заметить, что при переходе от клетки с номером k в нашей цепочке к клетке с номером k+1 сумма чисел t и s в адресе возрастает точно на 1. Значит,

чтобы перейти от клетки с адресом (1,1) к клетке с адресом (m,n), надо сделать ровно m + n – 2 шагов, пройдя, таким образом, m + n – 1 клеток.

Итак, ответ к задаче 3 – число клеток равно 2002.

Объединим задачи 2 и 3.

Пусть m и n – произвольные натуральные числа.

Сколько клеток рассекает диагональ

Пусть d = НОД (m×n). Как и при решении задачи 2,

мы видим, что вдоль диагонали исходного

прямоугольника образуется d маленьких прямоугольников  . Стороны этих маленьких прямоугольников уже взаимно просты, поэтому их диагонали рассекают по + – 1 клеток каждая. Значит, диагональ исходного прямоугольника рассечёт ( + – 1) · d = m + n – d клеток.

Теперь при желании мы можем без труда сосчитать, сколько клеток рассекут диагонали следующих прямоугольников: 36×56, 105×24, 2003×111.

Глава 3. Задачи на разрезание

С этими задачами, очевидно, столкнулся ещё первобытный человек, когда пытался раскроить шкуру убитого зверя, чтобы сшить себе одежду. Известно, что решения многих простых задач на разрезание были найдены ещё древними греками. Первый письменный источник с подобными задачами относится к Х веку – это фрагменты трактата персидского астронома Абул-Вефа, жившего в Багдаде. Профессиональные математики всерьёз занялись задачами на разрезание ближе к середине XIX века.

Сделаем небольшую классификацию таких задач [15]. Все их сюжеты можно условно поделить на следующие виды и подвиды:

* Дробление – требуется разрезать данную фигуру:

на заданное число равных между собой, или, как говорят математики, — конгруэнтных частей (фигур);

на заданное число конгруэнтных и подобных ей фигур (такие фигуры получили название «делящихся»);

определённым количеством прямых на максимально возможное число частей, не обязательно равных.

Возможны и другие вариации условий разрезания, так как фантазия человека не имеет ограничений.

* Квадрирование – разрезание фигуры на возможно меньшее число частей, из которых затем можно сложить квадрат.

* Трансформирование – требуется разрезать одну фигуру так, чтобы их её частей можно было сложить вторую заданную фигуру (не квадрат).

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

Учитывая большое общее количество задач на разрезание, мы в этой работе будем рассматривать задачи на клетчатой бумаге на дробление и задачи, связанные с шахматной доской. А остальные постараемся изучить при дальнейшем исследовании по этой теме.

Следует учесть, что термин «разрезание» не всегда надо понимать буквально: при решении приведённых далее задач достаточно на чертеже данной фигуры обозначить линии разреза карандашом. Но смысл разрезания предполагает ещё и выход из плоскости и переворачивание фигуры любой её стороной из двух существующих.

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

Задача 1 . Можно ли разрезать квадрат 66 на полоски 14 ?

Решение. Используем раскраску, показанную на рис. 1. Любая полоска 14, положенная на такую доску, покроет ровно одну чёрную клетку. Следовательно, если бы мы разрезали квадрат на полоски, то чёрных клеток оказалось бы столько же, сколько полосок. Но число полосок должно быть равно (6 · 6) : 4 = 9, а чёрных клеток на этом рисунке 8! Значит разрезание

Рис. 1 невозможно.

Вместо раскраски в два цвета можно было использовать раскраску в четыре цвета, изображённую на рисунке 2 (каждый цвет помечен своим номером: цвет 1, цвет 2, цвет 3 и цвет 4). Рис. 2

Тогда каждая полоска 14 будет содержать ровно по одной клетке каждого цвета. Значит, если бы удалось разрезать квадрат на полоски, то клеток всех цветов было бы поровну. Но клеток цветов 1 и 3 – по 9, цвета 2 – 10, а цвета 4 – 8 штук.

Теперь вы сможете самостоятельно решить задачи 2 и 3.

Задача 2. Можно ли прямоугольник 89 разрезать на полоски 16 ?

Задача 3. Можно ли сложить прямоугольник из нарисованных на рис. 3 фигурок? (Каждая фигурка должна использоваться ровно один раз!)

Задача 4. [8] На шахматной доске стоят 4 коня (рис. 4) Требуется разделить доску на 4 одинаковые по форме части, на каждой из которых стоял бы в точности один конь

Рис. 4 Задача 5 . [3] В Волшебной Стране свои волшебные законы природы, один из которых гласит: «Ковёр-самолёт будет летать только тогда, когда он имеет прямоугольную форму». У Ивана-царевича был ковёр-самолёт размером 912. Как-то раз Змей Горыныч подкрался и отрезал от этого ковра маленький коврик размером 18. Иван царевич очень расстроился и хотел было отрезать ещё кусочек 14, чтобы получился прямоугольник 812, но Василиса Премудрая предложила поступить по-другому. Она разрезала ковёр на три части, из которых волшебными нитками сшила квадратный ковёр-самолёт размером 1010. Сможете ли вы догадаться, как Василиса Премудрая переделала испорченный ковёр?

Задача 6. [1] На прямоугольном участке земли находятся 4 колодца, изображённые на рис. 5 точками. Разбейте этот участок на 4 части, одинаковые по величине и форме, так, чтобы колодцы на каждом участке занимали одно и то же положение. Рис. 5

Задача 7. [15] Найти все целые положительные числа n таким образом, чтобы каждый треугольник можно было разрезать на n треугольников, подобных между собой.

Решение. Начертим разносторонний треугольник. Прежде всего покажем, как любой треугольник можно разрезать на n = k² равных (следовательно, подобных) треугольников, т.е. на число n, равное квадрату целого числа. Разделим каждую сторону треугольника на k равных частей и через точки деления проведём прямые, параллельные его сторонам. Тогда число малых треугольников равно 1+ 3 + 5 + … + (2k – 1) = k²

Рис. 6. k = 5, n = 25 Рис. 7 Рис. 8

Теперь покажем, что каждый треугольник разрезается на любое число n ≥ 4 подобных между собой треугольников.

В самом деле, оставим на рис. 6 малые треугольники только в нижней полосе (трапеции), а все остальные объединим в один (рис. 7).

Столь же легко показать, что число таких частей может быть сделано любым нечётным n ≥ 7 : верхний из четырёх треугольников разбит на 2k (k ≥ 2) частей, и ещё имеется три нижних, так что общее число частей равно n = 2k + 3, где k ≥ 2 (рис. 8).

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

Вот именно с таких занимательных задач начинается уже серьёзная математика с исследованиями, доказательствами и построением небольшого раздела математической теории под названием «делящиеся фигуры на плоскости».

Задача 8. [16] «Парадокс шахматной доски»

Шахматная доска разрезается наискосок, как это изображено на левой половине рисунка 9, а затем часть В сдвигается влево вниз, как это показано на правой половине рисунка. Первоначальная площадь Рис. 9

равнялась 64 кв. ед, теперь же она равна 63. Куда исчезла одна недостающая квадратная единица?

Глава 4. Расстояние в «клетчатом» городе

С понятием расстояния мы сталкиваемся ежедневно. «Каково расстояние от дома до школы?», «Сколько километров от Москвы до Петербурга?» — эти вопросы никого не удивят. Зная расстояние, мы можем прикинуть, долго ли добираться от одного места до другого. Все мы умеем вычислять расстояние между двумя точками на координатной прямой, с помощью теоремы Пифагора мы можем вычислить расстояние между двумя точками на координатной плоскости.

А теперь возьмём хорошо знакомый нам листок клетчатой бумаги и представим себе, что это – город, линии сетки – улицы. Давайте прогуляемся по этому городу, ходя только по улицам (порядки в этом городе очень строгие). Длину клетки будем считать равной 1. Как нам быстрее всего попасть с перекрёстка А на перекрёсток Б (рис. 1)?

Можно, например, пройти из А в С, а потом – из С в В. Можно было идти через D, а можно – и более замысловатым путём. Что же мы теперь назовём расстоянием от А до В? Конечно, длину кратчайшего

Рис. 1 пути: 4 + 3 = 7.

А теперь представим себе, что у нас в запасе есть время проделать путь длиной 3. В каких узлах мы можем побывать, выйдя из А? (Или: из каких узлов можно добраться до А, пройдя путь не более 3?) Ответ на этот вопрос изображён на рисунке 2). Наверное, многие из вас сейчас вспомнили о круге на плоскости: ведь круг радиуса r с центром в точке А и есть множество всех точек плоскости, которые удалены от А не больше, чем на r. Но как не похож ромбик из точек с рисунка 2 на привычный круг! Рис. 2

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

Задача 1. [11] В «клетчатом» городе выделили район – квадрат 44. Какое

Наименьшее количество детских площадок нужно построить в этом районе, чтобы из любого узла этого района можно было попасть на одну из этих площадок, проделав путь не более 3?

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

Решите такую же задачу с прямоугольником 63. А как решается подобная задача, если расстояние на плоскости измеряется обычным способом?

Задача 2. Какое наибольшее количество котов можно разместить в узлах сетки на территории квадрата 44, чтобы расстояние между любыми двумя из них было не менее 2 (иначе коты подерутся)?

Наверное, без особого труда сумеете поделить территорию квадрата между 13 котами (рис. 4). А вот Рис. 4

14 котов мирно ужиться на этой территории уже не смогут. Докажем это. Поделим всю территорию, кроме центра квадрата, на 4 непересекающиеся зоны (рис. 5). Если даже одного из 14 котов поселить в центре квадрата, то остальных 13 придётся разместить по этим зонам. Значит, в какой-то зоне окажется хотя бы 4 кота. Перебирая различные варианты расселения 4 котов в

Рис. 5 какой-нибудь из этих зон, легко увидеть, что это невозможно.

Подумайте, как решить эту задачу, если расстояние на плоскости измеряется, как обычно.

Итак, мы познакомились с расстоянием в «клетчатом» городе. Оно ни чуть не менее естественно, чем обычное расстояние «по прямой». Что их объединяет? Каковы общие свойства, которыми должно обладать расстояние?

Свойство 1. Расстояние между двумя точками неотрицательно, причём оно равно нулю, только если точки совпадают.

Ещё бы! Чтобы попасть из точки А в неё же, никуда идти не надо, а чтобы попасть в другую точку В, придётся проделать некий путь положительной длины.

Свойство 2. Расстояние от точки А до точки В равно расстоянию от точки В до точки А.

Недаром мы говорим обычно не о расстоянии от А до В, а о расстоянии между А и В, не различая расстояния от А до В и от В до А.

Свойство 3. Для точек А, В и С сумма расстояний от А до С и от С до В не меньше расстояния от А до В (неравенство треугольника).

Свойства 1, 2 и 3 в математике называются аксиомами расстояния. Как мы знаем, эти свойства есть у обычного расстояния на плоскости. Не трудно проверить, что есть они и у нового расстояния, введённого нами в «клетчатом» городе.

Глава 5. Игры на клетчатой бумаге

1. Крестики — нолики

1. Популярная игра в крестики – нолики состоит в следующем. Двое по очереди рисуют на листе клетчатой бумаги крестики и нолики. Первый игрок рисует крестики, второй – нолики. Выигрывает тот, кто первым поставит определённое количество своих знаков в ряд (по вертикали, горизонтали или диагонали). Следующая задача относится к этой игре.

Задача. [4] Докажите, что при игре в крестики – нолики второй игрок, как бы хорошо он ни играл, не может рассчитывать больше, чем на ничью, если его партнёр играет правильно.

2. Бридж-ит («перебрось мостик!»)

На рисунке показана доска для игры в бридж-ит. Участники игры по очереди проводят вертикальные или горизонтальные линии, соединяющие две соседние точки «своего» цвета: один игрок соединяет синими линиями синие точки, другой – чёрными линями чёрные точки. Линии противников нигде не должны пересекаться. Выигрывает тот, кто первым построит ломаную, соединяющую две противоположные стороны доски «своего» цвета. Так на рисунке выиграли «синие». В этой игре у начинающего игру есть выигрышная стратегия.

Когда вы вдоволь наиграетесь с друзьями в эту игру, можете либо придумать стратегию, либо прочитать о ней в книге М. Гарднера «Математические досуги»

Для игры в солитер нужны игровое поле-доска из 33 клеток и фишки, шашки или монетки. Игра начинается с того, что на все клетки доски, кроме центральной, расставляются фишки. Цель игры состоит в том, чтобы после ряда «прыжков» на доске осталась всего одна фишка. «Прыжок» означает следующее: фишка переносится на свободную клетку через любую соседнюю фишку, которая при этом снимается с доски, причём фишки могут прыгать влево, вправо, вверх и вниз (но не по диагонали!). Каждый ход обязательно должен быть прыжком через фишку. Если очередной ход невозможен, то игра заканчивается.

Прежде чем играть в солитер, можете решить несколько более простых задач из книги М. Гарднера «Математические досуги».

4. Жизнь [11]

Эту игру придумал математик Дж. Конуэй. В неё можно играть одному. Для игры вам понадобится большая доска, разграфленная на клетки, и много плоских фишек двух цветов. Основная идея игры состоит в том, чтобы, начав с какого-нибудь простого расположения фишек, расставленных в разных клетках, проследить за эволюцией исходной позиции под действием «генетических законов» Конуэя, которые управляют рождением, гибелью и выживанием фишек. Вот эти законы.

1. Выживание. Каждая фишка, имеющая две или три соседние фишки, выживает и переходит в следующие поколения. (Соседние фишки – те, которые расположены на соседних клетках: смежных по горизонтали, вертикали или диагонали.)

2. Гибель. Каждая фишка, у которой больше трёх соседей, погибает (то есть снимается с доски) из-за перенаселённости. Каждая фишка, вокруг которой свободны все соседние клетки или занята всего одна клетка, погибает от одиночества.

3. Рождение. Если число фишек, с которыми граничит какая-нибудь пустая клетка, в точности равно трём, то на этой клетке происходит рождение нового «организма», то есть следующим ходом на неё ставится одна фишка.

Важно понять, что гибель и рождение всех «организмов» происходят одновременно. Вместе взятые, они образуют одно поколение – один «ход» в эволюции. Чтобы не запутаться, ходы рекомендуется делать так:

1) начать с конфигурации, целиком состоящей из чёрных фишек;

2) определить, какие фишки должны погибнуть, и положить на каждую из обречённых фишек по одной чёрной фишке;

3) Найти все свободные клетки, на которых должен произойти акт рождения, и на каждую из них поставить по одной белой фишке;

4) Всё проверить, затем снять с доски все погибшие фишки (столбики), а всех новорождённых (белые фишки) заменить чёрными фишками.

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

Глава 6. Интересные факты

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

Факт 1. Пусть выпуклый многоугольник имеет площадь больше 4 и начало координат является его центром симметрии. Тогда этот многоугольник содержит ещё хотя бы одну точку с целыми координатами. ( Теорема Минковского) .

Рис. 1 Эта теорема верна не только для выпуклых многоугольников, но и для выпуклых фигур – фигур, которые с любой парой своих точек содержат и весь отрезок с концами в этих точках. Например, круг и эллипс – выпуклые фигуры, а кольцо – нет.

Смысл этой теоремы состоит в том, что выпуклая фигура, «набирая» площадь 4, не сможет «избежать» захвата узлов сетки. Понятно, что для невыпуклых фигур это не так: они могут «набирать» площадь, «обходя» узлы сетки (рис. 1).

Факт 2. Пусть внутри выпуклой фигуры площади S и периметром 2р лежит узлов решётки. Тогда n > S – р. [10]

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

Кстати, задача о нахождении фигуры наибольшей площади, имеющей данный периметр, давно волновала математиков. Её назвали изопериметрической задачей. Такой фигурой является круг: из всех фигур с данным периметром самую большую площадь имеет он. (рис. 2 и 3)

Величина S – р велика. Площадь мала, а периметр велик.

Узлов много! Узлов нет!

Факт 3. Если вершины выпуклого n-угольника лежат в узлах клетчатой бумаги, а внутри и на его сторонах других узлов нет, то n ≤ 4.

Иными словами, вам ни за что не удастся (попробуйте сами!) нарисовать на клетчатой бумаге выпуклый пяти-, шести-, и т.д. многоугольник с вершинами в узлах сетки так, чтобы ни на его сторонах, ни внутри не было

Рис. 4 других узлов. А вот треугольник или четырёхугольник с таким свойством нарисовать совсем нетрудно!

Конечно, невыпуклые пяти-, шести-, и т.д. многоугольники с таким свойством тоже можно нарисовать (рис. 4).

Факт 4. Из правильных многоугольников только четырёхугольник (квадрат) можно разместить на клетчатом листе так, чтобы все его вершины лежали в узлах сетки. Ни с правильным треугольником, ни с правильным пятиугольником, и т. д., этого сделать нельзя! [2]

(Напомним, что правильным называется многоугольник, у которого все стороны и все углы равны).

Заметим, что квадрат с удобством размещается на клетчатой плоскости не только очевидным образом (когда его стороны Рис. 5

идут по линиям сетки), но и иначе (рис. 5).

В процессе исследования мы изучили много справочной, научно-популярной литературы, побывали на сайтах, вызывающих уважение и некоторое благоговение: малый Мехмат МГУ, ФИПИ, прочитали некоторые книги в электронном виде. Мы рассмотрели различные задачи на построение и вычисления, заданные на клетчатой бумаге, научились применять решение таких задач в различных областях математики, подобрали нестандартные задания. Эти задачи отличаются от обычных задач, изложенных в действующих учебниках и задачниках по математике.

Любители головоломок увлекаются решением задач на клетчатой бумаге, прежде всего потому, что универсального метода решения таких задач не существует, и каждый, кто берётся за их решение, может в полной мере проявить свою смекалку, интуицию и способность к творческому мышлению. Поскольку здесь не требуется глубокое знание геометрии, то любители иногда могут даже превзойти профессионалов-математиков.

Вместе с тем, задачи на клетчатой плоскости не являются несерьёзными или бесполезными, они не так уж и далеки от серьёзных математических задач. Из задач на разрезание родилась теорема Бойаи-Гервина о том, что любые два равновеликих многоугольника равносоставлены (обратное очевидно). Задача на нахождение площади многоугольника с вершинами в узлах сетки сподвигла австрийского математика Пика в 1899 году доказать замечательную формулу Пика.

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

Мы научились вычислять площади многоугольников, нарисованных на клетчатом листке, встретились с совсем новыми, необычными «расстояниями», узнали, как раскраска клеточек помогает решать многие задачи, познакомились поближе с задачами на разрезание и, наконец, научились играть в увлекательные игры на листке бумаги в клетку.

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

Работа по данной теме позволила нам преодолеть психологический барьер и поверить в свои силы, что является важнейшим фактором успешного решения олимпиадных и экзаменационных задач, выступления перед аудиторией с теоретическим материалом по математике.

Мы пришли к выводу, что тема, которая нас заинтересовала, достаточно многогранна, задачи на клетчатой бумаге многообразны, методы и приёмы их решения также разнообразны. Поэтому наша исследовательская группа решила продолжить работу в этом направлении: особенно интересными показались нам задачи на разрезание, «раскраски», задачи на трансформирование, пентамино, разрезание в пространстве. Мы решили составить сборник игр на клетчатой бумаге, которые не только увлекательны и интересны, но и развивают комбинаторно-геометрические навыки, интуицию, воображение.

Список используемой литературы

1. Болотин И. Б., Добрышина Л. Ф. Смоленские математические олимпиады школьников (готовимся к ЕГЭ). Смол. гос. ун-т; Смоленск: СмолГУ, 2008.

2. Геометрия на клетчатой бумаге. Малый МЕХмат МГУ. Режим доступа: /archive/20082009/KanunnikovKuznetsov/2.html

3. Григорьева Г. И . Подготовка школьников к олимпиадам по математике: 5 – 6 классы. Метод. пособие. – М.: Глобус, 2009.

4. Дынкин Е. Б., Молчанов С. А., Розенталь А. Л . Математические соревнования. Арифметика и алгебра. – М.: Наука, 1970.

5. Екимова М. А. ,Кукин Г. П. Задачи на разрезание. М.: МЦНМО, 2002. Режим доступа: /lib/files/pdf/kukin.pdf

6. Жарковская Н. М., Рисс Е. А . Геометрия клетчатой бумаги. Формула Пика // Математика, 2009, № 17, с. 24-25.

7. Задачи открытого банка заданий по математике ФИПИ, 2010 – 2011. Режим доступа: /or/ege/ShowProblems.html?posMask=32

8. Игнатьев Е. И . В царстве смекалки. – М.: Наука, 1982.

9. Кенгуру – 2010. Задачи, решения, итоги. Режим доступа: /load

10. Прасолов В. В . Задачи по планиметрии. – М.: МЦНМО, 2000.

11. Рисс Е. А . Математический клуб «Кенгуру» Выпуск № 8 (изд. второе). – Санкт-Петербург, 2009.

12. Смирнова И. М., Смирнов В. А . Геометрия на клетчатой бумаге. – М.: Чистые пруды, 2009.

13. Смирнова И. М., Смирнов В. А . Геометрические задачи с практическим содержанием. – М.: Чистые пруды, 2010.

14. Смирнов В. А. ЕГЭ. Математика. Задача В6. Планиметрия. Р/т. – М.: МЦНМО, 2011.

15. Трошин В. В. Занимательные дидактические материалы по математике. Сборник заданий. Выпуск 2. – М.: Глобус, 2008.

16. Гарднер М. Математические чудеса и тайны. – М.: Наука, 1986.

Видео:Три способа посадки порежа (ряжи) на рыболовной сети. Легкий способ.Скачать

Клетка и вычисление площади

Россия, г. Иркутск, МБОУ города Иркутска СОШ №11

с углублённым изучением отдельных предметов

СОДЕРЖАНИЕ

Теоретическая часть Историческая справка…………………………………………………стр.3 Формула Пика………………………………………………………….стр.3 Узлы на отрезке………………………………………………………..стр.7 Практическая часть Решение задач………………………………………………………….стр.9 Игры на клетчатой бумаге…………………………………………. стр.12 Заключение……………………………………………………………….стр.14 Список литературы………………………………………………………стр.15 Приложения……………………………………………………………стр.16

Участвуя в Международном конкурсе — игре «Кенгуру», сталкиваешься с задачами, в которых нужно вычислить площадь фигуры. Проблемы, возникающие при решении таких задач, вызваны как сложностью, так и тем, что в школе им уделяется мало времени. А порой их решение носит творческий характер.

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

Введите на клетчатой бумаге систему координат. Отметьте точки А(-2;7), В(1;-2), С(-4;-7), Д(2;-5), Е(3;-8), F(5;-4), G(14;-1), Н(8;2), К(11;8), L(6;3) и соедините их последовательно отрезками АВ, ВС, СД, ДЕ, ЕF, FG, GH, НК, KL, LA. Найдите площадь полученной фигуры.

Учитель математики мне предложила один из выпусков серии «Библиотечка клуба «Кенгуру». В нем рассказывается о формуле Пика, которая позволяет находить площади любых многоугольников с вершинами в узлах клетчатой бумаги.

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

Оказывается, задачи, связанные с бумагой в клеточку, достаточно разнообразны. Я научилась вычислять площади многоугольников, нарисованных на клетчатом листке. Для многих задач на бумаге в клетку нет общего правила решения, конкретных способов и приёмов. Вот это их свойство обуславливает их ценность для развития не конкретного учебного умения или навыка, а вообще умения думать, размышлять, анализировать, искать аналогии, то есть, эти задачи развивают мыслительные навыки в самом широком их понимании.

Предмет исследования: задачи на вычисление площади многоугольника на клетчатой бумаге, методы и приёмы их решения.

Методы исследования: моделирование, сравнение, обобщение, аналогии, изучение литературных и Интернет-ресурсов, анализ и классификация информации.

Цель исследования: вывести и проверить формулы вычисления площадей геометрических фигур с помощью формулы Пика.

Для достижения поставленной цели предусматриваем решение следующих задач:

Изучить литературу по данной теме; Рассмотреть различные способы вычислений площадей многоугольников; Показать практическое применение этих способов; Выяснить преимущества и недостатки каждого способа; Систематизировать и углубить накопленные мной знания; Повысить качество знаний и умений.

Многообразие задач на бумаге в клеточку, их «занимательность», отсутствие общих правил и методов решения вызывают у школьников затруднения при их рассмотрении

Гипотеза: Площадь фигуры, вычисленная по формуле Пика равна площади фигуры, вычисленной по формуле планиметрии.

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

Австрийский математик Георг Александер Пик родился 10 августа 1859 году в Вене. Его отец, будучи руководителем частного института, предпочел до 11 лет обучать мальчика на дому, а потом отдал его сразу в четвертый класс гимназии, окончив которую в 1875 году, поступил в Венский университет.

После защиты диссертации его утверждают на должность ассистента одного из ведущих физиков того времени, профессора Эрнста Маха, являющегося одновременно ректором Карлова университета в Праге — старейшего учебного заведения во всех славянских странах. Постоянно, за исключением поездки в Лейпциг для обучения под руководством Феликса Клейна в 1884-1885 годах, Пик живет и работает в Праге.

В 1900-1901 годах был деканом философского факультета Карлова университета, и в 1911 году Пик оказался во главе комиссии, которая приняла на кафедру математической физика Альберта Эйнштейна. Они становятся близкими друзьями, совершая продолжительные пешие прогулки и беседуя, вместе музицируют.

Среди всего многообразия достижений австрийского математика выделяется формула для вычисления площадей многоугольников с вершинами в узлах клетки. Она стала широко известна только в 1969 году,

после того, как Гуго Штейнгауз включил ее в свою знаменитую книгу «Математический калейдоскоп».

После выхода в 1927 году на пенсию Пик вернулся в свой родной город Вену. Однако после аншлюса (присоединение) 12 марта 1938 года Австрии с Германией ему снова пришлось перебраться в Прагу. В сентябре 1938 года фашистская Германия вторглась на территорию Чехословакии. был брошен в концентрационный лагерь в Терзинштадте, где и умер две недели спустя.

1.2 ФОРМУЛА ПИКА

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

Линии, идущие по сторонам клеток, образуют на нем сетку, а вершины клеток — узлы этой сетки.

Найдем площадь многоугольника с вершинами в узлах (рис.1). Искать ее можно по-разному.

1 способ: с помощью палетки.

способ: попробовать разрезать многоугольник на достаточно простые фигуры, найти их площади и сложить. Однако, это очень хлопотно! способ: вычислю площадь заштрихованной фигуры (рис.2), которая «дополняет» многоугольник до прямоугольника АВСД, и вычту эту площадь из площади АВСД. Заштрихованная фигура (в отличие от исходного многоугольника) легко разбивается на прямоугольники и прямоугольные треугольники, так что ее площадь вычисляется без усилий. Она равна:

1·2+0,5·1·2+0,5·1·1+1·3+0,5·1·4+0,5·1·2+0,5·1·4+0,5·1·3=13 кв. ед.

Следовательно, площадь исходного многоугольника равна 5·6-13=17кв. ед.

Хотя многоугольник и выглядел достаточно просто, для вычисления его площади мне пришлось изрядно потрудиться. Оказывается, площади многоугольников, вершины которых расположены в узлах сетки, можно вычислять гораздо проще: есть формула, связывающая площадь такого многоугольника с количеством узлов, лежащих внутри и на границе многоугольника.

Пусть дан некоторый решётчатый многоугольник, с ненулевой площадью. Обозначим его площадь через S; количество точек с целочисленными координатами, лежащих строго внутри многоугольника — через В; количество точек с целочисленными координатами, лежащих на сторонах многоугольника — через Г.

Тогда справедлива формула S=В+Г:2-1, которую открыл и доказал австрийский математик в 1899 году (1859-1943)

Доказательство проведу в несколько этапов: от самых простых фигур до произвольных многоугольников:

Единичный квадрат. В самом деле, для него S=1, В=0, Г=4, и формула верна.

2.Прямоугольник со сторонами, параллельными осям координат. Для доказательства формулы обозначу через а и b длины сторон прямоугольника.

Тогда нахожу:S=ab , В = (а-1)(b-1), Г=2(а+b). Непосредственной подстановкой убеждаюсь, что формула Пика верна. S= (a-1)(b-1)+a+b-1 = ab

3.Любой треугольник, расположенный на клетчатой бумаге, внутри которого нет узлов, а на его границе узлами являются только вершины треугольника, имеет площадь 0,5 кв. ед. Такие треугольники называются примитивными. Следовательно, справедливо следующее утверждение:

Все примитивные треугольники равновелики и их площади равны половине площади единичного квадрата.

Множество примитивных треугольников разнообразно.

4.Прямоугольный треугольник с катетами, параллельными осям координат. Для доказательства замечу, что любой такой треугольник можно получить отсечением некоторого прямоугольника его диагональю. Обозначу через c число целочисленных точек, лежащих на диагонали. Формула Пика выполняется для такого треугольника, независимо от значения c.

5.Произвольный треугольник. Замечу, что любой такой треугольник может быть превращён в прямоугольник приклеиванием к его сторонам прямоугольных треугольников с катетами, параллельными осям координат (при этом понадобится не более 3 таких треугольников). Отсюда можно получить корректность формулы Пика для любого треугольника.

Остается сделать последний шаг: перейти от треугольников к многоугольникам

6.Произвольный многоугольник. Для доказательства разобью на треугольники с вершинами в целочисленных точках. Для одного треугольника формулу Пика я уже доказала. Дальше, можно доказать, что при добавлении к произвольному многоугольнику любого треугольника формула Пика сохраняет свою корректность. Отсюда следует, что она верна для любого многоугольника.

У меня возник вопрос: а всякий ли многоугольник с вершинами в узлах можно разрезать на такие треугольники?

Если все углы многоугольника меньше 180°, т. е. многоугольник выпуклый, то его можно разрезать на треугольники, например, проведя диагонали, соединяющие одну из его вершин со всеми остальными.

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

Опять вопрос: а выполняется ли формула Пика для невыпуклых многоугольников?

Доказательство этого факта оказалось слишком сложным. Я решила на конкретных примерах проверить формулу Пика для таких многоугольников.

S=0+32:2-1=15 кв. ед S=18+17:2-1=25,5 кв. ед S=0+20:2-1=9 кв. ед

S =0+19:2-1=8,5 кв. ед

1.3 УЗЛЫ НА ОТРЕЗКЕ

Неудобство формулы Пика состоит в том, что уж очень четким должен быть чертеж и очень внимательно нужно его рассматривать, чтобы определить, лежит ли данный узел внутри фигуры или же попал на ее границу. Как точно сосчитать число узлов на границе? Поскольку граница состоит из отрезков, то меня заинтересовал вопрос о количестве узлов сетки, лежащих на произвольном отрезке с концами в узлах. Пусть А и В — узлы сетки. Обозначу через С1 первый узел, встретившийся после А на отрезке АВ (значит, между точками А и С1 больше узлов нет). Построю прямоугольный треугольник АС1Д1 с гипотенузой АС1 и катетами, лежащими на линиях сетки (рис.10).

Если С1≠В, то смещу этот треугольник вдоль отрезка АВ на расстояние АС1. Получу равный ему треугольник С1С2Д2. Следовательно, С2- узел, и между С1 и С2нет узлов. Ясно, что если эту процедуру продолжить, то когда-нибудь в качестве очередной точки Ск+1 можно получить точку В – узел сетки. Рассматривая большой прямоугольный треугольник АRВ с гипотенузой АВ, прихожу к выводу:

АR=(k+1)АД1, ВR=(k+1)C1Д1, АВ=(k+1) АС1 (*)

Сколько же узлов лежит между точками А и В (считаем, что А и В не лежат на одной линии сетки). Построю прямоугольный треугольник АКВ с вершинами в узлах сетки и с гипотенузой АВ (рис.11). Пусть АК =р, BR=q. Очевидно, что p и q — целые положительные числа.

Теорема. Если p и q — взаимно просты, то между А и В на отрезке АВ нет узлов сетки. Если же наибольший общий делитель p и q равен n, где n>1(НОД (p, q)= n>1), то на отрезке АВ между точками А и В расположено ровно (n-1) узлов сетки.

1) Пусть числа p и q взаимно просты. Если между А и В были k узлов (k≥ 1), то, взяв ближайший узел к А узел С1, получу по формулам (*): p=( k+1)АД1, q=(k+1)C1Д1, т. е. p и q имеют общий делитель ( k+1), больший 1. Но ведь они взаимно просты.

2) Пусть НОД(p, q)= n>1. Поделю отрезок АR и ВR на n равных частей, опять прихожу к рис.10, С1,С2,…,Сk — какие-то узлы сетки и k=n-1. Таким образом в этом случае между точками А и В есть хотя бы n-1 узел. Следовательно, если самый большой общий делитель чисел p и q равен n, то между А и В ровно n-1 узел. Зная, это, можно не мучаясь сомнениями с уверенностью сказать, через сколько узлов проходит произвольный отрезок с концами в узлах сетки.

Сколько клеток рассекает на две части диагональ прямоугольника m x n, где m и n взаимно простые числа?

Замечу, что диагональ такого прямоугольника не проходит через узлы. Буду считать, что диагональ идет из левого нижнего угла прямоугольника. Самой первой она рассекает левую нижнюю угловую клетку (клетку №1), потом она попадает в клетку №2 (рис.12), и так далее.

Пусть диагональ уже пересекла k клеток. Так как она ни разу не проходит через узел, то всегда можно однозначно указать, какую клетку она рассечет после клетки с номером k.

Итак, я получила «цепочку», идущую из левого нижнего угла в правый верхний. Мне необходимо понять, чему равно число клеток в этой цепочке. Дам каждой клетке адрес (t;s), если она расположена в горизонтальном ряду с номером t, и вертикальном ряду с номером s. Левый нижний угол получает адрес (1;1) а правый верхний — (m;n). Замечаю, что при переходе от клетки с номером k в нашей цепочке к клетке с номером k+1 сумма чисел t и s в адресе возрастает точно на 1. Значит, чтобы перейти от клетки с адресом (1;1) к клетке с адресом (m;n), надо сделать ровно m+n-2 шагов, пройдя, таким образом, m+n-1 клеток.

Пусть m и n-произвольные натуральные числа. Сколько клеток рассекает диагональ прямоугольника m x n?

Пусть d — НОД (m;n). Очевидно, что вдоль диагонали исходного прямоугольника образуется d маленьких прямоугольников md х nd. Стороны этих маленьких прямоугольников уже взаимно просты, поэтому их диагонали рассекают по md+nd -1 клеток каждая. Значит, диагональ исходного прямоугольника рассечет (md+nd -1)d=m+n-d клеток.

В прямоугольнике m x n диагональ рассекает m + n — НОД(ш;п) клеток.(**)

Например, если m и n взаимно просты — то m+n-1 клеток.

2.1 РЕШЕНИЕ ЗАДАЧ

Введите на клетчатой бумаге систему координат. Отметьте точки А(-2;7), В(1;-2), С(-4;-7), Д(2;-5), Е(3;-8), F(5;-4), G(14;-1), Н(8;2), К(11;8), L(6;3) и соедините их последовательно отрезками АВ, ВС, СД, ДЕ, ЕF, FG, GH, НК, KL, LA. Найдите площадь полученной фигуры.

Используя формулы для вычисления площади прямоугольника и площади треугольника, вычислю площади фигур 1-16.

📽️ Видео

Лепестковый узел | Базовые узлы макрамеСкачать