Математика. Подготовка к ЕГЭ. Решение задач. https://alexlarin.com/ | |
Натуральное число https://alexlarin.com/viewtopic.php?f=671&t=11829 |
Страница 1 из 2 |
Автор: | atakga [ 22 мар 2015, 13:01 ] |
Заголовок сообщения: | Натуральное число |
Подскажите пожалуйста идею решения этой задачи: Пусть `b(n)` означает количество всевозможных представлений натурального числа `n` в виде `n=a_(0)+a_(1)*2+a_(2)*2^2+...+a_(k)*2^k`, где `a_(i) in {0,1,2}`. Найти `b(1997)`. Спасибо заранее! |
Автор: | michel [ 22 мар 2015, 16:29 ] |
Заголовок сообщения: | Re: Натуральное число |
atakga писал(а): Подскажите пожалуйста идею решения этой задачи: Пусть `b(n)` означает количество всевозможных представлений натурального числа `n` в виде `n=a_(0)+a_(1)*2+a_(2)*2^2+...+a_(k)*2^k`, где `a_(i) in {0,1,2}`. Найти `b(1997)`. Спасибо заранее! Такое представление можно получить, если сначала представить число `1997` в виде суммы двух натуральных чисел, которые в свою очередь записаны в двоичном представлении (где соответствующие степени двоек имеют коэффициенты 0 или 1), тогда при сложении этих слагаемых могут появиться степени двойки с коэффициентом 2. Дальше надо подумать, для каких слагаемых не будут появляться при сложении степени двойки с коэффициентом 2, т.е. соответствующее представление совпадает с обычным двоичным представлением числа `1997` (таких вариантов достаточно много). |
Автор: | alex123 [ 22 мар 2015, 17:02 ] |
Заголовок сообщения: | Re: Натуральное число |
michel писал(а): atakga писал(а): Подскажите пожалуйста идею решения этой задачи: Пусть `b(n)` означает количество всевозможных представлений натурального числа `n` в виде `n=a_(0)+a_(1)*2+a_(2)*2^2+...+a_(k)*2^k`, где `a_(i) in {0,1,2}`. Найти `b(1997)`. Спасибо заранее! Такое представление можно получить, если сначала представить число `1997` в виде суммы двух натуральных чисел, которые в свою очередь записаны в двоичном представлении (где соответствующие степени двоек имеют коэффициенты 0 или 1), тогда при сложении этих слагаемых могут появиться степени двойки с коэффициентом 2. Дальше надо подумать, для каких слагаемых не будут появляться при сложении степени двойки с коэффициентом 2, т.е. соответствующее представление совпадает с обычным двоичным представлением числа `1997` (таких вариантов достаточно много). b(0) = b(1) = 1. n >=0 --> b(2n+1) = ????? b(2n+2) = ????? Потом воспользоваться этой рекурсией и получить результат за 11 шагов. Hint. Чему равно a0 в четном и в нечетном случаях? Как только - так сразу вместо ????? получатся простые формулы. А с двоичным разложением надо думать очень много и качественно, если кто додумает - покажите. Наверное, там придется думать в сторону естественной нумерации дробей из ряда Фарея. |
Автор: | OlG [ 22 мар 2015, 18:33 ] |
Заголовок сообщения: | Re: Натуральное число |
alex123 писал(а): michel писал(а): atakga писал(а): Подскажите пожалуйста идею решения этой задачи: Пусть `b(n)` означает количество всевозможных представлений натурального числа `n` в виде `n=a_(0)+a_(1)*2+a_(2)*2^2+...+a_(k)*2^k`, где `a_(i) in {0,1,2}`. Найти `b(1997)`. Спасибо заранее! Такое представление можно получить, если сначала представить число `1997` в виде суммы двух натуральных чисел, которые в свою очередь записаны в двоичном представлении (где соответствующие степени двоек имеют коэффициенты 0 или 1), тогда при сложении этих слагаемых могут появиться степени двойки с коэффициентом 2. Дальше надо подумать, для каких слагаемых не будут появляться при сложении степени двойки с коэффициентом 2, т.е. соответствующее представление совпадает с обычным двоичным представлением числа `1997` (таких вариантов достаточно много). b(0) = b(1) = 1. n >=0 --> b(2n+1) = ????? b(2n+2) = ????? Потом воспользоваться этой рекурсией и получить результат за 11 шагов. Hint. Чему равно a0 в четном и в нечетном случаях? Как только - так сразу вместо ????? получатся простые формулы. А с двоичным разложением надо думать очень много и качественно, если кто додумает - покажите. Наверное, там придется думать в сторону естественной нумерации дробей из ряда Фарея. `b(1997)=872`. |
Автор: | alex123 [ 22 мар 2015, 18:36 ] |
Заголовок сообщения: | Re: Натуральное число |
OlG писал(а): `b(1997)=871`. Нет, 38. |
Автор: | OlG [ 22 мар 2015, 20:19 ] |
Заголовок сообщения: | Re: Натуральное число |
alex123 писал(а): Нет, 38. Да, 38. Тоже получилось. Из разложение в 2-ую с/с получается (недолгим перебором) еще 37 вариантов представления. |
Автор: | atakga [ 22 мар 2015, 21:35 ] |
Заголовок сообщения: | Re: Натуральное число |
Спасибо всем откликнувшимся! Ниже привожу решение этой задачи. Хотел найти более простую решение задачи с помощью посетителей форума. Принимая во внимание какое значение может получить `a_(0)` получим: `b(2n+1) = b(n)` и `b(2n) = b(n) + b(n-1)`. Для `n=1997` получим `b(1997) = b(998) = b(499) + b(498) = 2b(249) + b(248) = 2b(124) + b(248)` `(1)` `b(62) = b(31) + b(30), ( b(31) = b(15) = b(7) = b(3) = b(1) = 1 ) ==> b(62) = b(30) + 1` `b(124) = b(62) + b(61) = b(62) + b(30) = 2b(30) + 1` `(2)` `b(248) = (2b(30) + 1) + b(123) = 3b(30) + 1` `(3)` Подставляя `(2)`и `(3)` в `(1)` получим: `b(1997) = (4b(30) + 2) + (3b(30) + 1) = 7b(30) + 3` `b(30) = b(15) + b(14) = 1 + b(14) = 1 + b(7) + b(6) = 2 + b(6) = 2 + b(3) + b(2) = 3 + b(2) = 5` Отсюда получим `b(1997) = 7 x 5 + 3 = 38`. |
Автор: | alex123 [ 22 мар 2015, 22:22 ] |
Заголовок сообщения: | Re: Натуральное число |
OlG писал(а): alex123 писал(а): Нет, 38. Да, 38. Тоже получилось. Из разложение в 2-ую с/с получается (недолгим перебором) еще 37 вариантов представления. Так предъявите? И докажите, что 39-го варианта нет. |
Автор: | OlG [ 22 мар 2015, 22:46 ] |
Заголовок сообщения: | Re: Натуральное число |
alex123 писал(а): OlG писал(а): alex123 писал(а): Нет, 38. Да, 38. Тоже получилось. Из разложение в 2-ую с/с получается (недолгим перебором) еще 37 вариантов представления. Так предъявите? И докажите, что 39-го варианта нет. `11111001101` `11111001021` `11111000221` `11110201101` `11110201021` `11110200221` `11110121101` `11110121021` `11110120221` `11110112221...` `02222112221`. |
Автор: | alex123 [ 22 мар 2015, 23:04 ] |
Заголовок сообщения: | Re: Натуральное число |
OlG писал(а): `11111001101` `11111001021` `11111000221` `11110201101` `11110201021` `11110200221` `11110121101` `11110121021` `11110120221` `11110112221...` `02222112221`. Тут пока явно меньше, чем 38 |
Страница 1 из 2 | Часовой пояс: UTC + 3 часа |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |