07.03.2018 07:42
lany 19 15500 Источник

Дело было вечером, перед сном. Чистил я зубы и устало разглядывал мозаику в ванной. Почему-то меня заинтересовал такой простой факт: если прямоугольник из клеточек 2?3 обвести с двух сторон ещё клеточками, то площадь обводки окажется такой же как площадь прямоугольника:




Голубых квадратиков ровно столько, сколько жёлтых. И тут меня понесло.

Я задумался, а бывают ли ещё подобные конфигурации. То есть чтобы прямоугольник $a \times b$ обвести контуром с двух сторон, и площадь контура совпадала с площадью прямоугольника. Разумеется, $a$ и $b$ должны быть целыми:



Кажется, таких случаев больше быть не должно. Площадь голубой части $a \times b$, а жёлтой — $a + b + 1$. Видно, что если $a$ или $b$ единица, то совпадений не будет, а если увеличивать их больше $2 \times 3$, то голубая будет явно расти быстрее. Так что такая конфигурация одна.


Скучно, сказал мозг. Надо ослабить задачу. Скажем, так:



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



Зафиксируем ширину окантовки. Много ли таких найдётся? Хм. Выглядит интереснее. Жёлтая площадь — это $(x + a)(x + b) - ab$, и нам хочется, чтобы она равнялась просто $ab$. То есть нам (мне и моему мозгу, который меня в это втянул) надо решить уравнение:


$(x + a)(x + b) - ab = ab$


Или, что то же самое:


$x^2 + ax + bx - ab = 0$


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


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

Таким способом легко находится, например, общая формула для всех пифагоровых троек. Кстати, как и с пифагоровыми тройками, в нашей задаче любое количество кратных решений. Например, прямоугольник $4 \times 6$ можно расширить окантовкой в два квадратика и так далее. Разумеется, нам интересны только некратные решения.


Смогу ли я проделать всё это в уме, подумал я, набирая увлажнитель. Алгебра без бумажки и компьютера — довольно коварная штука: перепутал плюс с минусом или забыл какой-нибудь член, и дальнейшие вычисления насмарку. Программисты знают, что делать, чтобы снизить вероятность ошибки — надо обложиться юнит-тестами. К счастью, мы знаем уже одно решение: $x = 1; a = 2; b = 3$. Будем на каждом шагу его проверять.


$1^2 + 2 \times 1 + 3 \times 1 - 2 \times 3 = 0$


Пока всё идёт хорошо. Итак, у нас однородное уравнение — все члены входят во второй степени. Поделим уравнение на $x^2$ (случай $x = 0$ нас не интересует, значит, делить можно):


$1 + \frac a x + \frac b x - \frac a x \times \frac b x = 0$


Делаем замену: $p = a / x; q = b / x$ и получаем уравнение с двумя рациональными переменными:


$1 + p + q - pq = 0$


В нашем юнит-тесте $p = 2; q = 3$, тест проходит. Теперь надо проводить прямую. В принципе её можно проводить как раз через точку $(2; 3)$, но в мозгу это сложно держать. Зато методом пристального вглядывания мы легко можем найти другую точку, которая удовлетворяет уравнению: $p = -1; q = 0$. Это соответствует нулевой площади $a \times b$ и опять же как решение не очень интересно, но для проведения прямой в самый раз. Довольно просто заметить, что все прямые (кроме одной), проходящие через $p = -1; q = 0$, описываются явным уравнением $q = \alpha(p+1)$ (да, почему-то мозг выдал греческую букву, хотя и латинские ещё не кончились). Одна недостающая прямая — это $p = -1$, она тоже не очень интересна нам. Разумеется, любой рациональной точке $(p; q)$, где $p \neq -1$ соответствует рациональная $\alpha$. Например, для точки $(2; 3)$ значение $\alpha = 1$. Подставим уравнение прямой в наше уравнение и получим:


$1 + p + \alpha(p+1) - \alpha p(p+1) = 0$


Или


