2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Задачи по комбинаторике
Сообщение12.06.2013, 16:28 
Помогите пожалуйста решить следующие задачи:
1) Каково число матриц из $n$ и $m$ столбцов с элементами из множества $\{0,1\}$?
2) У англичан принято давать детям несколько имён. Сколькими способами можно назвать ребёнка, если ему дадут не более трёх имён, а общее число имён равно 300?
3) Показать, что если $n=300$, то количество целых положительных чисел, не превосходящих $n$ и не делящихся ни на одно из чисел 6,10,15, равно $22m$.

 
 
 
 Re: Задачник по комбинаторике
Сообщение12.06.2013, 16:33 
Аватара пользователя
1) Выпишем все элементы матрицы построчно в одну длинную строку. Сколько в ней чисел?
3) В конце условия используется число $m$, хотя оно нигде не было определено.

 
 
 
 Re: Задачник по комбинаторике
Сообщение12.06.2013, 16:53 
svv в сообщении #735903 писал(а):
1) Выпишем все элементы матрицы построчно в одну длинную строку. Сколько в ней чисел?
3) В конце условия используется число $m$, хотя оно нигде не было определено.




Ничего не понятно

 
 
 
 Re: Задачник по комбинаторике
Сообщение12.06.2013, 17:04 
Аватара пользователя
С третьей задачей -- это я протупил. Претензия снимается.

С первой задачей. В матрице из $n$ строк и $m$ столбцов будет $nm$ элементов. Из них можно составить $nm$-разрядное двоичное число. Например:
$\begin{bmatrix}1&0&1\\0&0&1\end{bmatrix}$ даёт число $101001$.
Отсюда видно, что таких матриц столько, сколько $nm$-разрядных двоичных чисел, то есть... сколько?

 
 
 
 Re: Задачник по комбинаторике
Сообщение12.06.2013, 17:07 
svv в сообщении #735920 писал(а):
С третьей задачей -- это я протупил. Претензия снимается.

С первой задачей. В матрице из $n$ строк и $m$ столбцов будет $nm$ элементов. Из них можно составить $nm$-разрядное двоичное число. Например:
$\begin{bmatrix}1&0&1\\0&0&1\end{bmatrix}$ даёт число $101001$.
Отсюда видно, что таких матриц столько, сколько $nm$-разрядных двоичных чисел, то есть... сколько?


$2mn$?.. :)

 
 
 
 Re: Задачник по комбинаторике
Сообщение12.06.2013, 17:10 
Аватара пользователя
1-разрядные двоичные числа:
0,1
2-разрядные двоичные числа:
00,01,10,11
3-разрядные двоичные числа:
000,001,010,011,100,101,110,111
4-разрядные двоичные числа
0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111
И т.д.

Заметили закономерность? $k$-разрядных двоичных чисел ровно ... сколько?

 
 
 
 Re: Задачник по комбинаторике
Сообщение12.06.2013, 17:12 
PugovKa в сообщении #735913 писал(а):
Ничего не понятно

Совершенно верно, ничего не понятно. Что же это такое -- $m$ в третьей задаче?

 
 
 
 Re: Задачник по комбинаторике
Сообщение12.06.2013, 17:13 
Аватара пользователя
А я уже понял. :wink:

 
 
 
 Re: Задачник по комбинаторике
Сообщение12.06.2013, 17:16 
svv в сообщении #735924 писал(а):
1-разрядные двоичные числа:
0,1
2-разрядные двоичные числа:
00,01,10,11
3-разрядные двоичные числа:
000,001,010,011,100,101,110,111
4-разрядные двоичные числа
0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111
И т.д.

Заметили закономерность? $k$-разрядных двоичных чисел ровно ... сколько?

$2$ в степени $mn$?
А насчёт 3-ей задачи - неправильно написала с учебника:
"Показать, что если $n=30m$, то количество целых положительных чисел, не превосходящих $n$ и не делящихся ни на одно из чисел 6,10,15, равно $22m$."

 
 
 
 Re: Задачник по комбинаторике
Сообщение12.06.2013, 17:20 
Аватара пользователя
Да, правильно, $2^{nm}$.

 
 
 
 Re: Задачник по комбинаторике
Сообщение12.06.2013, 17:23 
svv в сообщении #735933 писал(а):
Да, правильно, $2^{nm}$.

Спасибо :)
а что насчёт 1-ой и 3-ей задач?

 
 
 
 Re: Задачник по комбинаторике
Сообщение12.06.2013, 20:08 
Аватара пользователя
PugovKa писал(а):
Показать, что если $n=30m$, то количество целых положительных чисел, не превосходящих $n$ и не делящихся ни на одно из чисел $6,10,15$, равно $22m$.
Итак, $n$ -- число, кратное $30$, то есть $30, 60, 90, 120$ и т.д.
Вопрос. Рассмотрим множество целых чисел от $1$ до $n$. Сколько чисел из этого множества делится на $10$?

 
 
 
 Re: Задачи по комбинаторике
Сообщение12.06.2013, 20:46 
Аватара пользователя
 i  Тема выделена из архивной темы.
PugovKa, создавайте новые темы здесь в корне, не дописывайте в старые архивные темы сообщения не по теме.
Формулы оформляйте $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике). В случае неоформления тема будет перемещена в Карантин.
Сейчас формулы я поправил.
svv в сообщении #736010 писал(а):
Я не знаю, что делать. Может, Вы создадите новую тему по третьей задаче? (только не здесь, а в корневом разделе "Помогите решить/разобраться (М)") И тогда обсудим.
Спасибо, я отделил :-)

 
 
 
 Re: Задачи по комбинаторике
Сообщение12.06.2013, 21:27 
PugovKa в сообщении #735937 писал(а):
а что насчёт 1-ой и 3-ей задач?

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

 
 
 
 Re: Задачи по комбинаторике
Сообщение12.06.2013, 22:39 
ewert в сообщении #736056 писал(а):
PugovKa в сообщении #735937 писал(а):
а что насчёт 1-ой и 3-ей задач?

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


Тогда получается:
300 в третьей степени + 300 во второй степени + 300 способов? :)

 
 
 [ Сообщений: 23 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group