Комбинаторика, алгебра и теорвер

[netang]

(Оффтоп)

Наконец-то получил степень бакалавра, появилось свободное время, и я теперь могу доделать эти задачи.

Чтобы было удобнее ориентироваться, решил собрать всё полученное в отдельное сообщение.
=================================================================
1. Рассмотрим последовательность $a_1 = 1$, $a_{n+1} = 2a_n + 1$. Напишите явную формулу для $a_n$ (знаки суммирования и многоточия использовать нельзя).
2. Приведите пример таких двух последовательностей, имеющих конечный предел, что их частное не имеет предела ни конечного, ни бесконечного.
3. Стороны правильного треугольника разбили на $n$ равных частей. Через каждую точку разбиения провели по две прямые, параллельные двум сторонам треугольника. Посчитайте количество треугольников разбиения. Ответ выразите через $n$ без многоточий и знаков суммирования.
4. Сколько существует четырехзначных чисел, все цифры которых различны? (С нуля число начинаться не может.)
5. Дана система линейных уравнений $Ax = b$ с квадратной матрицей $A$ размера $n \times n$, все элементы первой строки этой матрицы равняются $1$, второй строки $2$, …, $n$-ой строки $n$. Чему равняется размерность пространства решений системы уравнений $Ax = b$?
6. Может ли так быть, что определитель квадратной матрицы равен $0$ и остается равным нулю, если к ней прибавить единичную матрицу?
7. Верно ли, что если положительная последовательность стремиться к нулю, то она убывает, начиная с некоторого места?
8. В выпуклом $n$-угольнике посчитайте количество пар пересекающихся диагоналей. Ответ выразить без многоточий и знаков суммирования.
9. На каждой грани кубика написано два числа от $1$ до $6$: одно зеленое, другое красное. Каждое число каждого цвета написано ровно один раз. Кубик бросили так, что все грани выпадают с равной вероятностью. Пусть $p$ – это условная вероятность того, что зеленое выпавшее число четно при условии, что красное число делится на $3$. Найдите вероятность того, что красное число делится на три при условии того, что зеленое число четно.
10. Найдите собственные числа (с учетом кратности) матрицы $10 \times 10$, у которой на двух диагоналях стоят единицы, а все остальные элементы – нули.
=================================================================

1. Предположение: $a_n = 2^n - 1$
Доказательство (при помощи метода математической индукции).
Дано:
$a_{1} = 1$

$a_{n+1} = 2a_n + 1$

$a_{n} = 2^n-1 ?$

Обозначим,
$s_n = \frac{a_{n+1}-1}{2}$
$z_n = 2^n-1$

$s_{1} = z_{1} = 1$

$s_k = z_k$
$z_{k+1} = 2^{k+1} - 1$
$s_{k+1} = \frac{a_{k+2} - 1}{2} = \frac{2^{k+2}-1-1}{2}=2^{k+1}-1$
$z_{k+1} = s_{k+1}$
----------------------------------------------------------------------------
2.
$a_{n} = \frac{\sin(n)}{n}$

$b_{n} = \frac{1}{n}$

$\frac{a_{n}}{b_{n}} = \sin(n)$
----------------------------------------------------------------------------
3. При увеличении $n$ на единицу количество треугольников увеличивается на количество, равное количеству треугольников на предыдущем "слое", плюс два.
Используем формулу суммы арифметической прогрессии для того, чтобы вывести формулу зависящую от $n$, которая задает количество треугольников разбиения.

$S_{n} = \frac{(a_1 + (a_1+d(n-1)))n}{2} = \frac{(1+(1+2(n-1)))n}{2} = n^2$
----------------------------------------------------------------------------
4.

Цитата:

Всего цифр десять ${0, 1, 2, ... 9}$; найдем количество размещений по 4 элемента $A^4_{10} = 5040$. Но в эти размещения также вошли числа $0123, 0124, 0125, ...$; их нужно отсечь. Их количество равно $A^3_9 = 504$ (ноль в качестве цифры уже не учитываем, предполагая, что мы его поставили в начало числа). $A^4_{10} - A^3_9 = 4536$.

----------------------------------------------------------------------------
5. Пятое задание мне не понятно. Допустим, система $Ax = b$ однородна, тогда размерность пространства решений однородной системы мы можем вычислить по формуле $d = n - r$. В нашем случае получается $d = n - 1$.

Теперь, допустим, система неоднородна, тогда возможно только следующее,
$\begin{equation*} \begin{cases} x_1+ ... + x_n = b_1\\ 2(x_1+ ... + x_n) = b_2 = 2b_1\\ ...\\ n(x_1+ ... + x_n) = nb_1 \end{cases} \end{equation*}$
Но я не знаю, как найти размерность пространства решений этой системы.
----------------------------------------------------------------------------
6.

Цитата:

$\begin{vmatrix} \begin{pmatrix} A & B \\ C & D \\ \end{pmatrix} + \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ \end{pmatrix} \end{vmatrix} = 0 ?$
$\begin{equation*} \begin{cases} AD - BC = 0 \\ (A+1)\cdot (D+1) - BC = 0 \end{cases} \end{equation*} \Rightarrow A+D = -1 $
Пробуем подставить: $A = -0.5; B = -0.5$, подгоняем $B = 0.5$ и $C = 0.5$.
Ответ: можно, например, $\begin{pmatrix} -0.5 & 0.5 \\ 0.5 & -0.5 \\ \end{pmatrix} $

----------------------------------------------------------------------------
7. Ответ: неверно, можно взять такую последовательность,

$a_n = |\frac{\sin(\frac{n\pi}{2})}{n}| + |\frac{1}{n}|$

Пусть $n$ - чётное число, следовательно, $n+1$ - нечётное $(1)$
Тогда,
$a_n = \frac{1}{n}$, т.к. $|\frac{\sin(\frac{n\pi}{2})}{n}| = 0$
$a_{n+1} = \frac{1}{n+1} + \frac{1}{n+1} = \frac{2}{n+1}$
Сравним эти члены последовательности, чтобы показать немонотонность.
$\frac{n+1}{n^2+n} < \frac{2n}{n^2+1}$ для всех $n > 0$, удовлетворяющих условию $(1)$
----------------------------------------------------------------------------
8. Одно пересечение мы можем задать с помощью 4-х вершин многоугольника. Нам необходимо подсчитать сколько таких четырехугольников можно соорудить из $n$-вершин многоугольника. Для этого перенумеруем вершины многоугольника и подсчитаем число сочетаний из $n$ по 4. $C_n^4 = \frac{n!}{4!(n-4)!}$
Сейчас придёт ИСН и поругает меня

Deggial: netang, чтобы удобнее было ориентироваться, каждую задачу следует оформлять в отдельную тему. Убедительная просьба запомнить и делать так, иначе темы буду ссылать в Карантин.
Подтема выделена.

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

Убирайте Ваши картинки, набирайте задания в тексте сообщений.

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

[Lia]

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

[grizzly]

netang в сообщении #1026703 писал(а):

Сейчас придёт ИСН и поругает меня

Дайте сначала я на Вас потренируюсь :) Хотя я не так строг.

Задача 1 -- Ок.
Задача 2 -- где доказательство, что последовательность $\sin(n)$ расходится? Почему не взять с той же идеей последовательности попроще?
Задача 4 -- Сколько цифр может быть на первом месте? на втором?... события независимы? Это же в 2 раза короче и в 3 раза проще, нет?
Задача 6 -- Ок, контрпример. А посмотреть случай $3\times 3$ не пробовали?
Задача 7 -- Надо бы показать (или хотя бы сказать), что полученная последовательность сходится к 0. Вообще запись не идеально аккуратная, у Вас кусочки рассуждений остаются в уме -- недосказанными.
Задача 8 -- Ок, но зачем понадобилась титаническая работа по нумерации вершин?

Задачи 3 и 5 ещё не смотрел.

[provincialka]

Хм... А зачем в методе индукции (задача 1) нужно так много обозначений?

[grizzly]

netang в сообщении #1026703 писал(а):

3. При увеличении $n$ на единицу количество треугольников увеличивается на количество, равное количеству треугольников на предыдущем "слое", плюс два.

Я бы предпочёл, чтобы это было объяснено подробнее.

netang в сообщении #1026703 писал(а):

5. Пятое задание мне не понятно. Допустим, система $Ax = b$ однородна

Чем отличается однородная система от неоднородной? Вспомните определения.

[netang]

Цитата:

Задача 2 -- где доказательство, что последовательность $\sin(n)$ расходится? Почему не взять с той же идеей последовательности попроще?

Откопал следующее доказательство.

Brukvalub в сообщении #36547 писал(а):

... нужно использовать несоизмеримость числа пи с 1 и принцип ящиков Дирихле- тогда Вы сможете доказать, что множество частичных пределов этой последовательности состоит из более, чем одной точки, что противоречит сходимости.

Я не очень понял доказательство. Что берется в качестве "кроликов", а что в качестве "клеток"? Имеется ввиду, что натуральные числа это "кролики", а отрезки кратные числу $\pi$ это "клетки"? При этом "кролики" еще "скачут" в этих отрезках при изменении числа $n$? Вы меня убедили в том, что можно было взять что-нибудь попроще для доказательства, например,
$a_{n} = \frac{\sin(n\pi+\frac{\pi}{2})}{n}$
$b_{n} = \frac{1}{n}$
$\frac{a_{n}}{b_{n}} = \sin(n\pi+\frac{\pi}{2})$

grizzly в сообщении #1026776 писал(а):

А посмотреть случай $3\times 3$ не пробовали?

Нет, не пробовал. Попробую. Чую, там что-нибудь квадратичное получится.

grizzly в сообщении #1026776 писал(а):

Задача 8 -- Ок, но зачем понадобилась титаническая работа по нумерации вершин?

Как я себе это представлял, -- чтобы оперировать с вершинами необходимо их как-то пометить, чтобы зафиксировать вершины, чтобы они никуда не "бегали". После чего получаем множество отвечающее вершинам многоугольника из которого легко получить наборы (четырехугольники) из 4 элементов, применив формулу сочетания. Как попроще?

provincialka в сообщении #1026786 писал(а):

Хм... А зачем в методе индукции (задача 1) нужно так много обозначений?

Я не хотел смешивать обозначения в дано и обозначения в доказательстве. Лучше будет $s$ и $z$ не использовать?

grizzly в сообщении #1026789 писал(а):

Чем отличается однородная система от неоднородной?

Когда все свободные члены равны нулю, это однородная система, в противном случае иначе. Еще помнится, что решение неоднородной системы, это общее решение однородной системы $+$ частное решение неоднородной системы.

[Deggial]

Цитата:

Deggial: netang, чтобы удобнее было ориентироваться, каждую задачу следует оформлять в отдельную тему. Убедительная просьба запомнить и делать так, иначе темы буду ссылать в Карантин.
Подтема выделена.

[provincialka]

netang в сообщении #1026807 писал(а):

Я не хотел смешивать обозначения в дано и обозначения в доказательстве.

Да как хотите... Можно и не использовать!

[grizzly]

netang в сообщении #1026807 писал(а):

Я не очень понял доказательство.

[это касалось сходимости $\sin(n)$]
Всё же эта задача на порядок сложнее той, что стояла перед Вами. Я думаю, эта тема слишком перегружена количеством, чтобы отвлекаться на более сложные задачи (этой задаче была посвящена не одна тема на форуме). Поэтому предлагаю Вам вернуться к рекомендации:

grizzly в сообщении #1026776 писал(а):

Почему не взять с той же идеей последовательности попроще?

netang в сообщении #1026807 писал(а):

Как попроще?

[про нумерацию вершин в задаче 8]
Да всё то же самое, просто незачем их нумеровать. Никуда они не сбегут :) Ошибки здесь у Вас нет, но косвенно свидетельствует о некоторой неуверенности Вашего понимания. Ну да ладно, ерунда.

netang в сообщении #1026807 писал(а):

Когда все свободные члены равны нулю, это однородная система, в противном случае иначе.

Пожалуй, здесь мой вопрос был лишним. Из того, что Вы написали по этой задаче следует, что решения существуют только для определённого вида вектора $\mathbf b$. Значит, Вы должны рассмотреть 2 случая, в одном из которых решений нет, а значит и пространства решений в любом случае не существует.
Если же вектор $\mathbf b$ имеет этот самый нужный вид, тогда нам не обойтись без определения того самого пространства решений. Не исключаю, что здесь автор задачи имел в виду количество свободных неизвестных. Но в каком смысле эти решения можно было бы рассматривать как пространство, я сказать не могу.

[netang]

grizzly в сообщении #1026776 писал(а):

А посмотреть случай $3\times 3$ не пробовали?

Попробовал. Можно взять, например, такую матрицу
$A = \begin{pmatrix} -1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ \end{pmatrix} $
Заметил, что если брать матрицы бОльшей размерности и ставить -1 на первое место в матрице ($a_{11}$), а остальные элементы матрицы взять равными нулю, то выполняется $|A+E| = 0$

[grizzly]

netang в сообщении #1026846 писал(а):

Попробовал.

Супер! Ведь получилось найти общего вида контрпример, не особо перетрудившись

[netang]

grizzly в сообщении #1026834 писал(а):

Поэтому предлагаю Вам вернуться к рекомендации:

grizzly в сообщении #1026834 писал(а):

Почему не взять с той же идеей последовательности попроще?

$a_{n} = \frac{\sin(n\pi+\frac{\pi}{2})}{n}$
$b_{n} = \frac{1}{n}$
$\frac{a_{n}}{b_{n}} = \sin(n\pi+\frac{\pi}{2})$

То, что я взял разве не подходит? Ведь $\sin(n\pi+\frac{\pi}{2})$ уже не бегает, непонятно где, как $\sin(n)$, а принимает значения -1 и 1 через раз.

[ИСН]

Много букв, лень вникать. Какие номера ещё не сделаны?

[ewert]

netang в сообщении #1026703 писал(а):

Чтобы было удобнее ориентироваться, решил собрать всё полученное в отдельное сообщение.

(уже было сказано, но я обострю)

Это Вам так, может, и удобнее. Но посторонний читатель, скорее всего, при виде всего этого калейдоскопа попросту на него забьёт. Оно ему нужно, чтоб у него в глазах рябило?...