Спасибо. Вы утверждаете, что (k-r-b)(r-a) + (k-r)(r-b)>=0, но для этого (k-r-b) должно быть неотрицательным... Это требует доказательства.
Не особенно. Эр было взято меньше либо равно ка пополам, Вы ведь не забыли?
Тогда Ваше неравенство становится СТРОГИМ, не >=, а > и отсюда общее число ладей ОБЯЗАНО быть больше (k^2)/2... В то же время мы знаем, что для k=2, k=4 можно достигнуть равенства...
С какой радости? при a=b=r всё обращается в нуль.
Проблематичен Ваш тезис:
"3) Путём перестановок слоёв, перпендикулярных к нижнему (которые, соответственно, порождают перестановки вертикалей и горизонталей нижнего слоя) добьёмся, чтобы все ладьи нижнего слоя оказались в прямоугольнике a*b, один из углов которого совпадает с углом слоя, и при этом на каждой вертикали либо горизонтали, проходящей через прямоугольник. лежит хотя бы одна ладья. Отсюда a, b<=r.":
а) Путём перестановок Вы сможете всё ладьи нижнего слоя переместить в квадрат с диагональю r
б) При этом ладьи в остальных слоях расползутся как угодно, ых координаты не зависит от указанных преобразований.
Тезис самоочевиден. Свойство полей иметь ровно две общих координаты инвариантно относительно указанных преобразований.
Если r ладей в нижнем слое не бьют друг друга, то - да, они помещаются в квадрат r*r. В общем же случае, если какие-то из них друг друга бьют, они суммарно занимают меньшее количество вертикалей/горизонталей, отсюда и прямоугольник a*b.
Да, нас совершенно не волнует, куда "расползаются" ладьи в процессе этого преобразования. Всё, что сказано в доказательстве, относится к уже преобразованному кубу, его исходное состояние нам, мягко говоря, неинтересно.
поэтому меня не убедил Ваш тезис: "6) Из этого заключаем, что количество ладей в кубе не меньше (k-a)(k-b) + ar.", особенно: + ar
Очень жаль, потому что он истинен. У нас есть две непересекающиеся области куба, для каждой из которых доказано нахождение в ней некоторого числа ладей. Следовательно, в сумме куб содержит не менее суммы этих оценок.
Я тоже пришёл к 0.5, но другим путём. Если интересно, могу рассказать
Конечно, интересно. Излагайте.
Мне непонятно как у Вас получился + ar. С a=b=r - согласен, более того, к этому всегда можно свести - к квадрату, где плотно по диагонали стоят r ладей, но как при этом получилось +ar - не пойму. Но это - не суть важно.
Перейду к изложению своего пути.
1. Я решил определить сколько полей простреливается одной трёхмерной ладьёй.
Очевидно, что одиночная трёхмерная ладья в отсутствии остальных простреливает 3k-2 поля независимо от местоположения - по k в каждом из 3-х измерений минус 2, поскольку поле, на котором она стоит нельзя учитывать трижды (под простреливаемыми я понимаю те поля, которые она простреливает плюс поле, на котором находится).
Кстати, независимость числа простреливаемых полей от расположения одиночной ладьи - и есть тот чудодейственный инвариант (с ферзями и слонами у нас бы такое так просто не вышло бы
)
2. Если же ладья не одна, то она тоже простреливает 3k-2 поля, но некоторые из них могут простреливаться и другими ладьями и наша задача - позаботиться о том, чтобы ни одно поле не учитывалось дважды (например если ладьи А и Б пересекают общие поля а и б то, хотя каждая из них по-прежнему простреливает 3k-2 полей, но обе вмете они простреливают не 2*(3k-2) полей, а 2*(3k-2) - 2 поля, т.е. можно сказать, что каждая простреливает 3k-2 - 1 не простреленное до неё поле (одно из дважды простреливаемых полей я вычел у ладьи А и одно - у ладьи Б - просто мне так легче заниматься этой нудной бухгалтерией
)
3. Легко убедиться, что если в кубе со стороной k находятся более k ладей, то обязательно найдутся поля, простреливаемые несколькими ладьями.
4. Пусть r - минимальное число ладей на плоском слое (горизонтальном или двух вертикальных - фронтальном и профильном). Другими словами, мы считаем, что какой бы слой мы ни выбрали бы, в нём будет r или более ладей.
Для простоты будем считать, что это - верхний горизонтальный слой (на самом деле это не имеет никакого значения, просто легче для пространственного воображения)
5. Определим, сколько полей простреливает каждая из r ладей
в этом слое (поля, простреливаемые кратно мы будем учитывать только 1 раз). Легко показать, что это: 2k-r:
каждая ладья простреливает 2k - 1 поле, но каждая из r-1 остальных ладей также простреливает r-1 её полей по одному направлению и r-1 - по другому, то есть у неё 2*(r-1) общих полей с другими ладьями - по 2 с каждой.
Поэтому мы из "счёта" нашей ладьи должны вычесть половину, т.е. r-1. Итого имеем 2к-1-(r-1)=2k-r.
6. Очевидно, что некоторые поля будут простреливаться ладьями и из других слоёв (есть ведь ещё и вертикальная составляющая), но мы учтём это обстоятельство позже.
7. Мы подсчитали, сколько полей простреливает одна ладья (например, ладья А) в горизонтальном слое (т.е. в двух измерениях - фронтальном и профильном (горизонтальный слой имеет фронтальное и профильное направления, фронтальный слой имеет горизонтальное и профильное направления и профильный слой имеет горизонтальное и фронтальное направления). Теперь нам остаётся подсчитать, сколько полей простреливает ладья А в третьем (вертикальном) направлении.
8. Очевидно, что ладья А принадлежит также одному фронтальному и одному профильному слою. Очевидно, что в этих слоях также не менее r ладей и очевидно также, что мы и расчёты можем производить аналогично.
При этом мы получим, что, например и в фронтальном слое она простреливает 2k-r полей в вертикальном и профильном направлениях. Но!!!
а)Поскольку профильное направление мы уже подсчитали в горизонтальном слое, то здесь его надо убрать
b)Общие r полей мы ПОЛНОСТЬЮ вычтем из к (а не половину!!!) - тем самым учитывая пункт 6 (ведь поля, простреливаемые ладьёй А в горизонтальном слое мы записывали на счёт А даже, если они простреливались и в вертикальном направлении, теперь мы должны восстановить справедливость.
Поэтому расчёт в фронтальном слое добавляет k-r (не 2k-r потому что одно направление мы уже учли и не k-r/2, учитывая пункт 6)
c)Профильный слой ничего не добавит, поскольку все направления мы уже подсчитали (в профильном слое будут фигурировать уже подсчитанные направления.
9. Итак, мы имеем, что одна ладья А простреливает 3к-2r полей.
10. Всего у нас общее число ладей R>=kr (в кубе всего к горизонтальных, к фронтальных и к профильных слоёв, в каждом слое - не менее r ладей, но каждая ладья фигурирует в 3-х слоях, поэтому всего ладей - не менее kr, а не 3kr
)
11. Поскольку эти ладьи простреливают все поля, имеем: kr*(3k-2r) <= k
312. Раскрывая скобки сокращая на k, получаем: 2r
2 - 3kr + k
2 >= 0.
Решая его получаем нижнюю границу:
r
min = (3k +- sqrt(9k
2-8k
2)/4 = (3+-1)k/4 = 0.5k. (Второй корень - (1k) - посторонний)
Ранее я получил ошибочный результат, поскольку для третьего измерения принял k-r/2, а не k-r
13. Для 4-х измерений мы получим, что одна ладья А простреливает 4к-3r полей, для 5-ти: 5к-4r, 6-ти - 6к-5r и т.д.
Решая соотв. уравнения мы получим k
N-1/(N-1) для измерения N
Кстати, задача на минимум ладей, простреливающих все поля полностью эквивалентна задаче на максимум взаимно не простреливаемых ладей
