Название: А и У сидели...
Отправлено: fortpost от Октябрь 21, 2013, 22:55:24
В каждую клетку прямоугольной таблицы, количество строк которой больше количества ее столбцов, записали букву А или букву У. При этом букву А записали 33 раза, а У — 7 раз, причём вблизи каждой буквы А разместилась ровно одна буква У. (Две клетки считаем близкими, если они имеют общую сторону или вершину.) Все строки, в которых записано хотя бы по одной букве У, вычеркнули. Сколько букв А осталось в таблице?
Название: Re: А и У сидели...
Отправлено: Руслан Дехтярь от Октябрь 22, 2013, 14:33:30
Показать скрытый текст По ходу 24.
Но я тупо нарисовал 3 возможные таблицы: 2 X 20, 4 X 10, 5 X 8
Думаю, есть и другое решение...
Название: Re: А и У сидели...
Отправлено: fortpost от Октябрь 22, 2013, 15:41:07
Показать скрытый текст По ходу 24.
Но я тупо нарисовал 3 возможные таблицы: 2 X 20, 4 X 10, 5 X 8
Думаю, есть и другое решение... А в авторском решении не столько. Можно ваше посмотреть?
Название: Re: А и У сидели...
Отправлено: Руслан Дехтярь от Октябрь 22, 2013, 16:30:07
А-аа..возле каждого А должно быть У...
Название: Re: А и У сидели...
Отправлено: Руслан Дехтярь от Октябрь 22, 2013, 16:51:44
Название: Re: А и У сидели...
Отправлено: fortpost от Октябрь 22, 2013, 19:58:51
Название: Re: А и У сидели...
Отправлено: iPhonograph от Октябрь 27, 2013, 16:25:47
а есть решение без перебора всех таблиц?
несложно доказать, что из 4 возможных размеров таблиц только 2х20 имеет решение, но формулировка задачи намекает на общие рассуждения, подходящие ко всем таблицам сразу
можно доказать, что если длины обеих сторон таблицы больше 3, то количество букв У не может быть простым, и отсечь 4х10 и 5х8, но всё равно не красиво
Название: Re: А и У сидели...
Отправлено: Don_Omar от Октябрь 27, 2013, 19:37:14
26?
Название: Re: А и У сидели...
Отправлено: fortpost от Октябрь 27, 2013, 20:30:30
а есть решение без перебора всех таблиц?
несложно доказать, что из 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 букв А.
(http://s017.radikal.ru/i430/1310/c1/2be67ea496f5.png)(http://s019.radikal.ru/i622/1310/7d/8cff6f4a0140.png)
Название: Re: А и У сидели...
Отправлено: Питер Пен от Октябрь 28, 2013, 01:07:09
а есть решение без перебора всех таблиц?
несложно доказать, что из 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 букв А.
(http://s017.radikal.ru/i430/1310/c1/2be67ea496f5.png)(http://s019.radikal.ru/i622/1310/7d/8cff6f4a0140.png) Из условия задачи следует, что ОДНА буква А может граничить только с ОДНОЙ буквой У. Значит, возле буквы У может находиться только 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).
Название: Re: А и У сидели...
Отправлено: GamerPC от Октябрь 30, 2013, 10:26:39
//скрытый текст, требуется сообщений: 3//
|