Есть доска, размеченная на клетки N*N. В каждой клетки сидит мышка.
По команде они все перебегают в одну из соседних (по стороне, но не по углу) клеток.
В результате в одной клетке может быть сколь угодно мышек (реально не более 4). На месте мышка остаться после команды не может.

Вопрос сколько много может остаться пустых клеток в зависимости от N?

3/4*N*N

(1) неа...

при N=2 свободных клеток может быть только 2

(0) n*n/2?

В предельном случае N * N - 2. С учетом четных и нечетных клеток. То есть все мыши могут собраться в двух клетках, освободив все остальные. Но не в одной.

да, N*N-2

(4) а если N нечетное?
Команда всего одна!?

(5)(7) х*йня... и провакация...

(8) Про то, что команда всего одна, речи не было. Тогда, естественно, задача немного усложняется.

(0) за один ход?

(10) А как на счет "реально не больше четырех"???

(0) Мышки могут убежать с доски?

При N 3, МАкс свободных 6

(13) за один ход нет

(0) Мышки могут сожрать друг друга?

(13)(16) нет и нет
команда всегда одна

(16) Какая-то нечеткая задача, допускающая бесконечное множество решений, получается.

(0)2n?

(19) N=2 ??? проверять надо

(17)Что значит всегда?) Задачу надо решить после одной команды или при бесконечном числе команд?

(18)Бесконечности нет, а вот вероятность присутствует.

N2-N

n^2-n

Тогда делим квадрат на 3*3...
При н = 3к, н^2/9

а при N==1 что произойдет с мышкой по команде?

(21) после одной команды

(26) N>1

N*N-N

(29) при N=4 не выходит

(0) Мышки могут остаться на месте?

(30) в смысле больше свободных получается?

(29) в каждой клетке не может быть больше 4 => зависимость будет линейная, а не степенная

(20)при n=2 ответ 2 иначе 2n )

(32) меньше ))

тк степень просто перекроет эту четверку

(31) а тебе по-русски там не написано, что НЕТ?

(35) а при 2*2 выходит?

(38)+ хотя неважно :-)

Похоже народ гадает :)

Мышки не могут остаться на месте

Я бы разделил квадрат на 3*4

- - - -          * скопление мышек...
- * * -          - пустая клетка.    
- - - -

(41) Как угловые мышки попадут в центр за один ход?

(41) а куда из угла сбежали???

Прав домовой в (34)

(42) по диагонали

(44) не думаю, при N=4 не выходит

(45) нельзя по диагонали

(44) при n=4 можно сделать 10 свободных

(44)Не прав он)
(46)При n=4 выходит, а вот дальше фигня.
Закономерности вообще тут нет, надо как предложили делить на куски квадрат и там искать стандарт распределения мышек.

получается:
2,3,4,5, 6
2,6,8,15,24

(48)Как?

(50) ага

только 4-10

(50)У меня не так
2,3,4,5,6,7
2,6,8,13,20,35

(50) почему S(4)=8 ?

2 - 2
3 - 3
4 - 10
5 - 15
6 - 24
...
Закономерность уже выяснил, формулы придумываю.

(56)3-6

(54) по колонкам 1->2 3->2
вторая и четвертая колонка по вертикали, освобождая крайние 1->2 2->3 3->2 4->4

(57) А, ну да.

(55) крайние ряды переехали в центральные. Осталось восемь клеток

(56) N*sqr(2)-2N

Как у вас при n=4 получилось 10 свободных???

(53)(56) 4-12

(61) ne-ne

(63)Еще лучше)) тут хз как 10 свободных сделали, а уже 12)))

(54) для 5==15; первые ряд и третий ряд - во второй. Четвертый - в пятый

(62) Из первого и третьего столбца во второй. Второй столбец между собой, последняя колонка в две средних клетки.

1+2+3+..+N, для N>2

(56) что-то типа (n+1)*n/2+...

(63) Как для 4 получилось 12?

(67) а средние в последней колонки где?

(71) Друг с другом поменяются. Не суть важно.

(71) + понял, поменялись местами..

Ненавижу Ненавижу1С

Цел((N*N)/2)

При n = 3k, n^2/3

Для 2-х N(n-1)
Для 3-х N(n-1)
Для 4-х N(n-2)
Для 5-ти N(n-2)
Для 6-ти N(n-3)
Для 7-ми N(n-3)

При n = 3k+1, k*n + (n-2)

Кстати и для единицы работает ;-)

