35
«КВАНТ»
ДЛЯ
М ЛАДШИХ
ШК О ЛЬНИК О В
Добрыня и куча камней
В.КЛЕПЦЫН
НА МАТЕМАТИЧЕСКОМ КРУЖКЕ УЧИ- тель только что закончил записывать условие задачи: Есть куча из 1001 камня. Каждый раз, когда богатырь Добрыня делит кучу камней на две, царь платит ему столько монет, каково произведение количеств камней в двух получившихся кучах. Как должен действовать Добрыня, чтобы получить как можно больше?
И сразу ученики заспорили. – Ясно, что первым делом нужно поделить кучу почти пополам: тогда Добрыня сразу получит аж 500•501 монет. Потом меньшие кучи поделим еще пополам и т.д. А нам нужно будет весь этот заработок сложить. Только вот как? – сказала Женя. – А кто тебе сказал, что этот путь самый выгодный? Пару раз сорвет куш, а потом будет он у тебя, скажем, десятимонетные кучки пополам делить, по 25 монет за раз получая. А у меня Добрыня по одному камню брать будет. Тысяча монет на первом ходу, 999 на втором, 998 на третьем… Тише едешь – дальше будешь! – ответил ей основательный Мика. – Это что же, нам сейчас нужно будет все это складывать, чтобы сравнить? – Перспектива вычислять сумму тысячи слагаемых Женю явно не обрадовала. – Не торопитесь, – вмешался учитель. – Вы еще не «вжились» в задачу. Не спеши-
DOI: https://doi.org/10.4213/kvant20190104
те отвечать именно на заданный вопрос, попробуйте ее «покрутить» и поэкспериментировать, поймите, что происходит. – Поэкспериментируешь тут, когда каждый раз тысячу чисел складывать надо, – не согласилась Женя. – Правильно. Поэтому для начала измените задачу. Число 1001 слишком большое, возьмите число поменьше и разберитесь с ним. А там, глядишь, и на исходный вопрос ответите. – Один – замечательное число! Один камень в куче, делать ничего не надо, красота! Правда, и заработать у Добрыни не выйдет, – откликнулся на это предложение Мика. – Два камня принесут Добрыне одну монету, тут без вариантов. А если их три, то 2 + 1 = 3 монеты, – подхватила эстафету обрадовавшаяся Женя.
– Пусть теперь камней четыре. Если Добрыня поделит их пополам, а потом кучки опять пополам, как ты предлагаешь, то заработает 2 2 1 1 1 1 4 1 1 6 монет, – продолжил Мика. – А если будет оттаскивать по одному камню, как предлагаешь ты, то 3 + 2 + 1 = = 6. Опять 6 монет! – удивилась Женя. – А других вариантов нет. Смотрим на 5 камней? – Смотрим! Если их поделить как 5 = = 2 + 3, то Добрыня заработает 2 3 6 монет первым ходом, а потом одну монету за кучку из 2 камней и три монеты за кучку