$1 + p + \alpha p + \alpha - \alpha p^2 - \alpha p = 0$


Или


$1 + p + \alpha - \alpha p^2 = 0$


Или


$\alpha p^2 - p - (1 + \alpha) = 0$


В голове становится сложно приводить члены, мозг отчаянно просит бумажку. Но я убаюкиваю на руках младенца, тут уж не до бумажки. Прогоним юнит-тест ($p = 2; \alpha = 1$):


$1 \times 2^2 - 2 - (1 + 1) = 0$


Фуф, пока всё хорошо. Теперь у нас есть квадратное уравнение относительно $p$, которое вообще-то должно выдать рациональный корень для любого рационального $\alpha$. Как такое может быть, там же дискриминант и всё такое? Ладно, попробуем:


$D = b^2 - 4 a c = 1 ^ 2 + 4 \alpha (1 + \alpha) = 1 + 4 \alpha + 4 \alpha ^ 2 = (1+2 \alpha)^2$


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


$p_{1,2} = \frac {-b \pm \sqrt D} {2 a}$


Или в наших обозначениях:


$p_1 = \frac{1 - (1+2 \alpha)} {2 \alpha} = -1$


$p_2 = \frac{1 + (1+2 \alpha)} {2 \alpha} = \frac{1 + \alpha} \alpha$


$p_1$ — это наша опорная точка, $-1$, это нам неинтересно. Наше решение — это $p_2$. Подставив его в $q = \alpha(p+1)$ получаем ответ:


$p = \frac{1 + \alpha} \alpha; q = 1 + 2 \alpha$


То есть надо просто перебрать все рациональные дроби в качестве $\alpha$, и для них мы получим все рациональные решения уравнения $1 + p + q - pq = 0$ (ну кроме некоторых, которые нам не очень интересны).


Разумеется, перебирать проще целые числа, а не рациональные. Спаивая младенцу препарат симетикона, я подставляю $\alpha = m/n$ и получаю:


$p = \frac{1 + \frac m n} {\frac m n} = \frac {n + m} m$


$q = 2 + \frac m n = \frac {n + 2m} n$


(Боже, мозг, зачем ты выбрал именно $m$ и $n$? Они так легко путаются в голове! Букв мало что ли?) В нашем юнит-тесте, если $\alpha = 1$, то подойдут $m = n = 1$ и легко убедиться, что тест проходит.


Как нам вернуться к целым числам? Вспоминаем, что мы заменили $p = a / x; q = b / x$. Значит, надо принять за $x$ любое число, кратное общему знаменателю из формул выше. В частности, подходит просто $mn$. В итоге имеем:


$x = mn; a = mn + n^2; b = mn + 2m^2$


Видно, что если $m$ и $n$ не взаимно простые, то и решение будет кратно их общему делителю, поэтому нам интересны только взаимно простые $m$ и $n$. Кратное решение также получится, если $n$ окажется чётным. В самом деле пусть $n = 2n'$. Тогда


$x = 2mn'; a = 2mn' + 4n'^2; b = 2mn' + 2m^2$


Если поделить всё на два, то получим


$x = mn'; a = mn' + 2n'^2; b = mn' + m^2$


Это решение симметрично первому, что вполне логично: ведь задача симметрична относительно $a$ и $b$. Таким образом, нам интересны взаимно простые $m$ и $n$, причём $n$ нечётно.


Удобно, что выражение для $x$ получилось таким простым. Значит, у нас есть простой способ найти все некратные решения для заданной наперёд ширины окантовки $x$: это такие прямоугольники $a = x + n^2; b = x + 2(x/n)^2$, где $n$ любой нечётный делитель $x$, взаимно простой с $x/n$. Следующий прямоугольник будет для $x = 2; n = 1; m = 2; a = 3; b = 10$:



И голубая, и жёлтая часть содержат ровно по 30 клеточек!


Давайте посмотрим, какие ещё есть решения для маленьких $x$ ($a$ и $b$ я кое-где переставил, чтобы шли по возрастанию):