А автор ответ знает?

(77) для 5-ти можно освободить 16 клеток :(

При n = 3k+2, k*n + 2*(n-2)

(80) мне не интересны проблемы с известными мне решениями

(81) Как?

(48) покажи как ты сделаешь 10?

(85) Нельзя, ошибься

(81) ты учитываешь что мышка не должна оставаться на месте?

(85)

ОМОО
ОМОМ
ОМОМ
ОМОО

О - пусто
М - мышки (занято)

Ушел работать

(88) При n = 3k+1, k*n + (n-2)

6 мышек, k*n + (n-2) = 1*4 + (4-2) = 6

ОМООМ
ОМООМ
ОМООО
ОМОММ
ОМООО
К (81)

(88) 5 на 5 вообще-то надо)

(92) в (85) спрашивали про 4*4

т.е. 6 мышек собираются на 2 клетки, так же как и 4. Осталось решить с раскроем большого квадрата на куски 2*3 и 2*2

Вообще имеем шаблон
ОМО
ОМО
который можно крутить и перекрывать по "О". требуется заплонить квадрат N*N

для N%3==0 все просто: 2/3*N^2

(93) эт я переутомился - увидел 5 строк и 4 столбца)))

(96) видимо да, об этом же (76)

Если N/3 без остатка, то = N/3*N*2

упс, уже (96)

Приблизительно так:
Цел(N/3)*N*2 +
ЕслиЧетное(N) + N +
ЕслиНеЧетное(N) + N + 2

Иными словами:
Цел(N/3)*N*2 + (N%3 - 1)*2 + N

Короче, у меня вот что вышло.
Для N = X * 3 результат Z = N * N  * 2 / 3
Для N = X * 3 + 2 результат Z = (N * N - 1) * 2 / 3
X - целое число.
Для N = X * 3 + 1 еще сложнее. Там количество занятых ячеек в последнем столбце будет зависеть от кратности N четырем.

(102) Переделал (потом проверю :))
Для N = X * 3 ====== (N/3)*N*2
Для N = X * 3 + 1 == Цел(N/3)*N*2 + Цел(N/3) + 1
Для N = X * 3 + 2 == Цел(N/3)*N*2 + 2

Обрадовать вас?) при n=5 свободных - 18 )))

при n=6 свободных 26 вроде как.

Короче можно заново начинать думать)

(105) да ладно..

Итак имеем:
 квадрат N*N (N>1)
 ВСЕ мышки из ВСЕХ клеток по команде бегут в соседнюю клетку
 Первый вопрос: если в клетке несколько мышек, они бегут по команде в разные стороны или в одну? Или, вернее, могут ли мышки бежат в одну сторону все вместе? Предположим, что могут.)))
 Постановка вопроса: какое максимальное количество клеток они могут освободить? (Правильно ли я понял?)
Тогда:
 1 случай: N=2;
 Мышки из клеток(1,2), (2,1) бегут в верхнюю левую клетку, мышки (1,1), (2,2) бегут в верхнюю правую клетку, 2 клетки заняты, остальные - свободны. Дальнейшие перемещения количество свободных клеток увеличить не могут.
 2 случай: N>2;
   Часть А:
  Некоторое количество следующих итераций:
   Мышки из первой строчки из каждой клетки бегут вниз в соответствующие клетки второй строчки, остальные бегут вверх. Через (N-1) итераций имеем заполнеными только первые две строчки.
  Часть Б:
   То же самое, только по столбцам, т.е из первого столбца мышки бегут вправо, остальные влево. Через (N-1) итераций имеем заполненными только первые два столбца(вернее, с учетом Части А, заполнены их первые две строчки).
  Итого имеем заполненный квадрат 2*2 в левом верхнем углу,остальные клетки пусты, т.е. задача сведена к случаю N=2, т.е. ответ тот же: 2 клетки заняты, остальные - свободны.
 Так что, окончательный ответ: N*N-2(для N>1), и правильный ответ был дан в самом начале темы)))))
 Если же мышки выбирают направление каждая случайным образом, тогда задача поставлена некорректна и можно говорить только о вероятности того или иного варианта заполнения квадрата. При этом ненулевую вероятность имееют все варианты от 0 до (N*N-2) свободных клеток.

(109)Какие итерации? Один раз команда дается.

Упсс... Тогда сорри, неправильно понял условия)))

(105) Нарисуй как 18 получилось ))

Кстати я понял как при n=4 получилось 12))

