Страниц: 1 [2] 3 4 ... 6
  Печать  
Автор Тема: Ладьи в кубе  (Прочитано 18375 раз)
0 Пользователей и 1 Гость смотрят эту тему.

Какое максимальное число ладей можно расставить в кубе 8×8×8 так, чтобы они не били друг друга?


Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #15 : Июль 26, 2011, 14:46:36 �

B2, B4,  E5, E7, - неужели не бьют друг-друга Huh?
Да нет же, проблема возникает в третьем слое. B1 перейдёт в В3 и станет бить В3 из первого слоя.
Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
soxjke
Новенький
*
Offline Offline

Сообщений: 10

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 1


Просмотр профиля
Ответ #16 : Июль 26, 2011, 15:04:11 �

...которая уже под боем B1 из первого слоя. Идея ясна...думаю дальше тогда.
Записан
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #17 : Июль 26, 2011, 15:07:43 �

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

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
soxjke
Новенький
*
Offline Offline

Сообщений: 10

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 1


Просмотр профиля
Ответ #18 : Июль 26, 2011, 15:11:56 �

Да в том-то и фишка чтобы без компа... Прогу написать не проблема и отработает она за пару минут.
Записан
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #19 : Июль 26, 2011, 15:18:59 �

soxjke, да ну? Тупой перебор на современном персональном компьютере потребует порядка 5*10150 лет. С оптимизацией это количество, конечно, сократится... Но для сравнения - моя хорошо оптимизированная программа, искавшая расстановки ферзей на плоской доске 8*8, где каждый бьёт ровно четырёх других, работала порядка суток.

С ладьями, конечно, проще в том смысле, что перестановки плоских "поддосок" не влияют на свойства позиции. И всё же меня терзают смутные сомнения...
Последнее редактирование: Июль 26, 2011, 15:21:56 от Sirion Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
soxjke
Новенький
*
Offline Offline

Сообщений: 10

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 1


Просмотр профиля
Ответ #20 : Июль 26, 2011, 15:25:26 �

Ну тогда сейчас попробую..
P.S. Цифра 5*10^150 как получается?
Записан
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #21 : Июль 26, 2011, 15:29:13 �

в уме прикинул
сейчас посчитал на калькуляторе, вышло 1,4171960013891634005130670765903e+137

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

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
soxjke
Новенький
*
Offline Offline

Сообщений: 10

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 1


Просмотр профиля
Ответ #22 : Июль 26, 2011, 15:32:38 �

Это в том случае, если ядро за такт способно проверить состояние куба =)
Записан
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #23 : Июль 26, 2011, 15:35:27 �

Ну, при оценке порядка сложности снизу я обычно делаю подобное допущение. Разница невелика, на самом деле: столько мы не проживём)
Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
soxjke
Новенький
*
Offline Offline

Сообщений: 10

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 1


Просмотр профиля
Ответ #24 : Июль 26, 2011, 16:39:24 �

Не прокатывает решение в лоб =(
Sirion, а как ты располагаешь 76 ладей в кубе, если можно чтобы каждая стояла не более чем под одним боем?
Записан
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #25 : Июль 26, 2011, 17:05:32 �

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

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #26 : Август 17, 2011, 04:57:24 �

Sirion, тогда я Вам дам задачку из этой же серии, но задачка - наоборот:
Каково минимальное число ладей в кубе К *К * К, чтобы ими простреливались все поля?
Трёхмерная ладья ходит в 3-х ортогональных направлениях.
По-моему, эта задача будет поинтереснее...
Записан
Sirion
Гений-Говорун
*
Offline Offline

Сообщений: 1095

СПАСИБО
-вы поблагодарили: 137
-вас поблагодарили: 278



Просмотр профиля Email
Ответ #27 : Август 17, 2011, 09:12:46 �

забавно
я подумаю над этим, когда просплюсь)
Записан

sirion=irion+srion+rion+siion+iion+sion+ion+siron+iron+sron+ron+sion+ion+son+on+sirin+
+irin+srin+rin+siin+iin+sin+in+sirn+irn+srn+rn+sin+in+sn+n+sirio+irio+srio+rio+siio+
+iio+sio+io+siro+iro+sro+ro+sio+io+so+o+siri+iri+sri+ri+sii+ii+si+i+sir+ir+sr+r+si+i+s
moonlight
Умник
****
Offline Offline

Сообщений: 741

СПАСИБО
-вы поблагодарили: 19
-вас поблагодарили: 232


Просмотр профиля Email
Ответ #28 : Август 18, 2011, 00:47:16 �

при k>2 всегда можно k(k-1)
при k=3 точно 6
при k=4 найти меньше 12 не удалось.
Записан

Зачем откладывать на завтра то, что можно отложить на послезавтра?
buka
Гений
*****
Offline Offline

Сообщений: 960

СПАСИБО
-вы поблагодарили: 4
-вас поблагодарили: 120



Просмотр профиля
Ответ #29 : Август 18, 2011, 02:18:08 �

при k>2 всегда можно k(k-1)
при k=3 точно 6
при k=4 найти меньше 12 не удалось.
При К=3, попробуйте 5 ладей...
При К=4 попробуйте 8 или докажите, что 8 не хватит.
При К >> 2 можно и меньшим числом... => ~0.382*K^2
Последнее редактирование: Август 18, 2011, 02:48:29 от buka Записан
Страниц: 1 [2] 3 4 ... 6
  Печать  
 
Перейти в: