|
В квадрате nxn расставлены числа 2; 2^(1/2); 2^(1/3); 2^(1/4); 2^(1/5); … ; 2^(1/20) так, что каждое из этих чисел встречается хотя бы один раз и произведение в каждом столбце и каждой строке целые. Найти наименьшее возможное значение n. задан 20 Янв '14 20:12 
serg55 |
|
Ваше решение неверно. Можно найти намного меньше квадрат. Следует отказаться от того мнения, что все строки и столбца содержат одинаковые элементы с точностью до циклических сдвигов. Вот как можно получить оптимальный квадрат. Берем наибольший простой знаменатель 19. составим из чисел 1/19 квадрат 19х19 и поместим его например в углу будущего квадрата nxn. Назовем этот квадрат ЖЕЛТЫМ. под ним расположите квадрат размером 17х17 из чисел 1/17. Назовем этот квадрат ЗЕЛЕНЫМ. справа под лишними клетками ЗЕЛЕНОГО квадрата поставьте единицы. Справа от ЖЕЛТОГО квадрата расположите СИНИЙ квадрат размером 13х13. Под ним КРАСНЫЙ квадрат размером 11х11, справа от которого для выравнивания с ЖЕЛТЫМ поставим единицы. на этой стадии мы имеем уже прямоугольник размером 36Х24. Ну а дальше подбираем суммы так, чтобы занимать оставшиеся клетки суммами по целым числам. если квадрат не получается - то для этого есть единицы. Потрудитесь, вы получите квадрат меньших размеров, чем 89Х89. И будет вам счастье! отвечен 27 Янв '14 19:20 
nynko |
|
Задача сводится к расстановке дробей вида 1/n в квадрате nxn так что сумма в каждой строке и каждом столбце была целым числом. У меня получается наименьшее число дробей такого вида: 1+1\2+1\3+1\6=1 - четыре дроби 3\5+2\10+3\15+1\20=1 - девять дробей 2\4+1\8+2\16+1\12+1\9+1\18=1 - восемь дробей 6\7+2\14=1 восемь дробей 11\11+13\13+17\17+19\19=4 60 дробей Всего 89 дробей использовано. Если их циклично сдвигать в каждой строке, то и каждая строка и каждый столбец будут содержать необходимое число дробей каждого вида. отвечен 21 Янв '14 0:20 
aid78 @aid78: Извините меня, но я не понял как Вы подбирали именно эти группы дробей и как доказать, что это минимальное количество. Я понимаю, что дроби выбираются так, чтобы в сумме они давали целые числа, но возможно есть ещё набор дробей, отвечающих тем же требованиям. Заранее благодарен.
(21 Янв '14 11:32)
serg55
@aid78: Ещё раз извините, но у Вас ошибки в вычислениях: 1+1/2+1/3+1/6=2; 3/5+2/10+3/15+1/20=1+1/20 - не целое число. Получается, что во втором наборе другое количество дробей, например такое 3/5+1/10+3/15+2/20=1, получается 3+1+3+2=9 дробей, совпало с Вашим результатом, отлично.
(21 Янв '14 13:12)
serg55
1
Дроби 1\11, 1\13, 1\17 и 1\19 невозможно ни с чем скомпоновать, поэтому каждую из них приходится брать максимальное число раз. Дроби 1\7 и 1\14 компонуются тоже только друг с другом. А дальше я честно подбирал. :(
(21 Янв '14 14:57)
aid78
|