Короче принци прост хз как теперь его математически настругать.

OOMOO
MOOOM
MOOMO
OOOMM
OMOOO

(114)Ой не то
OMOMO
OOOOO
MOMOM
OMOMO

(114) куда делась мышка из первого ряда посередине?

А епт опять поспешил
OMOMO
OOOOO
MOMOM
OOOOO
OMOMO

(115) куда делись две мышки из первого ряда, 2 и 4 клетки?

(117) все равно бред и не соответствует условиям

А все понял я скосячил)))

Надо отедльно рассмотреть случаи
n=4k,4k+1,4k+2,4k+3

Для n=4k

(3n^2/4)-n

2:
0 0
2 2
3:
0 3 0
0 4 0
0 2 0
4:
0 3 0 0
0 3 0 2
0 3 0 2
0 3 0 0
Далее можно заметить, что столбцы N*3 (N строк, 3 столбца), наиболее эффективное разбиение. Поэтому, посмотрим, что можно сделать с оставшейся частью:
1. если в остатке - 1
Здесь будут эффективны:
0
2
2
0
1.1 если N - четное (это случаи N=4, 10, 16 и тд)
в остатке либо 0, либо 2. максимальное количество свободных в таком случае равно половине N.
1.2 если N - нечетное (это случаи N=7, 13, 19 и тд)
в остатке либо 3(даст дополнительно 1 пустое поле), либо 1(займет пустое поле и само же освободит).
2. если в остатке - 2
Здесь будет эффективно чередование:
0 0
2 2 (количество в этой строке меняется)
2.1 если N - четное (это случаи N=8, 14, 20 и тд). Получаем N свободных ячеек.
2.2 если N - нечетное (это случаи N=5, 11, 17 и тд).Получаем (N-1)+2 свободных ячеек.

Сложно в какую-то одну формулу свести

Чего тут сводить? Понятно что все мышки могут собраться в две клетки на любой доске от 2x2.
Пусть у мышки изначально координаты x,y
Назовем четными мышками тех, у которых x+y четно, нечетными тех, у кого нечетно.
Возьмем любое число шагов  2*N.
Понятно что любая четная мышка за это число шагов может добраться до любой четной клетки, и любая нечетная мышка до любой нечетной клетки. (если мы можем добраться до клетки за M шагов, то сделав шаг туда-обратно сможем и за М+2).

Выберем любую четную клетку на доске, и любую нечетную.
За N*2 шагов мы легко загоним всех четных мышек в эту четную клетку, а нечетных в выбранную нечтную.

впервые правильный ответ дан в (5) и (7)
задача совсем уж простая.

А, один раз перебегают?
Сейчас, дам ответ.

(125) да-да, всего 1 разик. Причем обрати внимание, что КАЖДАЯ мышка ОБЯЗАНА куда-либо переместиться

(126) Понял. Задача - сколько минимально нужно расставить ладей, которые двигаются только на одну клетку, чтоб все поля доски были биты.

(127) ого как перефразировал.

В случае четной доски на каждую четную вертикаль нужно поставить по N ладей, кроме последней, а на последнюю можно поставить попарно, то есть вот так

00000000
xxxxxxxx
00000000
xxxxxxxx
00000000
xxxxxxxx
00000000
0xx00xx0

в случае нечетной доски вот так

00000
xxxxx
00000
xxxxx
00000

То есть для нечетной доски N*(N-1)/2
А для четной - пара минут, сейчас формулу выведу.

поправка - я пишу сколько минимально может быть занято. Чтоб ответить на вопрос в (0) - нужно это значение вычесть из N*N

(129) по твоему алгоритму: для 6*6
0 0 0 0 0 0
М М М М М М
0 0 0 0 0 0
М М М М М М
0 0 0 0 0 0
0 М М 0 М М
получаем 20 свободных (16 занятых)
однако можно сделать так:
0 0 0 0 0 0
М М М М М М
0 0 0 0 0 0
0 0 0 0 0 0
М М М М М М
0 0 0 0 0 0
получаем 24 свободных (12 занятых)

(131) Наврал я. Конечно ряды ставим не через один, а через два, начиная со второго. Надо посчитать при каких условиях образуется исключительный последний ряд, и сколько в нем получается мышек.

(132) я так и сделал. Только транспонировал)

Если N mod 3 = 0
Тогда мышек N*N/3

Если N mod 3 = 2
Тогда мышек N*(N+1)/3

И самый поганый случай когда N mod 3 = 1

