2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Способы расстановки цифр в таблице
Сообщение02.11.2019, 10:12 


02/11/19
7
Сколькими способами можно заполнить цифрами 0, 1, . . . , 9
(можно с повторениями) таблицу $3 \cdot 3$ так, чтобы сумма цифр в каждой строке и каждом
столбце равнялась 4? :|
Понятно, что участвовать будут только цифры от 0 до 4, явно надо решать применяя формулы комбинаторики. Но как именно пока не понял.
Пробовал строить дерево возможных вариантов при наличии "3" в таблице, но это явно не то что нужно.
при наличии ряда из 4;0;0 получилось 33 варианта
при наличии ряда из 3;1;0 получилось 108 вариантов
при наличии ряда из 2;2;0 получилось 54 варианта
дальше я понял что случаи с этими вариантами строчек пересекаются, поэтому пробовать решать через них бесполезно. а другого варианта классификации возможных случаев пока не вижу. Возможно, всё получится с другим вариантом разделения вариантов на группы. но придумать его не получается.
Не понятно, как согласовать требования и к строчкам и столбцам для использования формул.

-- 02.11.2019, 10:13 --

 Профиль  
                  
 
 Posted automatically
Сообщение02.11.2019, 11:15 
Заслуженный участник


09/05/12
25179
 i  Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:

- отсутствуют собственные содержательные попытки решения задачи;
- уберите второй экземпляр условия.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 Профиль  
                  
 
 Posted automatically
Сообщение02.11.2019, 13:04 
Заслуженный участник


09/05/12
25179
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»


-- 02.11.2019, 13:13 --

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

 Профиль  
                  
 
 Re: Способы расстановки цифр в таблице
Сообщение03.11.2019, 19:03 


02/11/19
7
Это да, четыре угловые клетки полностью определяют всю расстановку таблицы. Вариантов расставить в них цифры 0,1,2,3,4:
$(5^4-5-5 \cdot4/2 \cdot2)/4+5+5 \cdot4/2=165$
но надо ещё как-то учесть варианты, когда соседние пары цифр в сумме дают более 4. это 4;1 4;2 4;3 4;4 3;3 3;2 надо как-то найти количество расстановок, в которых такие пары присутствуют

 Профиль  
                  
 
 Re: Способы расстановки цифр в таблице
Сообщение03.11.2019, 19:13 
Заслуженный участник


09/05/12
25179
fedro в сообщении #1423757 писал(а):
Это да, четыре угловые клетки полностью определяют всю расстановку таблицы.
Да, например (мне больше нравится блок $2 \times 2$ в одном из углов, но это дело вкуса).
fedro в сообщении #1423757 писал(а):
Вариантов расставить в них цифры 0,1,2,3,4:
$(5^4-5-5 \cdot4/2 \cdot2)/4+5+5 \cdot4/2=165$
Ой ли? Если ограничение по сумме пока не рассматривать, то вариантов будет $5^4=625$. А если учитывать, то нужно еще немного подумать. Допустим, мы сначала задаем два числа в диаметрально противоположных углах таблицы...

 Профиль  
                  
 
 Re: Способы расстановки цифр в таблице
Сообщение03.11.2019, 21:06 


02/11/19
7
165 я получил, отбрасывая варианты, получающиеся друг из друга при повороте таблицы. наверно это не нужно. если не переворачивать, то да, 625. Задавая вначале числа в противоположных углах, получаем 25 возможных пар.

в 9 парах из них максимальная цифра 4, поэтому единственный возможный вариант дозаполнить эти 4 клетки- заполнение нулями-1 вар
в 7 парах максимум 3 значит дозаполняем цифрами 0,1 - 4 вар
в 5 парах максимум 2 значит дозаполняем цифрами 0,1,2 - 9 вар
в 3 парах максимум 1 значит дозаполняем цифрами 0,1,2,3 - 16 вар
в 1 паре оба числа нули значит дозаполняем цифрами 0,1,2,3,4 - 25 вар

$9\cdot1+7\cdot7+5\cdot9+3\cdot16+1\cdot25=155$

-- 03.11.2019, 21:15 --

но у меня здесь явно ошибка, тк не учтено, что если например во всех четырёх клетках нули, в дальнейшем таблицу заполнить явно не удастся. суммы цифр в тех строчках/столбцах, где нет определённых нами клеток окажутся 8 или более, что нам явно не подходит. видимо я какое-то условие пропустил, что посторонние решения получаются.

 Профиль  
                  
 
 Re: Способы расстановки цифр в таблице
Сообщение03.11.2019, 21:21 
Заслуженный участник


09/05/12
25179
fedro в сообщении #1423787 писал(а):
165 я получил, отбрасывая варианты, получающиеся друг из друга при повороте таблицы. наверно это не нужно
Так можно, но, пожалуй, не нужно. Сами себе усложните жизнь.
fedro в сообщении #1423787 писал(а):
Задавая вначале числа в противоположных углах, получаем 25 возможных пар.
Да. Причем эти числа друг с другом не связаны и могут быть любыми.
fedro в сообщении #1423787 писал(а):
но у меня здесь явно ошибка, тк не учтено, что если например во всех четырёх клетках нули, в дальнейшем таблицу заполнить явно не удастся.
Ну скорее не ошибка, а неучет еще одного условия. Но да, его нужно добавить. И вот тут, кстати, стоит вспомнить, что матрицу можно отображать зеркально относительно диагонали (в т.ч. и той, где у нас стоят первые два числа), это позволит упростить поиск четвертого числа по третьему.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Bing [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group