Правильный ответ:
Первым правильное решение предложил
asg_rus, всего через час после публикации условия. Sic!Как справедливо указывает уважаемый
a_shen, условия задачи задают случайное блуждание по двухвершинному графу (матрицу перехода), что делает получение ответа достаточно тривиальным.Однако, я предлагаю облокотиться на теорию цепей Маркова в этот раз и решить задачку посредством аппарата матричной алгебры.
Очевидно, что матрица, удовлетворяющая условию задачи имеет вполне определенный вид:
Найдем ее собственные значения:
Так как матрица у нас вещественнозначная и симметричная, то для нее существует спектральное разложение:
Отсюда тривиально
Ну и
Более того, строки матрицы
Аккуратно проделав все выкладки, найдем, что
Окончательно:
Другое решение?
Предлагаю другое решение.
1. А - не единичная матрица (это тривиальный случай в котором, кстати, 2 нулевых элемента, т.е. не строго положительны)
2. | det A| < 1
3. lim | det A^n | = lim ( | det A |^n )= 0
4. Строки (и столбцы) предельной матрицы (вырожденной) - совпадают и сумма эл-тов строки (столбца) = 1 ==> все эл-ты = 1/2
Re: Другое решение?
Не до конца ясно, откуда следует 4 (хотя постфактум - это верно).
Re: Другое решение?
Матрица (предельная) вырождена, значит строки линейно зависимы
Если первая строка ( а в ), то вторая - ( k*а k*в )
Сумма элементов = 1 (для обеих строк) значит k = 1
Обе строки - ( а в ), ( а в ).
Сумма элементов столбцов = 1 значит а = в = 1/2
Re: Другое решение?
>Сумма элементов = 1 (для обеих строк)
вот это откуда следует.
Re: Другое решение?
"Тарапыцца нада нэт"
В общем, кажется, я отдельно (только что) доказал, что для предельной матрицы этот факт имеет место быть (но 1 - еще себя не перепроверил; 2 - изящество из-за необходимости этого доказательства и его длины ушло напрочь). Так что свой коммент считаю неудачным.
Сорри.
Re: Другое решение?
Re: Другое решение
Да, так вот, доказательство. Матрица А, симметричная, первая строка (а 1-а), в квадрате дает также симметричную матрицу с первой строкой (1+2*а*а-2*а 2*а-2*а*а). То есть, с тем же свойством сумма элементов строки (столбца)= 1.
Соответственно, и в любой четной степени (пардон, в степени вида 2^n) матрица А также будет обладать тем же свойством.
Значит и предельная - такая же (если предел существует, что тоже надо доказывать, разумеется).
Вроде бы так...
А за задачку (не только эту) - всё равно, спасибо.
Re: Другое решение
Комбинируя решение, которое привел я, с вашим подходом, целиком получится следующее: не будет необходимости искать конкретный вид матрицы S. Зато потребуются рассуждения об определителе и об особых свойствах степени двойки.
PS. Поторопился чуток, да.
Edited at 2014-07-12 06:44 pm (UTC)
Доказательство сходимости
1) для любой начальной А (заданного условием вида (а 1-а)) предельная матрица S существует (но, пока, если рассматривать предел не по всем натуральным n, а по степеням двойки)
2) Эта S состоит из 4-х элементов по 0.5.
3) Любая исходная матрица А при умножении на S даёт... S (проверяется умножением)
4) Если опять идти по степеням двойки, то А ^ (2^n) = S + [Нечто малое (n)]
5) Это [Нечто малое (n)] уходит в ноль при росте n
6) Соответственно, для промежуточных степеней матрицы А получаем
А ^ k = S + [Нечто малое (n)] * A ^ (k - 2^n)
7) Последняя добавка ( [Нечто малое (n)] * A ^ (k - 2^n) ) уходит в ноль при соответствующем уходе пары (k, n) в бесконечность. Последний тезис тоже можно (нужно) развить и обосновать подробней, но... надо ли... от исходно красивого доказательства и так почти ничего не осталось (в плане красоты)