Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2001/03/63.pdf Дата изменения: Fri Dec 23 19:26:25 2005 Дата индексирования: Tue Oct 2 00:16:48 2012 Кодировка: Windows-1251 Поисковые слова: sirds

ОТВЕТЫ,

УКАЗАНИЯ,

РЕШЕНИЯ

63

12. Решим задачу в общем случае найдем минимально необходи" ! мое число разрезов для # квадрата размером n Ч n клеток. Рассмот рим сначала произвольный клетчатый прямоугольник. Разре# зав его по любой ли$ нии сетки, мы получим два прямоугольника, у $ которых длина одной % & из сторон (той, вдоль &% которой шел разрез) одинакова. Длины вто. 2 рых сторон могут и не совпадать. Но в любом случае получатся два прямоугольника, которые можно сложить так, что один поместится на другом, не выступая за его пределы, и при этом линии сетки совпадут. Поскольку такое наложение разрешено условием, то в дальнейшем вместе с разрезанием большего прямоугольника одновременно будет разрезан и меньший. Поэтому можно после очередного разреза забыть о меньшем из получившихся прямоугольников, ибо, наложив его на больший и в дальнейшем не снимая его, мы одновременно с разрезанием большего прямоугольника на единичные квадратики разрежем на такие же квадратики и меньший. Таким образом, задача свелась к следующей: квадрат размером n Ч n разрезаем по линиям сетки и после каждого разреза меньшую из частей отбрасываем (если они одинаковы то любую). Требуется за наименьшее число разрезов 'добраться' до квадрата размером 1 Ч 1 . Расположим исходный квадрат так, чтобы одна из его сторон была горизонтальна, а другая вертикальна, и после очередного разреза и отбрасывания меньшей части большую часть не будем трогать, сохраняя ее ориентацию. Заметим, что при любых разрезаниях вдоль горизонтали меняется лишь высота оставшейся части прямоугольника, а при любых разрезах вдоль вертикали меняется лишь его ширина. Значит, разрезы по вертикали и горизонтали независимы, и их порядок на итоговый размер 'остатка' не влияет. Поэтому мы можем сначала произвести все необходимые горизонтальные разрезы, получив из квадрата n Ч n горизонтальную полоску размером 1 Ч n , а затем вертикальными разрезами получим из нее квадратик 1 Ч 1 . Выясним, какое потребуется наименьшее количество горизонтальных разрезов. После каждого разреза высота прямоугольника-'остатка' уменьшается не более чем вдвое. Поэтоk -1 k < n 2 , то наму если k такое натуральное число, что 2 верняка потребуется не менее k разрезов. Покажем, что k разрезов и достаточно. Первым разрезом отрежем прямоуk -1 гольник высотой 2 . Второй получившийся в результате k -1 k разреза прямоугольник будет иметь высоту n - 2 2 - k -1 k -1 - 2 = 2 , т.е. его высота не превышает высоту первого. Значит, отбрасываем второй, так как он меньший. В дальнейшем все разрезы проводим, деля высоту точно пополам. k -2 Тогда после второго разреза высота станет равна 2 , после 0 k -k k -3 = 2 = 1 , что и требуеттретьего 2 , ..., после k-го 2 ся. Очевидно, столько же потребуется и вертикальных разрезов, а всего, таким образом, нужно сделать 2k разрезов. Это и есть ответ для произвольного n. 10 11 Так как 2 < 1111 2 , то k = 11, и для разрезания данного квадрата на единичные квадратики потребуется как минимум 2 11 = 22 разреза. 13. Пусть n наибольшее число колонок, которые можно установить при заданных условиях. Суммарное количество

!"

улиц, выходящих из перекрестков, на которых установлены колонки, не меньше 4n. Поскольку среди перекрестков нет соседних, то все эти улицы различные, поэтому 162 4n . Отсюда n 40 . 14. а) Пусть A = a n a n -1 K ak 0K0 , где ak , ak +1 , ..., a n -1 , a n цифры, причем a n 0 , ak 0 , n k 1 . В частном случае a k может быть ненулевой цифрой, стоящей в разряде единиц, тогда нули справа в записи числа А отсутствуют. Если взять m число B = 10 - 1 , где m n , то сумма цифр произведения m AB = A 10 - A равна 9m. Чтобы убедиться в этом, произведем вычитание в столбик и с учетом поразрядного переноса получим an + an -1 + K + ak - 1 + 9 + K + 9 - a n + 9 - a n -1 + K + 1 0 - ak = 9m . б) Сначала построим десять последовательных натуральных чисел, из которых первое делится на 2000, второе на 2001, ..., десятое на 2009. Пусть A = 2000 Ч 2001 Ч K Ч 2009 , тогда требуемым свойством обладают числа АВ + 2000, АВ + 2001, ..., АВ + 2009, где В некоторый вспомогательный натуральный множитель. Если бы удалось подобрать число В таким образом, чтобы сумма цифр числа АВ равнялась 1998, то задача была бы решена. Поскольку 1 998 = 9 222 , то, по доказанному в п.а), достаточ222 но взять B = 10 - 1 (число 222 превышает количество цифр 10 40 в числе А, поскольку A < 1 0000 = 1 0 ). 15. Обозначим через х, у числа, задуманные Труляля, а через а, b числа, задуманные Траляля. Тогда x + y = ab,

b

g

Таким образом, натуральные числа х, у корни уравнения 2 z - abz + a + b = 0 , дискриминант которого 2 D = ab - 4 a + b должен быть квадратом целого числа. Без ограничения общности полагаем b a . Рассмотрим несколько случаев. 2 Пусть а = 1, тогда D = b - 2 - 8 = t 2 , где t натуральное (очевидно, D 0 ). Отсюда b - 2 - t b - 2 + t = 8 , что возможно в одном из двух случаев: b - 2 + t = 8, b - 2 + t = 4,

R | S | T

a + b = xy.

bg

b

b

g

g

b

g b

gb

g

- 2 - t = 1; - 2 - t = 2. Первая из этих систем целых решений не имеет; решение второй системы: b = 5; t = 1. Итак, одно из решений задачи: а = 1; b = 5. В этом случае неизвестные х, у составляют множество значений 2; 3 . Аналогично, при а = 2 получаем b = 3 или b = 2; этим случаям соответствуют ответы 1; 5 и {2; 2}. Разбор случаев а = 3, а = 4, a 5 показывает, что при этих значениях а дискриминант на является квадратом целого числа. Ответ: Труляля мог задумать либо числа 1; 5 , либо числа {2; 3}, либо числа {2; 2}. Соответственно, Траляля мог задумать либо числа {2; 3}, либо числа 1; 5 , либо числа {2; 2}. Других решений нет.

R | Sb | T

R | Sb | T

lq

lq

lq

lq

''

1. При наличии трения часть механической энергии переходит во внутреннюю тепловую энергию тел. 2. Слабо накачанная шина деформируется в большей степени, поэтому ее внутренняя энергия, а значит, и температура, возрастут больше, чем у сильно накачанной шины. 3. На совершение работы против силы сопротивления воздуха и внутренних сил трения во вращающихся частях автомобиля. 4. Частицы покоятся друг относительно друга, т.е. движутся с одинаковыми по величине и направлению скоростями.