Подрузамевается, что порядок сообщают при выдаче колпака, тоесть с другими обсудить его нельзя. Мне кажется, что я тоже решил эту задачу по методу что имеем с тем и работаем
Своими словами привожу доказательство Юрика с ЧП о верхней оценке 2^(n-1) - 1 для задачи библиотекаря.
Ищем полуинваринат (откуда название?), который с каждой книгой, перемещаемой на своё место, возрастает и ограничен сверху. Естественно привязать полуинваринат к книгам, находящимся на своих местах. Книги, находящиеся справа от занявшей свое место, могли занять или сойти со своего места при сдвиге вправо. Значит полуинвариант должен обеспечивать рост независимо от того, что произошло справа от книги, занявшей своё место. Такими полуинвариантами являются суммы степеней любого натурального не меньше 2. По существу такие суммы совпадают с системами счисления - двоичная, троичная и т.д. Степень-вес первой (самой левой) книги 1 равна n-2, а у предпоследней книги n-1 степень равна нулю 0, в соответствии с суммой ниже. Единственная среди сумм степеней натуральных, которая могла бы пересчитывать перестановки n книг, если всегда брать книгу с самым ниским весом (n-1, n-2, ...), это сумма степеней двойки 2 (двоичная система счисления). Сумма эта ограничена сверху значением 2^(n-1) - 1, а минимальное значение равно 0. Пересчитать все значения (перестановки книг) от 0 до максимального удаётся лишь для единственного начального беспорядка n, 1, 2, 3, ..., n-2, n-1. Если всегда брать книгу на последнем месте справа, сумма будет последовательно возрастать не больше, чем на 1-цу, дабы после 2^(n-1) - 1 перестановок достичь того же максимума, соответствующего финальной перестановке 1, 2, 3, ..., n-2, n-1, n
На плоскости нарисован параллелограмм, с вершинами в целых точках, и такой, что ни одна целая точка (кроме вершин) не лежит на его сторонах или внутри него. Пример:
Доказать, что площадь любого такого параллелограмма равна 1.
Длина короткой диагонали равна 1, а две другие вершины не могут отстоять больше, чем на один параллельный ряд. Общая площадь оказывается суммой 2-х треугольников с длиной основания = 1 и высотой =1, т.е. общая площадь = 1/2 * 2 = 1. Так подойдет?
Длина короткой диагонали равна 1, а две другие вершины не могут отстоять больше, чем на один параллельный ряд. Общая площадь оказывается суммой 2-х треугольников с длиной основания = 1 и высотой =1, т.е. общая площадь = 1/2 * 2 = 1. Так подойдет?
Нет, не подойдет
Например, вот для такого параллелограмма это не проходит:
Вообще говоря, несложно увидеть, что площадь белой части прямоугольника (состоящей из 2-х больших, 2-х маленьких прямоугольных треугольников и 2-х прямоугольников) равна площади всего прямоугольника - 1. Как это расписать, чтобы было изящно, пока не знаю...
Возьмем для простоты первую точку (0,0)
Соседние вершины будут (x1,y1) и (x2,y2). Вершина, расположенная по диагонали нас пока не интересует.
Всего есть три случая. (y1y2,x1x2) 2 картинка, y1=y2, x1=x2 (1 картинка)
Последние два случая идентичны с точностью до поворота на 90.
Не нарушая общности откинем поэтому случай 2 и будем считать, что y1y2
Тогда S=2*Sтр+Sпар двух треугольников (от 0, x1) и параллелограмма (от x1 до x2)
Переведем проблему в матричную форму. Итак у нас есть целочисленная матрица А, которая отображает единичный квадрат {(0,0)',(0,1)',(1,0)',(1,1)'} на наш параллелограмм. Площадь этого параллелограмма равна детерминанту матрицы d=det(A). Надо доказать, что если внутренние точки квадрата (т.е. все точки квадрата за исключением его вершин) не отображаются в целое число, то d=1. Или, если d1, то есть внутренняя точка, отображаемая в целочислeнный вектор. Итак, пусть d1. Пусть также наши вектора а1=(а11,а21)' и а2=(а12,а22)'.
Если все они делятся на d, то матрица обратного преобразования тоже целочисленная, и может отобразить целочисленные точки только на вершины квадрата, но не внутрь. Если все они на d не делятся, то либо в первой строке, либо во второй, есть число не делящееся нд d. Без потери общности будем считать, что во второй. Тогда, пусть r1 остаток от деления а22 на d, a r2 остаток от деления -а21 на d. Тогда точка r=(r1/d,r2/d)' - внутренняя в единичном квадрате, и А*r - целочислeнный вектор. qed
Что-то я фигню какую-то спорол. Две мысли пересеклись в моей голове с забавными результатами. Конечно-же, если все элементы матрицы делятся на d, то r=(1/d,1/d)' вполне подойдет.
1, Площадь данного паралелограмма - целое число.
2, Замостим достаточно большой кусок плоскости этими паралелограммами, приставленными друг к другу. Получим подобный паралелограм в n раз линеино больший и n**2 по площади. В нём будет n**2 целых точек. Но площадь фигуры на плоскости с достаточно гладкой границей примерно равна числу целых точек(т к граничные эффекты пропорциональны длине границе, а она в нашем случае будет расти линейно, а число целых точек - квадратично_
3. Рассуждение в п 2 можно формализовать так(предполагая для определённости что одна вершина в начале координат и стороны от неё идут вправо и вверх(это мне нужно только для описаня картинки, для других случаев легко изменить)):
Выпустим из левой верхней вершины горизонтальную прямую до пересечения с правой стороной, Отрежем получившийся треугольник и приставим его снизу. Аналогично с получившимся паралеллограммо выпуская верика;нуки прямую из той же вершины вниз. Получим прямоугольник той же площади и с тем же числом целых точек. А для прямоугольника равенство площади числу целых точек очевидно.
P.S. Гм. Получается, что можно прямо резать исходный паралелограмм(только нужны уточнения с + 1)
Доказать, что площадь любого такого параллелограмма равна 1.
А ru.wikipedia.org/wiki/Формула_Пика формулой Пика как бы нельзя пользоваться (разбив параллелограмм на два треугольника)?
То есть надо доказать саму формулу Пика? Или я что-то не понял?
А формулой Пика как бы нельзя пользоваться (разбив параллелограмм на два треугольника)?
То есть надо доказать саму формулу Пика? Или я что-то не понял?
Потому что, насколько я помню, доказательство (по индукции) этой формулы опирается на факт, что площадь любого треугольника с вершинами в целых точках и не содержащего других целых точек внутри или на границе равна 1/2, а это, в свою очередь, выводится из результата про параллелограммы.
Тут похоже надо начинать с прямоугольника в котором вписан наш параллелограмм. Затем надо отломать все прямоугольные треугольники (ниже диагонали параллелограмма) дополняя их до прямоугольников за счет второй половинки (которая выше диагонали). Сложить площадь обломков и должно получится на 1 меньше площади исходного прямоугольника. Расписывать лень, но должно получиться.
РР, а чем Вас не удовлетворяет разрезание, о котором я написал выше? - т е последовательное превращение в прямоугольник? Там не важно, выше или ниже противоположной вершины мы пересекаемся - важно, что получается треугольник, который мы приставляем по равной стороне. И получается новый паралелограм с горизонтальными сторонами, а потом новый - с горизонтальными и вертикальными. В результате получается прямоугольник у которого нет целых точек ни внутри ни на сторонах(кроме вершин), т е единичный квадрат.
Результат удивительный т к кажется, что он противоречит существованию сколь угодно вытянутых параллелограммов с вершинами в целых точках и площадью единица, но это означает только то, что у них есть и целые точки внутри или на сторонах.
Можно сделать замечание, что после разрезов и перекладываний может получит;ся паралелограмм у которого вершины не обязательно в целых точках - но это м б только в промежуточной стадии, после 1-ого разреза и перекладывания - так как площадь исходного паралеллограмма целое число, а целых точек на сторонах и внутри нет по построению.
P.S. Херню написал. Будем думать
Похоже я изложил свое решение слишком пунктирно. Попробую еще раз.
Пусть у нас есть два целочисленных вецтора (а11,а21)' и (а12,а22)'. (' - транспонирование, то есть вектора я буду писать в столбик).
Легко убедиться, что площадь паралеллограма с точностью до знака равна а11*а22-а21*а12 (т.е. определителю d матрицы А={(а11,а21)',(а21,а22)'}), просто на картинке выше из площади прямоугольника вычтете все что не помещается в паралеллограм и получите это значение.
Далее, матрица А отображает единичный квадрат (0 = x,y =1) на наш паралеллограм, и, если мы при d1 найдем внутреннюю точку этого квадрата, которая отображается в целочисленный вектор, то мы решим задачу.
Предположим d1.
Если все элементы матрицы делятся на d, то внутрення точка (1/d,1/d)' отображается в целочисленный вектор и мы нашли целочисленную точку внутри нашего паралеллограма. Если же либо а21 либо а22 не делятся на d, то разделим их на d с остатком, причем поменяем знак у а21: а22 = d*n1 +r1 и -а21 = d*n2 + r2. Точка (r1/d, r2/d)' является внутренней для единичного квадрата, обе координаты строго меньше 1 и по крайней мере одна строго больше нуля.
А теперь посмотрим на точку А*(r1/d, r2/d)', которая по построению находится в паралеллограме, но не является его вершиной. Поскольку d = а11*а22-а21*а12, то
А*(r1/d, r2/d)' = (1-n1*а11-n2*а12, -n1*a21-n2*a22), т.е является целочисленной точкой внутри паралеллограма.
Аналогично поступим, если а21 и а22 делятся на d, а либо а11 либо а12 - не делятся.
Значит d=1.
Пример для наглядности. Пусть наш паралеллограм задан точками (0,0)', (3,7'), (1,3)', (4,10)'.
А = {(3,7)',(1,3)'},
d=2,
r1=r2=1
A*(1/2,1/2)' = (2,5)'.
Если есть бумага в клеточку под рукий, нарисуйте этот паралеллограм и убедитесь, что его площадь равна 2 и точка (2,5) лежит внутри.
Я вот какое решение имел в виду. Предположим, что одна фиксированная вершина параллелограмма P лежит в начале координат, и рассмотрим всевозможные сдвиги P+x, где x пробегает множество целых точек. Тогда нетрудно убедиться, что таким образом мы замостим всю плоскость без перекрытий и дырок:
Но отсюда уже следует, что площадь должна быть равна 1, т.к. если бы она была 1, то обязательно были бы дырки, а если бы 1, то перекрытия.
Собственно, ув. Григорий к этому решению практически и пришел.
Кстати вопрос на засыпку.
В своем первом варианте решения я написал:
Если все они делятся на d, то матрица обратного преобразования тоже целочисленная, и может отобразить целочисленные точки только на вершины квадрата, но не внутрь.
А потом я это решение поправил:
если все элементы матрицы делятся на d, то r=(1/d,1/d)' вполне подойдет
Если посмотреть внимательно, то эти два утверждения противоречат друг другу. Первое утверждает, что искомых точек внутри квадрата нет, а второе приводит пример такой точки. И оба они выглядят верными.
Как разрешить это противоречие?
Извините, при цитировании упустил важную деталь. d - это не любое целое число, а определитель матрицы А.
Собственно, мне вышеприведенное противоречие и увиделось потому что я сам про это забыл. А так, очевидно что все элементы целочисленной матрицы могут делиться на ее определитель только если матрица является скаляром, либо определитель равен по модулю 1.
