Автор Тема: объясните решение пожалуйста  (Прочитано 2052 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн svetnt

  • Новичок
  • *
  • Сообщений: 35
    • Просмотр профиля
объясните решение пожалуйста
« : 14 Сентябрь 2014, 19:42:29 »
Здравствуйте! Объясните пожалуйста кто может. Есть задача с решением, которое никак не доходит до меня.
Задача: В стро­ку под­ряд на­пи­са­но 1000 чисел. Под каж­дым чис­лом a пер­вой стро­ки на­пи­шем число, ука­зы­ва­ю­щее, сколь­ко раз число a встре­ча­ет­ся в пер­вой стро­ке. Из по­лу­чен­ной таким об­ра­зом вто­рой стро­ки ана­ло­гич­но по­лу­ча­ем тре­тью: под каж­дым чис­лом вто­рой стро­ки пишем, сколь­ко раз оно встре­ча­ет­ся во вто­рой стро­ке. Затем из тре­тьей стро­ки так же по­лу­ча­ем четвёртую, из четвёртой — пятую, и так далее.
а) До­ка­жи­те, что не­ко­то­рая строч­ка сов­па­да­ет со сле­ду­ю­щей.
б) До­ка­жи­те, что 11‐я стро­ка сов­па­да­ет с 12‐й.
Ре­ше­ние.
а) Оче­вид­но, что на­чи­ная со вто­рой строч­ки, все числа в таб­ли­це не боль­ше 1000. Кроме того, каж­дое число не боль­ше на­пи­сан­но­го под ним. По­это­му сумма чисел в тре­тьей строч­ке не мень­ше, чем во вто­рой и т.д., и каж­дая из этих сумм не боль­ше мил­ли­о­на. Сле­до­ва­тель­но, по­сколь­ку все время суммы воз­рас­тать не могут, в каких-то со­сед­них строч­ках суммы сов­па­дут, а тогда сов­па­дут и сами строч­ки.

б) До­ка­жем, что если в m-ой строч­ке при m>=2 число от­лич­но от на­пи­сан­но­го над ним, то оно не мень­ше, чем 2 в степени (m-2). Дей­стви­тель­но, для m=2 это оче­вид­но, так как все числа вто­рой стро­ки на­ту­раль­ные. Пусть это уже про­ве­ре­но для всех строк с но­ме­ра­ми, мень­ши­ми . Пусть это уже про­ве­ре­но для всех строк с но­ме­ра­ми, мень­ши­ми m. Пусть в m-ой строч­ке на­пи­са­но число A, а под ним на­пи­са­но число B боль­шее A. Тогда в (m-2)-ой строч­ке на­пи­са­но B чисел, рав­ных A. Ясно, что в (m-2)-ой строч­ке будет на­пи­са­но не­сколь­ко групп оди­на­ко­вых чисел, по A в каж­дой груп­пе, при­чем числа из раз­ных групп раз­лич­ны.  :o  :(  :surrender:  От­сю­да вы­те­ка­ет, что B де­лит­ся на A, то есть B>=2A. Кроме того, по край­ней мере одно из чисел в этих груп­пах от­ли­ча­ет­ся от A, зна­чит, по пред­по­ло­же­нию ин­дук­ции A>=2 в степени (m-1)-2. Итак, B>=2A>=2 в степени (m-2). Наше утвер­жде­ние до­ка­за­но по ин­дук­ции для всех m>=2. Если пред­по­ло­жить, что 11-я строч­ка от­лич­на от 12-й, то какое-то число в 12-й строч­ке будет боль­ше, чем 2 в степени (12-2), то есть 1024>1000, что не­воз­мож­но.[/color]

В решении части а) всё понятно. А вот в части б) никак не доходит до меня то, что после смайликов. "Отсюда вытекает что В делится на А...". Да почему делится-то?