Ладьи в кубе

[moonlight]

те поля на которых стоят ладьи должны простреливаться другими ладьями?
если нет то поставить 5 и 8 можно.

[buka]

те поля на которых стоят ладьи должны простреливаться другими ладьями?
если нет то поставить 5 и 8 можно.

Te поля, на которых уже стоят ладьи простреливаются самими ладьями которые на них стоят, поэтому дополнительно простреливать их не обязательно.
Сколько ладей потребуется для 5*5*5?
Хотелось бы получить оценку общего случая
Вообще-то эта задача достаточно сложная...
Особенно интересно продолжение - для четырёхмерных шахмат и далее - N-мерных...
В последнем случае - даже оценку получить сложно... Не знаю даже, существует ли она, только намётки...

[☭-Изделие 20Д]

А 4-ое измерение - это что? 5-е вроде энергия, тогда выходит 4-е - время

[moonlight]

для 5х5х5 не более 13

[Sirion]

~0.382*K^2

Это оценка сверху или снизу?

[Sirion]

а, ну да
оценка снизу, причём довольно грубая
я думаю, её можно серьёзно приблизить к 0.5

[buka]

а, ну да
оценка снизу, причём довольно грубая
я думаю, её можно серьёзно приблизить к 0.5

У Вас есть обоснование?

[Sirion]

я как раз работаю над этим
проснулся, вдарил вотки и размышляю =)

[Sirion]

да, я практически доказал это
сейчас ещ стопочку, и оформлю

[Sirion]

в общем, тут такая тема
рассмотрим все плоские "слои" нашего куба
пусть минимальное количество ладей на слой -  r
для удобства повернём куб и переставим слои так, чтобы этот слой был нижним
затем переставим перпендикулярные ему слои так, чтобы эти r ладей оказались в одном углу
оптимальным (лень оформлять, но я это доказал, это правда) будет случай, когда ни одна из этих ладей не бьёт другую, т.е. они занимают квадрат r*r
при этом (k-r)^2 полей нижнего слоя этими ладьями не бьётся, т.е. такое количество ладей должно находиться в верхних слоях и бить эти поля
если рассмотреть перпендикулярные слои и вспомнить, что в каждом слое минимум r ладей, можно понять, что в оптимальном случае в параллелепипеде, основание которого - тот самый квадрат с r ладьями, должно быть минимум r^2 ладей (тоже обосновывается несколько более пространно, но я сейчас не осилю)
отсюда ладей минимум (k-r)^2+r^2
отсюда - минимум [k^2/2] (верхняя целая часть)

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

[buka]

Жду с нетерпением. Пока мне не понятен ход Ваших рассуждений...
Кстати, я получил нижнюю оценку в 0.5К², но другим путём

[Sirion]

итак, строгое доказательство:
1) Очевидно, что свойство ладей бить все "клетки" куба инвариантно относительно поворотов куба и относительно перестановок его слоёв
2) Пусть в кубе k*k*k минимальное количество ладей в слое равняется r<=k/2 (случай r>k/2 неинтересен, поскольку даёт слишком большое количество ладей). Путём поворотов и перестановок слоёв добьёмся, чтобы слой с минимальным количеством ладей (один из) оказался нижним
3) Путём перестановок слоёв, перпендикулярных к нижнему (которые, соответственно, порождают перестановки вертикалей и горизонталей нижнего слоя) добьёмся, чтобы все ладьи нижнего слоя оказались в прямоугольнике a*b, один из углов которого совпадает с углом слоя, и при этом на каждой вертикали либо горизонтали, проходящей через прямоугольник. лежит хотя бы одна ладья. Отсюда  a, b<=r.
//это всё была подготовительная часть для большей наглядности
4) Нетрудно понять, что клеток нижнего слоя, которые не бьются ладьями из этого слоя, будет в точности (k-a)(k-b). Эти клетки будут находиться в "дополнении" к прямоугольнику, содержащему ладьи - прямоугольнике, клетки которого не лежат на одной вертикали либо горизонтали с клетками первого прямоугольника. Соответственно, внутри параллелепипеда с основанием в "дополнительном" прямоугольнике и высотой, равной высоте куба, лежит как минимум (k-a)(k-b) ладей, бьющих поля дополнительного прямоугольника.
5) Пусть a>=b. Немного уточним терминологию: вертикалями назовём те ряды нижнего слоя, которые проходят через "прямоугольник с ладьями" в количестве a. Рассмотрим слои, перпендикулярные нижнему и проходящие через эти a вертикалей. По определению числа r, эти слои суммарно содержат не менее ar ладей, причём ни один из них не пересекает параллелепипед, построенный на "дополнительном" прямоугольнике как на основании.
6) Из этого заключаем, что количество ладей в кубе не меньше (k-a)(k-b) + ar.
7) Докажем, что (k-a)(k-b) + ar >= (k-r)^2 + r^2.
Раскроем скобки в обеих частях неравенства, перенесём все члены из правой части в левую. приведём подобные слагаемые. Получим:
2kr - ka - kb + ab + ar - 2r^2 >=0
выделим некоторые общие множители, а также прибавим и вычтем br:
k(r-a)+k(r-b)+ab-br+br+r(a-r)-r^2 >=0
вынесем ещё пару общих множителей:
(k-r)(r-a) + k(r-b) + b(a-r) + r(b-r) >=0
и ещё чуть-чуть:
(k-r-b)(r-a) + (k-r)(r-b)>=0
вспомнив, какими неравенствами связаны наши параметры, понимаем, что значения во всех скобках неотрицательны, что доказывает неравенство
8) Не будем доказывать (полагаю, это должно быть очевидно), что (k-r)^2 + r^2 достигает минимума при r=[k/2] (любая целая часть), и минимум этот - [(k^2)/2] (верхняя целая часть).
9) Бурно радуемся, открываем шампанское, угощаем дам =)

[Sirion]

полагаю, кстати, что ценой некоторых усилий этот результат обобщается на любую размерность больше единицы в виде [k^n-1/(n-1)] (верхняя)

[Sirion]

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

[buka]

Спасибо. Вы утверждаете, что (k-r-b)(r-a) + (k-r)(r-b)>=0, но для этого  (k-r-b) должно быть неотрицательным... Это требует доказательства.
Но нюанс - не в этом.
Допустим, Вам удаётся это доказать.
Тогда Ваше неравенство становится СТРОГИМ, не >=, а > и отсюда общее число ладей ОБЯЗАНО быть больше (k^2)/2... В то же время мы знаем, что для k=2, k=4 можно достигнуть равенства...
Проблематичен Ваш тезис:
"3) Путём перестановок слоёв, перпендикулярных к нижнему (которые, соответственно, порождают перестановки вертикалей и горизонталей нижнего слоя) добьёмся, чтобы все ладьи нижнего слоя оказались в прямоугольнике a*b, один из углов которого совпадает с углом слоя, и при этом на каждой вертикали либо горизонтали, проходящей через прямоугольник. лежит хотя бы одна ладья. Отсюда  a, b<=r.":
а) Путём перестановок Вы сможете всё ладьи нижнего слоя переместить в квадрат с диагональю r
б) При этом ладьи в остальных слоях расползутся как угодно, поэтому меня не убедил Ваш тезис: "6) Из этого заключаем, что количество ладей в кубе не меньше (k-a)(k-b) + ar.", особенно: + ar
-------------------------------------------------------------
Я тоже пришёл к 0.5, но другим путём. Если интересно, могу рассказать