Комбинаторная арифметика и комбинаторная алгебра
Основные задачи
Арифметика и алгебра
Цифры
1. (6-7) Дата 21.02.2012 читается одинаково слева направо и справа налево. Сколько всего таких дат в XXI веке? (А. Шаповалов)
2. (6-7) Астролог считает год счастливым, если в его записи используются четыре последовательные цифры. Например, следующий, 2013-й год будет именно таким. А когда, по мнению этого астролога, был предыдущий счастливый год? (Н. Нетрусова)
3. (6) Четырёхзначное число назовем временным, если можно расположить его цифры и поставить посередине двоеточие так, чтобы получилось какое-то показание часов (например,временным являются числа 2010 и 1995, так как часы могут показывать время 00:12 и 19:59). Найдите наименьшее невременное число, большее, чем 2007. (А. Шаповалов)
4. (6-8) Решите ребус РОТОР:СОКОЛ = 3:1. (А. Хачатурян)
5. (6-7) Решите ребус: FOOLS + ROADS = RUSSIA. (К. Кноп)
6. (6-7) На доске было написано равенство. Дежурный по классу успел стереть некоторые цифры (сколько цифр он стёр, неизвестно). На доске осталось:
1127...173×1017...565 = 1126...745.
Могло ли исходное равенство быть верным? (Фольклор)
7. (7-8) На доске выписаны все целые числа от 1 до n. Сеня посчитал, сколько всего цифр выписано. Оказалось, что это число записывается теми же цифрами, что и n, но в обратном порядке. Найдите n, если известно что оно
а) двузначно;
б) трехзначно. (А. Шаповалов)
8. (7-8) Каждая цифра натурального числа N строго больше стоящей слева от нее цифры. Чему равна сумма цифр числа 9N? С.Волчёнков)
9. (7-8) Докажите, что между натуральными числами n и 9n есть натуральное число, чья сумма цифр на 7 больше чем у n. (А. Шаповалов)
10. (7-8) Верно ли, что любое натуральное число, делящееся на 9, отличается от некоторого натурального числа n на сумму цифр этого числа n? (И. Акулич)
11. (8-9) В одну строку без пробелов выписаны числа натурального ряда: 12345678910111213... Далее цифры полученной последовательности попеременно складываются на разные плечи качелей: цифру 1 – на левое плечо, цифру 2 – на правое, цифру 3 – на левое и т.д. Если на очередном шаге сумма цифр на каком-то плече окажется больше, то это плечо перевешивает. Докажите, что качели никогда не перестанут качаться. (А. Жуков)
Простая арифметика
См. также задачи 6А1-6А3, 6К2, 7Г1.
12. (6-7) В дремучем лесу вот уже более 1000 лет живет Волшебная ёлка. Известно, что каждое утро на ней вырастают 100 иголок и каждая иголка живет ровно 4 года, а затем отмирает. Сколько же сегодня иголок на Волшебной ёлке? (Фольклор)
13. (6-7) Старик Хоттабыч может совершить чудо, вырвав из своей волшебной бороды один волос (при этом на месте двух вырванных волос вырастает один новый). Сколько всего чудес может совершить старик Хоттабыч, если первоначально в его бороде 2012 волос? (Фольклор)
14. (6-7) Каждый мальчик съел по одной конфете, 5 котлет и 3 омлета, а каждая девочка – по 2 котлеты, 4 омлета и 6 конфет. Всего они съели 220 конфет и котлет вместе взятых. А сколько омлетов? (По мотивам Харьковской областной олимпиады 1999/2000)
Делимость и остатки
См. также задачи 47, 49, 50, 52, 55, 56, 59, 61, 62, 63, 113, 114, 122, 143, 155, 169, 174, 181, 189, 193, 194, 6Ц2, 6Ц3, 6Ч2, 6Ч3, 7А5, 7Т3, 7К1, 7К3, 8Ар1, 8Ар2, 8Ар4, 8К1, 8М1, 9П1, 9П2, 9П4, 9Т1.
15. (6-7) Саша живёт в своём доме, в котором окон на 2 больше, чем дверей. Все братья Саши – Петя, Коля и Лёня – тоже живут каждый в своём доме. В доме Коли окон на 5 больше, чем дверей, а в доме Пети окон на 4 больше, чем дверей. Может ли у всех братьев Лёни в домах в сумме окон быть в 4 раза больше, чем дверей? (Фольклор)
16. (6-7) Для проведения тренировочной командной олимпиады пригласили всех желающих школьников и заранее объявили, что в каждой команде – от 6 до 8 человек. Когда подсчитали количество пришедших, то выяснилось, что выполнить это условие невозможно, при этом на две команды школьников хватало. Сколько человек пришло на олимпиаду? (А. Блинков)
17. (6-7) У Мальвины были золотые колечки веса 1 г, 3 г, 4 г, 6 г, 8 г, 9 г, 11 г, 12 г и 16 г. Алиса и Базилио украли по 4 кольца. При этом Алисе досталось втрое больше золота, чем Базилио. Сколько весит оставшееся кольцо? (Фольклор)
18. (6-8) В Зазеркалье имеют хождение монеты достоинством 7, 13 и 25 гиней. Алиса заплатила за пирожок несколько монет и получила на сдачу на две монеты больше.
а) Могла ли покупка стоить 100 гиней?
б) Могла ли покупка стоить 60 гиней?
в) Какова минимально возможная стоимость покупки? (А. Шаповалов)
19. (6-7) В теремке лежали 100 конфет. Пришла мышка и съела некоторое количество конфет. Но тут пришла лягушка, и мышка сьела еще одну конфету, чтобы количество оставшихся делилось поровну на двоих. Потом пришли по очереди зайчик, лисичка, волк и медведь, и каждый раз мышка съедала по одной конфете, чтобы то, что осталось, делилось поровну на всех собравшихся. Наконец пришел слон. Какое наименьшее количество конфет придется съесть мышке на этот раз, чтобы количество оставшихся делилось поровну на семерых? (И. Раскина)
20. (6-7) Сумма трех натуральных чисел равна 520. На какое наибольшее число нулей может оканчиваться их произведение? (Колумбия, 2004)
21. (6-7) Докажите, что сумма всех семизначных палиндромов делится на 9. (А.Шаповалов)
22. (6-7) а) В стране имеют хождение банкноты в 60, 15, 12 и 10 динаров. Некто жил в гостинице и платил каждый день одну и ту же сумму, получая причитающуюся сдачу. Вначале у него была банкнота в 60 динаров. Могло ли оказаться, что гость прожил в гостинице 10 дней?
б) В стране имеют хождение монеты в 1 динар, а также в 1/4 и 1/6 динара. Гость жил в гостинице и платил каждый день одну и ту же сумму, получая причитающуюся сдачу. Вначале у него был 1 динар. Мог ли гость прожить в гостинице 10 дней?
в) В стране имеют хождение монеты в 1 динар, а также в 1/4, 1/5 и 1/6 динара. Гость жил в гостинице и платил каждый день одну и ту же сумму, получая причитающуюся сдачу. Сначала у него был 1 динар. Мог ли гость прожить в гостинице 14 дней? (Ни на что другое гость денег не тратил.) (А. Шаповалов)
23. (7-8) Приехав от бабушки, марсианин Надгоб через несколько дней написал ей первое электронное письмо. Промежуток между первым и вторым письмом длился на день дольше, между вторым и третьим – ещё на день дольше и т. д. Спустя длительное время бабушка рассортировала письма по дням недели, и на каждый хоть одно письмо да пришлось. Докажите, что в марсианской неделе чётное число дней. (И. Богданов)
24. (7-8) Мама пекла блины, а четверо детей их ели, каждый со своей скоростью. Получив сначала по блину, дети начали есть одновременно. Как только ребенок съедал блин, он получал еще один. Каждый хоть раз получил добавку. Наконец, мама объявила, что больше блинов не будет. Дети доели то, что у каждого оставалось, и закончили одновременно. Известно, что до этого не было моментов, когда бы заканчивали есть блин одновременно двое или больше детей. Какое наименьшее число блинов могла испечь мама? (А. Шаповалов)
25. (7-9) Докажите, что существует бесконечно много таких пар натуральных чисел
(m, n), что m и n имеют одинаковые наборы простых делителей, и m – 1 и n – 1 также имеют одинаковые наборы простых делителей. (Фольклор)
26. (7-8) Берутся всевозможные произведения наборов из 2011 чисел от 1 до 2010, необязательно различных, а далее находится их сумма. Найдите остаток от деления этой суммы на 2011. (Наборы {1, 2, 2, 1, 1, 1, ...} и {2, 1, 1, 2, 1, 1, 1, ...} считаются одинаковыми.) (А. Юрков)
27. Числа 1, 2, 3, ..., n записаны в строку в таком порядке, что из каждых трёх подряд записанных чисел одно равно сумме двух других. Может ли быть
а) (7) n = 100? б) (9) n = 2007? (И. Акулич)
28. (6-7) Можно ли расставить на окружности цифры 0, 1, 2, …, 9 так, чтобы сумма каждых трёх из них, идущих подряд, не превышала 13? (Фольклор)
29. (6-7) а) В треугольнике все углы измеряются целым числом градусов, причём все цифры в записи углов различны. Каков наибольший возможный НОД величин углов?
б) Сумма нескольких натуральных чисел равна 1000, все цифры в их записи различны. Какие значения может принимать наибольший общий делитель этих чисел? (А. Шаповалов)
30. (6-7) а) Найдите наибольшее простое число, которое нельзя представить как сумму двух составных.
б) Найдите наибольшее натуральное число, которое не представляется как сумма восемнадцати составных. (А. Шаповалов)
31. (6-7) Перемножили несколько натуральных чисел и получили 224, причём самое маленькое число было ровно вдвое меньше самого большого. Сколько чисел перемножили? (А. Сгибнев)
32. (7-8) У натурального числа есть десять различных простых делителей. Докажите, что найдется несколько делителей этого числа, сумма которых делится на 1024. (Д. Калинин)
33. (7-8) Пусть n и m – натуральные числа, причём n > m. Докажите, что n представимо в виде суммы двух натуральных чисел, одно из которых – делитель числа m, а другое взаимно просто сm. (С. Конягин, А. Спивак)
34. (9) Пусть p и q – произвольные целые числа. Последовательность чисел хn определяется следующим образом: х0 = р, хn = (n + 1)xn–1 + (–1)nq для всех n ³ 1. Докажите, что хn делится на nдля всех натуральных n. (И. Акулич)
36. (9) Существует ли нечётное число, сумма всех делителей которого (исключая само число) больше него? (А. Марачёв)
37. (9) Пусть P – произведение некоторых восьми последовательных натуральных чисел, а Q – наименьший точный квадрат, для которого Q > P. Докажите, что разность
Q – P является точным квадратом. (С. Токарев)
Дроби
См. также задачи 36, 182, 6А4, 7А3, 8Ал3, 8М1.
38. (6-7) Клетчатая таблица называется магическим квадратом, если все числа в ней различны и суммы чисел во всех строках и столбцах одинаковы.
Существует ли магический квадрат 3×3, заполненный числами, обратными натуральным? (А. Шаповалов)
39. (6-8) За одно нажатие можно число на экране калькулятора увеличить на его дробную часть (например, из 3/7 получить 6/7, а из 3,8 получить 3,8 + 0,8 = 4,6).
а) Начав с положительного числа, меньшего 1, за три нажатия получили число 3. С какого числа начали?
б) Начав с положительного числа, меньшего 1, за десять нажатий получили число 10. С какого числа начали? (А. Шаповалов)
40. (7) Григорий Вячеславович планировал, что стоимость проживания на базе составит А рублей с человека в день (А – целое трёхзначное число, большее ста). Узнав, что команд очень много, он снизил оплату на b процентов (b – целое число). В итоге турнир проводился на двух базах, поэтому новая стоимость проживания была поднята также на b процентов. Могло ли оказаться так, что в итоге стоимость проживания на базе отличалась от первоначальной ровно на 1 рубль? (А. Блинков)
41. (7-8) В одном стакане было 100 мл раствора кислоты, причём доля кислоты (по объему) составляла 40%, а в другом – 150 мл с долей кислоты 50%. Ложку раствора из первого стакана перелили во второй и, после перемешивания, такую же ложку перелили из второго в стакана в первый. В результате доля кислоты в каждом из стаканов по-прежнему выражалась целым числом процентов.
а) Найдите доли кислоты в стаканах после переливаний.
б) Найдите вместимость ложки (объем ложки меньше стакана). (С. Токарев)
42. (8-9) Числа a2 – a и a4 – a целые. Докажите, что a – целое число. (К. Кноп)
Средние
См. также задачи 80, 82, 90, 7А2, 7А3, 7Т4, 8Ар1, 9П5.
43. (6-7) Профессор Мумбум-Плюмбум мечтает найти десять различных натуральных чисел, наибольший общий делитель которых совпадает с их средним арифметическим. Удастся ли ему это сделать? (А. Жуков)
44. (6-7) Среднее арифметическое всех Володиных оценок по геометрии за четверть – целое число. Если заменить все двойки – тройками, тройки – четверками, а четверки – пятерками, то среднее арифметическое оценок опять-таки будет целым. Что Володя получил в четверти, если известно, что не все его оценки – одинаковые? (В. Гуровиц)
45. (7-8) Петя вычислил среднее арифметическое некоторого множества (т. е. неупорядоченного набора) различных степеней двойки. Лена вычислила среднее арифметическое некоторого другого множества различных степеней двойки. Может ли Петино число быть равно Лениному? (О. Крижановский)
46. (7-9) Выступления танцоров оценивались семью судьями. Каждый из судей выставлял оценку (целое число от 0 до 10), худшая и лучшая оценки отбрасывались, и выводилось среднее арифметическое. По окончании соревнований председатель жюри подсчитал, что если бы средняя оценка выводилась по всем семи оценкам, то все участники расположились бы строго в обратном порядке. Какое наибольшее количество танцоров могло участвовать в соревновании? (А. Блинков)
Комбинаторная арифметика и комбинаторная алгебра
См. также задачи 66, 73, 113, 114, 183, 8Ар3.
48. (6-7) Мартышка, Попугай, Удав и Слонёнок устроили концерт по случаю приезда бабушки Удава. На концерте было исполнено 7 номеров, причем каждый номер представлял собой либо пение вдвоем, либо танец втроем. Никакие два номера не исполнялись одним и тем же составом. Удав участвовал в исполнении одной песни и двух танцев. Мартышка исполнила больше номеров, чем Слонёнок. Сколько номеров исполнил Слонёнок? (Е. Барабанов)
49. (6-7) Разложите 100 орехов на 10 кучек так, чтобы в них было разное число орехов, но никакую из куч нельзя было бы разбить на две так, чтобы число орехов во всех 11 кучках оставалось различным. (А. Шаповалов)
50. (7) У Сени есть пять альбомов с фотографиями. Как-то, рассматривая фотографии, он заметил, что суммарное число фотографий в любых двух альбомах принимает только три значения: 75, 88 и 101. Сколько фотографий в каждом альбоме? (Е. Барабанов)
51. (7-8) В Галактическом теннисном турнире, проведенном по «олимпийской» системе (проигравший – выбывает) участвовало 2100 спортсменов. В каждом туре играли все оставшиеся спортсмены. Все матчи одного тура проходили одновременно, и каждый из них судил один арбитр. Известно, что арбитр, судивший финал, не судил больше ни одной встречи. Докажите, что были, по крайней мере, еще два арбитра, судившие по одной встрече. (Б.Френкин)
52. (8-9) В строке 2, 3, 2, 4, 3, 1, 1, 4 каждое из чисел от 1 до 4 встречается дважды, и количество запятых между одинаковыми числами равно этому числу. А можно ли записать такую строку для чисел от 1 до 2006? (В. Гуровиц)
53. (6-7) На доске вначале выписаны два числа: 1 и 2. За один ход разрешается увеличить любое число на доске на сумму цифр другого. Можно ли добиться, чтобы оба числа превратились в 2012? (А. Шаповалов)
54. (6-7) На дощечке написаны два числа: с левой стороны – 2012, а с правой – 1000. За один ход можно прибавить к числу, написанному слева, некоторое натуральное число, а число, написанное справа, умножить на то же самое число. Можно ли уравнять числа на разных сторонах дощечки, сделав не более 1000 ходов? (А. Штерн)
55. На доске были написаны некоторые целые числа. На каждом шаге мы выбираем числа a и b и заменяем их на числа 3a – b и 13a – 3b.
а) (7) Вначале на доске были записаны числа 1, 2, 3, ..., 32. Можно ли через конечное число шагов получить на доске числа 2, 4, 6, ..., 64?
б) (9) Вначале на доске были записаны числа 1, 2, 3, 4, ..., 2011, 2012. Можно ли получить числа 2, 4, 6, 8, ..., 4022, 4024? (Хорватия, 2012)
56. (6-7) Миллионзначное натуральное число назовем кошачьим, если оно делится на произведение своих цифр. Сколько последовательных натуральных чисел могут быть кошачьими? (В.Сендеров)
57. (7) Числа от 1 до 100 раскрасили в несколько цветов так, что разность одноцветных чисел не равна 2, 3 или 6. Каково наименьшее возможное число цветов? (В. Каскевич)
58. (7-8) Прибор «Сложномер» представляет любое натуральное число в виде произведения простых чисел (не обязательно различных) и выдает количество сомножителей в таком представлении. Например, для 28 = 2×2×7 «Сложномер» выдает 3. Прибор начали последовательно применять к натуральным числам, начиная с 2. В какой-то момент прибор впервые выдал число, большее 2012. Докажите, что следующее выданное число меньше 2013. (Б. Френкин)
59. (7-8) По кругу написаны натуральные числа, причём каждое равно сумме или разности своих соседей. Докажите, что количество чисел на круге делится на 3. (Фольклор)
60. (6-8) Турнир математических боев в «Берендеевых Полянах» продолжался 7 дней. На 28 команд-участниц в столовой накрывалось ровно 28 столов. В первый же день не все команды ели за своим столом. Во второй день команд, евших не за своим столом, оказалось на 2 больше, в третий день – еще на 2 больше, и так далее. По окончании турнира Григорий Вячеславович подсчитал, что каждая команда все-таки сумела поесть за отведённым ей столом не менее пяти дней. Сколько команд ели за своим столом в последний день? (В течение одного дня команда ела за одним и тем же столом.) (А. Блинков)
61. (8-9) Дана бесконечная последовательность пифагоровых (т. е. прямоугольных с целочисленными сторонами) треугольников. Гипотенуза каждого из них служит катетом следующего. Может ли в этой последовательности быть бесконечно много треугольников, подобных египетскому (т. е. со сторонами 3, 4, 5), не обязательно идущих подряд? (Б. Френкин)
62. (8-9) Докажите, что числа от 1 до n можно расставить в ряд так, чтобы каждое делило сумму предыдущих. (А. Шаповалов)
63. (9) Каких чисел больше в первой тысяче: представимых или не представимых в виде
x3 – y!, где x и y натуральны? (В. Сендеров, Н. Агаханов)