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 ] 

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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