0000000
xxxxxxx
0000000
0000000
xxxxxxx
0000000
0xx0xx0

Хотя чего в нем поганого?
(N-1)/3*2+(N-1)*N/3

образец для первого случая - (131)
Для второго -

00000
ххххх
00000
00000
ххххх

(136) можно же так:
00000
ххххх
00000
00000
хх0хх

(137)ой нет, ошибся

(137) Нельзя.

(136) можно же так:
00000
ххххх
00000
0х0х0
0х0х0

Да, точно - одну клетку для исключительного случая можно сэкономить.

Если N mod 6 = 5, тогда
(N-2)*N/3+(N-1)

Что равно
N*(N+1)/3 - 1

В третьем случае я тоже ошибся - (134)
там другая формула - расположение
0xx00xx0 - пустые клетки кроме краев парно.

в общем, как я понимаю, пришел к тому же, что и у меня в (122). Только я наверное плохо расписал)

вот возможные ситуации, когда N mod 3 = 1
...0xx0
...0xxх0
...0xххх0
...0xx0хх0

Всё в корне неверно, при N стремящемся к бесконечности, количество занятых мышами клеток стремится к N*N/4

0Y000Y000Y000Y0
0X0Z0X0Z0X0Z0X0
Z00Y000Y000Y00Z
Z00X0Z0X0Z0X00Z
0Y000Y000Y000Y0
0X000X000X000X0
Z00Y000Y000Y00Z
Z00X000X000X00Z
0Y000Y000Y000Y0
0X0Z0X0Z0X0Z0X0
0Z0Z000Z000Z0Z0

таким порядком мы можем заполнить всю доску, Z будет максимум на двух крайних рядах

А в центре - на каждые четыре клетки - по одной мыши.

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

Что есть x, y, и z?

(148) не пойму принципа построения (как распространить на случай любого N). к тому же - это поле размерами 15*11 - в нем 108 пустых клеток.
аналогичное поле, заполненное
0X0...
0X0...
...
0X0...
будет содержать больше пустых клеток - 110 клеток

Х - клетки в которые мы собираем четных мышей, Y - нечетных. располагаются вот так -
...............
.x...x...x...x.
...............
...x...x...x...
...............
.x...x...x...x.
...............
...x...x...x...
...............

плотность в центре - одна занятая клетка из четырех.

а во всех предыдущих построениях - одна занятая клетка из трех.

Три алгоритм перемещения мышей для N%3:

0 0 0 0 0
х х х х х
0 0 0 0 0
0 х 0 х 0  <---
0 х 0 х 0  <---

0 0 0 0 0 0
x x x x x x
0 0 0 0 0 0
0 0 0 0 0 0
x x x x x x
0 0 0 0 0 0

0 0 0 0 0 0 0
x x x x x x x
0 0 0 0 0 0 0
0 0 0 0 0 0 0
x x x x x x x
0 0 0 0 0 0 0
0 x x 0 x x 0  <---

Да, кстати, а все сразу сообразили, что у любой заполненной клетки(после команды) по соседству должна быть ещё как минимум одна, т.к. мышке из этой клетки(до команды) тоже нужно куда-то по команде переместиться?

P.S. ТС - ты сволочь! Я всю ночь не спал, мышек из клетки в клетку перегонял...)))

(156) все сообразили
заведи себе женщину

Не путай мягкое с теплым

(0) с доказательством того, что именно такой расклад будет оптимальным задача далеко не так тривиальна...

В (104) мое решение

(160) решение должно включать почему именно данный порядок будет оптимальным. Т.е. доказательство того, что все остальные перемещения не оставят больше пустых клеток.

(161) исходя из (155)

Еще раз повторю - при N стремящемся к бесконечности, в правильном решении число занятых клеток стремится к N*N/4
Исходя из этого - (104) неверно.

Сейчас попробую оптимизировать перебор, и выложить переборное решение.

ТС, ответ будет?

(165) я его не знаю

(166) Программу еще пишу, но практически на 100% уверен что ответа в радикалах не существует, только перебором.

В общем случае:
Цел(2/3*n*n)

(168) Еще раз повторю - при N стремящемся к бесконечности стремится к 3/4*N*N

Прочитай ветку.

Подниму ветку, чтоб не закрылась.

(170) извини, был в отпуске ))

(171) А я из больницы только что выписался :) Ногу сломал.
Теперь "немного  титановый". Завтра дома, мож программку всё-таки напишу.