Умнее ли вы 11-классника?

а я их тапком

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

все, нада доску только мелком противотараканьим расчертить ...

42!

Я бы не решил такое в 11 классе. Это вообще фиг знает на что задача. Тупо сидеть варианты придумывать? Так этим пятиклассников обычно мучают.

128!

а я их дустом, ну и что, что запрещён

0 - отстань противный :)

> 128!

Вещества?

>> 128!

>Вещества?

пыщ-пыщ, НЕНАВИСТЬ!!!НЕНАВИСТЬ!!!НЕНАВИСТЬ!!! ??

Внезапно тараканы!!! Тысячи их!!!

>Тупо сидеть варианты придумывать?

Графы рулят!

Хотя можно решить как пазл (подсказка - из углов тараканы точно поползут в соседние клетки например из а1 один таракан точно переползёт в а2 другой в b1)

>> 128!

> Вещества?

биты, товарищ, биты!

32?

> Графы рулят!

И как же они рулят?

> 32?

нет.

>Графы рулят!

Теория графов в 11 классе? вы еб*нулись!

24 клетки

> 24 клетки

Вы можете это доказать?

доказать строго - нет, но мысли такие:
- тараканам нужно ползти навстречу друг другу, чтобы освободить максимум места (отсюда, наверное, можно выдумать какой-нибудь формальный критерий, но лень)
- есть некоторое количество клеток, которые будут заняты в любом случае
- разбиваем доску на квадраты с центром в центре доски и сторонами, равными 2n, где n = {1,2,3,4}, пронумеруем их от 1 до 4 (в зависимости от длины сторон) и тупо перебираем варианты - больше всего клеток остается свободными, если тараканы с внешних клеток 2 и 4 квадрата не будут уходить на внешние клетки других квадратов, а тараканы с внешних клеток квадратов 1 и 3 уйдут на внешние клетки квадратов 2 и 4 (двигаться на внешние клетки большего квадрата выгодннее, чем на внешние клетки меньшего)

как-то так (формализмом и не пахнет, наверняка есть какой-то совсем простой финт ушами)

>> Графы рулят!

>И как же они рулят?

ну например вот так:
http://bash.org.ru/quote/394252

39 клеток

42 точно можно освободить, больше - хз

28

Ненавижу олимпиадные задачи.

а вы не в курсе что тараканы вымерли? в гугле проверьте.

Люди-то хоть живы?

> 28
Это верно, но бездоказательно.
В качестве подсказки привожу частный случай.
0 X X X X X X 0
X X 0 0 0 0 X X
X 0 0 X X 0 0 X
X 0 X 0 0 X 0 X
X 0 X 0 0 X 0 X
X 0 0 X X 0 0 X
X X 0 0 0 0 X X
0 X X X X X X 0

> Люди-то хоть живы?

Нет, слава роботам!

Ну я просто взял участок 3 на 3. Получилось 4 пустых из 9. Для 64 4/9 это примерно 28.

>42 точно можно освободить, больше - хз

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

44?

Для бесконечной или замкнутой доски будет половина, для ограниченой явно меньше. Т.е. не больше 32.

32-4=28

> В качестве подсказки привожу частный случай.

Куда уползли тараканы с клетки d3 (и 3 симметричных)?

+1

>опс, посчитал для одного (таракана в каждой клетке)
короче 2S(угол)+3S(край)+4S(центр)=128 (S - сумма занятых, после передвижения клеток в соотвествующих полях) =>
S(край)>=16 => S(угол)+S(край)+S(центр)>=36, итого, оценка снизу 28 (32 сверху)
пример придумать не могу, а ваш некорректен))

Частный случай:

O X O X O X O X
X X O X O X O X
X X O X O X O X
O X O X O X O X
O X O X O X O X
X X O X O X O X
X X O X O X O X
O X O X O X O X

То, что на бесконечной доске свободными может остаться не более половины
клеток -- очевидно (на любой клетке может собраться не более 4
тараканов). Осталось доказать, что на краевых эффектах доски 8x8
теряется не менее 4-х свободных клеток.

Упс. Тоже облажался.

/me подозревает, что 28 многовато)), кажется что-то не самая простая задача из всеросса))

Угу. 24 - самое оно

>итого, оценка снизу 28 (32 сверху) в смысле оценка _сверху_ 28

аффтар, число или пример!))

36*(2/4)+24*(2/3)+4*(2/2)=38 -столько клеток займут твари.
Пустых, соответсвенно: 64-38=26

Пример в студию! (я в первый раз облажался, 24 видимо все таки)

>36*(2/4)+24*(2/3)+4*(2/2)=38
простовато)), +1 к примеру
по-крайней мере, 26 попадает в достоверный промежуток [24,28]

На бесконечной доске будут свободны 2/3 клеток:

0x00x00x00x0
0x00x00x00x0
0x00x00x00x0
0x00x00x00x0

На 8х8:

0x0000x0
0x0xx0x0
0x0000x0
0x0000x0
0x0xx0x0
0x0000x0
0x0000x0
0x0xx0x0

Бля, я тупой. Это для 1 таракана в каждой клетке

охоххохо
хххооххх
оххооххо
хооххоох
хооххоох
оххооххо
хххооххх
охоххохо

х - клетка занята после перехода, о - свободна. 28 свободно.

ЕГГОГ. У каждого крестика должно быть не менее двух соседей - крестиков.

>ЕГГОГ. У каждого крестика должно быть не менее двух соседей - крестиков.
+1, точнее, у каждой клетки (необ и дост)
to abraziv_whiskey куда ползут насекомые из, скажем, a2? ;)

для одного таракана, вроде 3/4 на бесконечной и >=44 на 8x8
0 0 x 0 0 0 x ...
0 0 x 0 0 0 x ...
x 0 0 0 x 0 0 ...
x 0 0 0 x 0 0 ...
0 0 x 0 0 0 x ...
0 0 x 0 0 0 x ... - 3/4 пустые
=)