x n m площадь без окантовки площадь с окантовкой
1 1 1 2 ? 3 = 6 3 ? 4 = 12
2 1 2 3 ? 10 = 30 5 ? 12 = 60
3 1 3 4 ? 21 = 84 7 ? 24 = 168
3 3 1 5 ? 12 = 60 8 ? 15 = 120
4 1 4 5 ? 36 = 180 9 ? 40 = 360
5 1 5 6 ? 55 = 330 11 ? 60 = 660
5 5 1 7 ? 30 = 210 12 ? 35 = 420
6 1 6 7 ? 78 = 546 13 ? 84 = 1092
6 3 2 14 ? 15 = 210 20 ? 21 = 420

Насчитывая в голове эти произведения, мозг снова добился дозы эндорфина. Как красиво и чудесно делители перетекают из одного числа в другое! Взять, например, $6 \times 55$: первое делится на 6, а второе на 11. Добавляем к обоим числам пятёрку, и чудо — теперь первое делится на 11, а второе — на 6. И такие фокусы в каждой строчке! А тут и сын вроде успокоился. Одиннадцать вечера, можно и спать ложиться.


Возможно, это всё можно посчитать проще. Возможно, мои рассуждения были где-то неточными. Возможно, у этих чисел и произведений есть какое-то специальное название. Я не знаю — не искал. Мне больше вот что интересно: я один такой чушью занимаю своё сознание, или вы тоже этим страдаете наслаждаетесь? Нас вылечат?

Комментарии (19)


  1. AstarothAst
    07.03.2018 11:06
    #10700068
    +3

    Какая у людей жизнь интересная! Вот я когда зубы чищу, то занят в основном тем, что ужасаюсь, какая панда на меня из зеркала смотрит — сама бледненькая-пребледненькая, кружочки вокруг глаз черненькие-пречерненькие…


    1. DanilinS
      07.03.2018 13:53
      #10700386

      Везет Вам. Панда из зеркала смотрит.
      А у меня какой-то страшный мужик пялится. Волосы взъерошены, в глазах — легкое безумие (поработайте инженером с мое), рожа пастой перемазана. Красавчик…


      1. nickko
        08.03.2018 09:38
        #10701224

        Я — минималист. У меня нет зеркала в ванной.
        P.S. Хотя давно уже жене обещал )))


  1. Germanets
    07.03.2018 11:17
    #10700080

    Как же сложно быть математиком — пока чистил зубы — придумал и начал проверять научную теорию…


    1. lany Автор
      07.03.2018 11:19
      #10700082

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


      1. e_Hector
        07.03.2018 11:35
        #10700104

        Читал статью с надеждой, что в итоге все сведется к статическому анализу и IntelliJ IDEA, эх :(


  1. 3dcryx
    07.03.2018 12:23
    #10700206

    Вы были просто удивительно близки к ответу на вопрос "бывают ли еще подобные конфигурации" т.к тройки (k, 2k, 3k) очевидно подойдут. Все решения конечно значительно интересней найти.


    1. lany Автор
      07.03.2018 12:31
      #10700214

      В задаче с окантовкой ширины в одну клетку (и вообще фиксированной ширины) такие тройки не подойдут. А разбирая более общую задачу я это ниже отметил:


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


  1. hdfan2
    07.03.2018 13:37
    #10700358
    +1

    Спасибо за тёплую ламповую статью! Очень напомнило (и содержанием, и слогом) статьи из старого «Кванта» (выписывал в конце 80-х).


  1. kahi4
    07.03.2018 15:41
    #10700536

    Отличное видео про визуализацию пифагорских троек Думаю в данном случае можно найти похожее обобщенное решение


  1. pallada92
    07.03.2018 20:19
    #10700814
    +2

    Если я ничего не напутал и правильно понял постановку задачи, то это можно проще решить:
    image
    Таким образом можно взять любое x, разложить на любые два множителя число image и ответом будет тройка image


    1. pallada92
      07.03.2018 20:54
      #10700850

      Если мы ищем только некратные тройки, то p и q должны быть взаимно простыми (т.к. любой общий делитель x, p + x, q + x является общим делителем p и q). Так как любой простой множитель кроме 2 входит в 2x^2 в четной степени, а двойка — в нечетной (и p и q — взаимно простые), то image, где n — нечетно.
      Таким образом для некратных решений получаем ответ image, где 2m и n взаимно просты, который совпадает с ответом автора.


      1. lany Автор
        08.03.2018 03:40
        #10701122

        Звучит разумно, спасибо за комментарий!


    1. michael_vostrikov
      07.03.2018 21:29
      #10700894

      Проще выразить a через x и b. Тогда можно просто перебирать по порядку.
      a = x + (2*x*x)/(b-x)


  1. DrNefario
    07.03.2018 22:25
    #10700956

    Приходят, если лечь спать на несколько часов раньше обычного.


  1. IIvana
    09.03.2018 04:40
    #10702164

    Моему далекому от Бурбакизма мозгу проще оперировать геометрическими кустарными аналогиями, чем производить формальные символьно-алгебраические преобразования без бумажки. Поэтому (в обозначениях автора) я бы вырезал правый нижний кусок (удалил 2 одинаковых куска разного цвета) и получил бы (заменив разность в-х например с)
    сх + 2хх = са = с(х+щ) (о Боже, мозг, ну зачем ты выбрал щ? наверное потому что так проще набирать не переключая раскладку?)
    откуда со всей очевидностью выходим на сокровенную формулу 2хх = сщ, где задавая любой х можем получить все варианты через факторизацию.


  1. IIvana
    09.03.2018 05:08
    #10702170

    Та же кустарщина с Пифагоровыми тройками: впишем мелкий целочисленный квадрат в угол большого, останется "уголок", из которого тоже должно быть можно сложить полный квадрат. То есть отрезав от каждой "ноги" уголка хвостики, ими можно было заполнить оставшееся пустое место обрезанного уголка до квадрата. При ширине "ноги" х и пропорции отрезания а к б получаем (сразу безо всякой алгебры) волшебную формулу:
    аа = 2бх, что очень похоже на волшебную формулу выше. И так же берем любой четный (по очевидным причинам) полный квадрат (а следовательно четное а), факторизуем его и получаем все тройки, задаваемые данным а. Например:
    а = 2: б = 2, х = 1 — переводя к Пифагору м = а + б = 4, н = а + х = 3, к = а + б + х = 5
    или
    а = 100: бх = 5000, пусть б = 5, х = 1000; тогда м = 105, н = 1100, к = 1105 и т.д., т.е. каждое четное а принесет нам пачку троек. хотя в данном случае тройка получилась кратная, можно сократить на 5 — но если надо отсекать кратные тройки можно предварительно факторизовать а и не группировать в б и х одинаковые составляющие


  1. IIvana
    09.03.2018 06:11
    #10702180

    Из дальнейших попыток поиграться с сабжевой задачей варианты с добавлением такой же площади если приклеивать желтые куски одинаковой ширины с 3 или 4 сторон приводят к тривиальным (не настолько интересным) уравнениям, вариант достройки прямоугольника до квадрата в 2 раза большей площади приводит к ровно такому же сид эквэйшену, как и для Пифагоровых троек, а вариант как у автора, только чтобы желтая площадь была в 2 раза меньше синей решается аналогичными кустарными рассуждениями, приводящими к сид (как это по-русски?) уравнению вида:
    6хх = сщ где а = щ + 2х, б = с + 2х
    например при х = 1 беря с = 3 и щ = 2 получаем а = 4, б = 5 и синяя площадь аб = 20 а желтая площадь (а+х)(б+х) — аб = 30 — 20 = 10 и в 2 раза меньше синей.


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


  1. qeeqeeqee
    09.03.2018 07:45
    #10702192
    +1

    oeis.org/search?q=6%2C30%2C60%2C84&language=english&go=Search