А и У сидели...

[fortpost]

В каждую клетку прямоугольной таблицы, количество строк которой больше количества ее столбцов, записали букву А или букву У. При этом букву А записали 33 раза, а У — 7 раз, причём вблизи каждой буквы А разместилась ровно одна буква У. (Две клетки считаем близкими, если они имеют общую сторону или вершину.) Все строки, в которых записано хотя бы по одной букве У, вычеркнули. Сколько букв А осталось в таблице?

[Руслан Дехтярь]

Показать скрытый текст

По ходу 24.
Но я тупо нарисовал 3 возможные таблицы: 2 X 20, 4 X 10, 5 X 8
Думаю, есть и другое решение...

[fortpost]

Показать скрытый текст

По ходу 24.
Но я тупо нарисовал 3 возможные таблицы: 2 X 20, 4 X 10, 5 X 8
Думаю, есть и другое решение...

А в авторском решении не столько. Можно ваше посмотреть?

[Руслан Дехтярь]

А-аа..возле каждого А должно быть У...

[Руслан Дехтярь]

Показать скрытый текст

26?

[fortpost]

Показать скрытый текст

26?

Вот это точно!!!

[iPhonograph]

а есть решение без перебора всех таблиц?
несложно доказать, что из 4 возможных размеров таблиц только 2х20 имеет решение, но формулировка задачи намекает на общие рассуждения, подходящие ко всем таблицам сразу

можно доказать, что если длины обеих сторон таблицы больше 3, то количество букв У не может быть простым, и отсечь 4х10 и 5х8, но всё равно не красиво

[Don_Omar]

26?

[fortpost]

а есть решение без перебора всех таблиц?
несложно доказать, что из 4 возможных размеров таблиц только 2х20 имеет решение, но формулировка задачи намекает на общие рассуждения, подходящие ко всем таблицам сразу

можно доказать, что если длины обеих сторон таблицы больше 3, то количество букв У не может быть простым, и отсечь 4х10 и 5х8, но всё равно не красиво

Есть только такое.
Показать скрытый текст

Поскольку 40 = 1x40 = 2x20 = 4x10 = 5x8, то возможны 4 варианта различных таблиц. Рассмотрим их по отдельности

1) В таблице 1 столбец и 40 строк. В этом случае вблизи каждой буквы У может быть не более двух букв А. Но тогда не более чем у 7x2 = 14 букв А вблизи будет буква У - противоречие.

2) В таблице 4 столбца и 10 строк.
Разобьем такую таблицу на 8 частей (жирные линии на рисунке 8 ) и в каждой части одну клетку пометим крестиком. В каждой части непременно должна быть хотя бы одна буква У. В противном случае вблизи буквы А, стоящей в этой части в помеченной крестиком клетке, не будет буквы У, что противоречит условию. Но частей 8, а букв У только 7 - не хватает!

3) В таблице 5 столбцов и 8 строк. Разобьем такую таблицу на 6 частей (жирные линии на рисунке 9). В каждой части должно находиться не более одной буквы У, иначе найдутся буквы А, граничащие с двумя буквами У. Таким образом, в таблице можно разместить не более 6 букв У - противоречие.

4) В таблице 2 столбца и 20 строк. Одна из возможных расстановок букв показана на рисунке 10. Возможны и другие расстановки, однако все они обладают общим свойством: поскольку вблизи буквы У может стоять только буква А, то каждая буква У может стоять только в отдельной строке. После вычеркивания 7 строк с буквой У останется 13 строк с буквой А. Всего останется 26 букв А.

[Питер Пен]

а есть решение без перебора всех таблиц?
несложно доказать, что из 4 возможных размеров таблиц только 2х20 имеет решение, но формулировка задачи намекает на общие рассуждения, подходящие ко всем таблицам сразу

можно доказать, что если длины обеих сторон таблицы больше 3, то количество букв У не может быть простым, и отсечь 4х10 и 5х8, но всё равно не красиво

Есть только такое.
Показать скрытый текст

Поскольку 40 = 1x40 = 2x20 = 4x10 = 5x8, то возможны 4 варианта различных таблиц. Рассмотрим их по отдельности

1) В таблице 1 столбец и 40 строк. В этом случае вблизи каждой буквы У может быть не более двух букв А. Но тогда не более чем у 7x2 = 14 букв А вблизи будет буква У - противоречие.

2) В таблице 4 столбца и 10 строк.
Разобьем такую таблицу на 8 частей (жирные линии на рисунке 8 ) и в каждой части одну клетку пометим крестиком. В каждой части непременно должна быть хотя бы одна буква У. В противном случае вблизи буквы А, стоящей в этой части в помеченной крестиком клетке, не будет буквы У, что противоречит условию. Но частей 8, а букв У только 7 - не хватает!

3) В таблице 5 столбцов и 8 строк. Разобьем такую таблицу на 6 частей (жирные линии на рисунке 9). В каждой части должно находиться не более одной буквы У, иначе найдутся буквы А, граничащие с двумя буквами У. Таким образом, в таблице можно разместить не более 6 букв У - противоречие.

4) В таблице 2 столбца и 20 строк. Одна из возможных расстановок букв показана на рисунке 10. Возможны и другие расстановки, однако все они обладают общим свойством: поскольку вблизи буквы У может стоять только буква А, то каждая буква У может стоять только в отдельной строке. После вычеркивания 7 строк с буквой У останется 13 строк с буквой А. Всего останется 26 букв А.

Из условия задачи следует, что ОДНА буква А может граничить только с ОДНОЙ буквой У. Значит, возле буквы У может находиться только 3, 5 или 8 букв А: 3 – когда буква У в углу таблицы, 5- когда на стороне и 8 – когда на одну и более клеток от стороны. Последний случай не подходит, т.к. при нем букв У могло бы быть только две (33=8*2+5*1+3*4 (2+1+4=7)), а это возможно только в таблице с 5-ю графами, где буква А, принадлежащая одной из 2-х букв У, занимало бы угол, препятствуя использованию всех 4-х троек (а они, как указывалось выше, могут быть только в углу). Следовательно, эта таблица 2х20, где 33=5*6+3*1 (6+1=7).

[GamerPC]

//скрытый текст, требуется сообщений: 3//