Экстремальные задачи в целых числах.

⇐ ПредыдущаяСтр 11 из 14Следующая ⇒

Экстремум - это обобщающее понятие, означающее либо максимум, либо минимум. Мы в основном будем рассматривать задачи с «экономическим» уклоном, в которых требуется найти экстремум функции (последовательности) целочисленного аргумента. Особенностью таких задач является отсутствие какого-либо единого метода их решения. Будут применяться все уже изученные методы решения задач в целых числах (делимость, оценки переменных, графические иллюстрации и т.д.). Однако при этом каждая «экстремальная» задача имеет свою ярко выраженную специфику. Рассмотрим несколько примеров.

Уровень А:

Пример 1. Зоопарк ежедневно распределяет 111 кг мяса между лисами, леопардами и львами. Каждой лисе полагается 2 кг мяса, леопарду - 14 кг, льву - 21 кг. Известно, что у каждого льва бывает ежедневно 230 посетителей, у каждого леопарда - 160, у каждой лисы - 20. Сколько должно быть лис, леопардов и львов в зоопарке, чтобы ежедневное число посетителей у этих животных было максимальным?

Решение. Пусть - количество лис, леопардов и львов соответственно. Тогда условие задачи можно сформулировать следующим образом: «При каких натуральных х, у и z, таких, что , выражение принимает наибольшее значение? » Пусть . Выразив и подставив в первое уравнение, получим систему:

Значит, максимально, когда максимально . Это означает, что леопардов и львов в сумме должно быть как можно больше. Но так как леопард съедает меньше мяса, чем лев, надо брать как можно больше леопардов. При этом наибольшее возможное число леопардов - семь, иначе им не хватит на всех 111 кг мяса. Пусть . Имеем:

Так как то и , следовательно, поскольку - натуральное число. Но тогда не является целым числом, поэтому последняя система решений не имеет. Пусть . Имеем:

Так как , то и , следовательно, или поскольку z- натуральное число. Если , то не является целым числом, если

Ответ: 3 лисы, 6 леопардов и 1 лев.

Пример 2. На полевых работах геологу нужно собрать образцы типов А и В. Вес одного образца типа А равен 3 кг, а типа В -4 кг. По каждому из образцов типа А требуется провести 5 видов анализов, а по каждому из образцов типа В- 7 видов. Известно, что вес всех собранных образцов не должен превышать 149 кг, а общее число всех проведенных анализов должно быть не менее чем 249. Какое минимальное и максимальное суммарное количество образцов обоих типов можно собрать при указанных условиях?

Решение. Пусть x и y – количество собранных образцов типа А и В соответственно, - суммарное количество образцов. Согласно условиям задачи имеем следующую систему:

⇔

На координатной плоскости изобразим множество точек, являющихся решением последней системы неравенства с учетом условия (рис.9).

Так как и - натуральные числа, то точка этого множества с наименьшей ординатой есть точка , а точка с наибольше ординатой есть точка . Таким образом, при данных условиях можно собрать минимально 36 образцов, максимально - 49 образцов.

Ответ: 36 и 49.

Уровень В:

Пример 3.

Фабрика получила заказ на изготовление 1005 деталей типа P и 2010 деталей типа Q. Каждый из 192 рабочих фабрики затрачивает на изготовление двух деталей типа P время, за которое он мог бы изготовить одну деталь типа . Каким образом следует разделить рабочих фабрики на две бригады, чтобы выполнить заказ за наименьшее время, при условии, что обе бригады приступят к работе одновременно и каждая из бригад будет занята изготовление деталей только одного типа?

Решение.

Пусть – число рабочих в бригаде, изготовляющей детали типа , -число рабочих в бригаде, изготовляющих детали типа , -количество деталей типа , которое один делает рабочий за единицу времени, тогда -количество деталей типа P, которое один рабочий делает за ту же единицу времени. Тогда время изготовления деталей типа составит , а время изготовления деталей типа есть . Время выполнения заказа равно , где .

Таким образом, задача свелась к поиску натурального , лежащего в интервале , для которого достигается минимум функции . Для решения этой задачи удобно нарисовать график функции (рис.10).

Очевидно, что минимум достигается при , где есть решение уравнения , т.е. . Поскольку не является целым числом, необходимо исследовать два близлежащих целых числа и и сравнить и . Так как , то минимум достигается при Таким образом, рабочих фабрики следует разделить на бригады в количестве 39 и 153 человека.

Ответ: 39 и 153 человека.

Пример 4. На покупку тетрадей в клетку и в линейку можно затратить не более 140 рублей. Тетрадь в клетку стоит 3 рубля, тетрадь в линейку - 2 рубля. При закупке число тетрадей в клетку не должно отличаться от числа тетрадей в линейку более чем на 9. Необходимо закупить максимально возможное суммарное количество тетрадей, при этом тетрадей в линейку нужно закупить как можно меньше. Сколько тетрадей в клетку и сколько тетрадей в линейку можно закупить при указанных условиях?

Решение. Пусть — количество закупленных тетрадей в клетку и в линейку соответственно, - общее количество тетрадей. Согласно условиям задачи имеем следующую систему:

Сложив первые два неравенства, получим неравенство , которое эквивалентно неравенству , поскольку - целое число. Следовательно, максимально возможное значение переменной - это При этом исходная система принимает следующий вид:

Ясно, что минимально возможное значение переменной - это при этом . Таким образом, нужно купить 26 тетрадей в клетку и 31 тетрадь в линейку.

Ответ: 26 тетрадей в клетку и 31 тетрадь в линейку.

Уровень С:

Пример 5. Из строительных деталей двух видов можно собрать три типа домов. Для сборки 12-квартирного дома необходимо 70 деталей первого и 100 деталей второго вида. Для 16-квартирного дома требуется 110 и 150, а для дома на 21 квартиру нужно 150 и 200 деталей первого и второго видов соответственно. Всего имеется 900 деталей первого и 1300 деталей второго вида. Сколько и каких домов нужно собрать, чтобы общее количество квартир в них было наибольшим?

Решение. Пусть - число домов на 12, 16 и 21 квартиру соответственно. Тогда условие задачи можно сформулировать следующим образом: «Какое наибольшее значение может принять выражение

при условиях, что и ? » Пусть Имеем:

Так как числа не принимают отрицательных значений, из второго неравенства системы следует, что . Пусть . Имеем:

Так как - целые неотрицательные числа, то полученной системе удовлетворяет единственная пара чисел , однако при этом не является целым числом. Аналогичная ситуация и при . Пусть . Имеем:

Данной системе удовлетворяют пары чисел , однако x ни в одном из случаев не являете целым числом. Аналогичная ситуация и при . Пусть . Имеем:

Данной системе удовлетворяют пары чисел , однако снова ни в одном из случаев не является целым числом. И, наконец, если , система примет вид

и будет иметь единственное целочисленное решение

Ответ: Один дом на 16 квартир и 11 домов на 12 квартир.

Пример 6. Паром грузоподъемностью 109 тонн перевозит джипы и грузовики. Количество перевозимых на пароме грузовиков не менее чем на превосходит количество перевозимых джипов. Вес и стоимость перевозки одного джипа составляют 3 тонны и 600 рублей, а грузовика - 5 тонн и 700 рублей соответственно. Определить наибольшую возможную суммарную стоимость перевозки всех джипов и грузовиков при данных условиях.

Решение: Пусть - количество перевозимых на пароме джипов и грузовиков соответственно. Согласно условиям задачи имеем следующую систему:

где - суммарная стоимость перевозки всех джипов и грузовиков, которую надо сделать максимальной. Исключая из системы переменную , получаем:

⇒

Так как t-целое число, получаем, что . Пусть . Имеем:

Если , получаем:

не является целым числом.

Если , имеем:

не является целым числом.

И, наконец, если , получаем:

Таким образом, ответом к задаче будет служить сумма рублей.

Ответ: 17100 рублей.

Задачи для самостоятельного решения

Уровень А:

1. Один рабочий бригады, состоящей из 5 человек, производит в среднем 14 деталей в час, причём каждый из рабочих производит в час целое число деталей, не превышающее 16. Сколько деталей в час может делать при этих условиях рабочий с самой низкой производительностью?

2. Из пункта А в пункт В по железной дороге нужно перевезти 20 больших и 250 малых контейнеров. Один вагон вмещает 30 малых контейнеров, вес каждого из которых 2 тонны. Большой контейнер занимает место 9 малых и весит 30 тонн. Грузоподъемность вагона равна 80 тонн. Найти минимальное число вагонов, достаточное для перевозки всех контейнеров.

3. Детский сад хочет приобрести на сумму 2200 рублей наборы конфет. Наборы одного типа стоят 50 рублей (в каждой коробке 10 конфет), наборы другого типа - 180 рублей (в каждой коробке 38 конфет), наборы третьего типа - 150 рублей (в каждой коробке 32 конфеты). Сколько коробок каждого типа должен купить детский сад, чтобы общее число купленных конфет было максимальным?

Уровень В:

4. При проведении геологических исследований требуется пробурить скважины типов А и В. Каждая скважина типа А имеет глубину 70 метров, а типа В - 90 метров. Расходы на бурение одной скважины типа А составляют 500 тыс. руб, а одной скважины типа В - 600 тыс. руб. Суммарная глубина всех скважин должна быть не менее 3290 метров, а общие затраты на бурение всех скважин не должны превышать 22 300 тыс. руб. Какое минимальное и максимальное суммарное количество скважин обоих типов можно пробурить при указанных условиях?

5. Цех получил заказ на изготовление 2000 деталей типа А и 14 000 деталей типа В. Каждый из 146 рабочих цеха затрачивает на изготовление одной детали типа А время, за которое он мог бы изготовить 2 детали типа В. Каким образом следует разделить рабочих цеха на две бригады, чтобы выполнить заказ за наименьшее время, при условии, что обе бригады приступят к работе одновременно и каждая из бригад будет занята изготовлением деталей только одного типа?

6. В профком поступили путёвки трёх типов на отдых в санатории. Одна путёвка первого типа стоит 4 тыс.руб., одна путёвка второго типа - 6 тыс.руб., одна путёвка третьего типа - 9 тыс.руб. По путёвке первого типа можно отдыхать 8 дней, по путёвке второго типа - 14 дней, по путёвке третьего типа -20 дней. Сколько путёвок каждого типа надо купить, чтобы общее число дней отдыха было наибольшим, а сумма, израсходованная на приобретение всех путевок, составляла 100 тыс.руб.?

7. В магазине продаются гвоздики и розы. Гвоздика стоит 30 рублей, роза - 40 рублей. На покупку гвоздик и роз можно потратить не более 710 рублей. При покупке число гвоздик не должно отличаться от числа роз более чем на 6. Необходимо купить максимально возможное суммарное количество цветов, при этом гвоздик нужно купить как можно меньше. Сколько гвоздик и сколько роз можно купить при указанных условиях?

Уровень С:

8. Предприятие производит телевизоры и является прибыльным. Известно, что при изготовлении п телевизоров в месяц расходы предприятия на выпуск одного телевизора составляют не менее тыс. руб., а цена каждого телевизора не превосходит. тыс. руб. Определите ежемесячный объем производства, при котором может быть получена наибольшая из возможных в данных условиях ежемесячная прибыль.

9. Автофургон грузоподъемностью 339 кг перевозит ящики с виноградом и яблоками. Вес и стоимость одного ящика с виноградом составляют 15 кг и 10 условных единиц, ящика с яблоками - 27 кг и 8 условных единиц соответственно. Известно, что количество загруженных на автофургон ящиков с виноградом составляет не более 70% от количества загруженных ящиков с яблоками. Определить наибольшую возможную суммарную стоимость всех ящиков с виноградом и яблоками, перевозимых автофургоном при данных условиях.

10. Из строительных деталей двух видов можно собрать три типа домов. Для сборки 6-квартирного дома необходимо 30 деталей первого и 40 деталей второго вида. Для 10- квартирного дома требуется 40 и 60, а для дома на 14 квартир нужно 90 и 120 деталей первого и второго видов соответственно. Всего имеется 600 деталей первого и 800 деталей второго вида. Сколько и каких домов нужно собрать, чтобы общее количество квартир в них было наибольшим?

Целочисленные прогрессии.

Пусть - первый член и разность некоторой арифметической прогрессии, - количество её членов. Пусть также - -й член этой прогрессии, - сумма первых её членов. Имеют место следующие соотношения:

Пусть теперь и - первый член и знаменатель некоторой геометрической прогрессии ), - количество её членов. Пусть также - -й член этой прогрессии, - сумма первых её членов. Тогда выполнены следующие равенства:

В данной главе в основном рассматриваются задачи на арифметическую либо геометрическую прогрессии, все члены которой являются целыми числами. При решении таких задач используются уже изученные нами методы и приемы. Рассмотрим несколько примеров.

Уровень А:

Пример 1. Последние члены двух арифметических прогрессий совпадают, а сумма всех их общих членов равна 815. Найти и

Решение. Очевидно, что . Для нахождения общего члена двух прогрессий составим и решим в натуральных числах уравнение:

Рассматривая всевозможные остатки от деления на 3, получим, что . Найдем . Легко видеть, что общие члены обеих арифметических прогрессий сами образуют арифметическую прогрессию с первым членом, равным 14, разностью, равной 15, и количеством членов, равным . Применив к этой прогрессии формулу для нахождения суммы её первых членов:

Ответ:

Пример 2. Все члены геометрической прогрессии { } являются целыми числами. Определить, при каких из указанных ниже значений число делится на независимо от выбора прогрессии, если a) ; б) ; в) .

Решение. Пусть - первый член геометрической прогрессии, a - её знаменатель. Согласно условиям задачи - целые числа, кроме того, Если , то , . Поэтому первое число делится нацело на второе. Пусть . Имеем:

При любом нечётном полученная дробь является целым числом. Действительно,

+1.

Поэтому и удовлетворяют требованиям задачи. В то же время, к примеру, для т.е. первое из чисел не делится нацело на второе.

Ответ:

Уровень В:

Пример 3. Количество сотрудников корпорации ежегодно возрастало в геометрической прогрессии и за шесть лет увеличилось на 20615 человек. Найти первоначальную численность сотрудников корпорации.

Решение. Пусть - первоначальная численность сотрудников корпорации, a , где взаимно просты, - знаменатель геометрической прогрессии ( рационально как отношение двух натуральных чисел). Прирост за шесть лет равен

где -натуральное число, поскольку взаимно просты, а значит, числа и также взаимно просты. Имеем далее:

причем

Возможны четыре случая:

1. Если , то каждое из четырех чисел должно совпадать с соответствующим из чисел , поэтому откуда , что невозможно, так как

2. Если , а , то ,

3. Если , а , то , что не делится ни на одно из чисел

4. Если , а , , откуда получается что , , что невозможно. Таким образом, первоначальная численность сотрудников корпорации составляла 1984 человека.

Ответ: 1984 сотрудника.

Пример 4. Сумма первых четырнадцати членов арифметической прогрессии равна 77. Известно, что ее первый и одиннадцатый члены - натуральные числа. Чему равен восемнадцатый член прогрессии?

Решение. Пусть и - первый член и разность данной арифметической прогрессии, a - сумма её первых четырнадцати членов. Согласно условию задачи имеем уравнение

откуда вытекает, что является целым числом. Далее, - целое число, следовательно, также является целым числом. Имеем:

так как - целое число. Итак, мы доказали, что разность прогрессии является целым числом.

Из равенства вытекает, что и . Так как , и не только целые, но и натуральные числа, имеем следующую систему неравенств:

поскольку - целое число.

Если неявляется целым числом. Если же , то и .

Ответ:

Пример 5. Найти первый член целочисленной арифметической прогрессии, у которой сумма первых шести членов отличается от суммы следующих шести членов менее чем на 450, а сумма первых пяти членов превышает более чем на 5 сумму любого другого набора различных членов этой прогрессии.

Решение. Пусть и - первый член и разность данной арифметической прогрессии, и ; - -й член и сумма ее первых членов соответственно. Тогда первое из условий задачи можно записать следующим образом:

так как - целое число. Здесь - сумма членов данной прогрессии с седьмого по двенадцатый включительно.

Далее, согласно второму условию задачи, имеем неравенства и (здесь используем целочисленностью данной прогрессии). Первое из этих неравенств эквивалентно неравенству , а второе - неравенству . Имеем:

Итак, , первое неравенство системы принимает вид , второе неравенство преобразуется к виду . Значит,

Уровень С:

Пример 6. Первый член конечной геометрической прогрессии с целочисленным знаменателем меньше последнего, но не более чем на 17, а сумма её членов со второго по последний не меньше 26. Найти знаменатель прогрессии.

Решение. Пусть и - соответственно, -й член и сумма л первых членов данной прогрессии, — ее знаменатель. Заметим, что , иначе не выполняется первое из условий задачи. Согласно остальным условиям задачи при имеем следующую систему неравенств:

Так как дробь положительна при всех целых , отличных от нуля и единицы, полученная система эквивалентна следующему двойному неравенству:

Ясно, что последнему неравенству с учетом всех вышеперечисленных условий удовлетворяет только . При этом двойное неравенство принимает вид и выполняется, например, при и Таким образом, знаменатель данной геометрической прогрессии равен двум.

Ответ: .

Пример 7. Найти все возможные значения суммы возрастающей арифметической прогрессии:

где - некоторое целое число.

Решение. Заметим, что разность данной прогрессии равна .

Прогрессия является возрастающей, если , т.е. (так как — целое число). При или имеем .

По формуле -го члена арифметической прогрессии находим, что

Тогда сумма первых членов этой прогрессии будет равна

Если или , имеем

В этом случае:

- не является целым числом. И, наконец, при находим, что

В этом случае получаем, что

Тогда . Таким образом, сумма членов данной арифметической прогрессии может быть равна 7 или 4.

Ответ: или

Пример 8. Шесть простых чисел являются последовательными членами возрастающей арифметической прогрессии. Доказать, что разность этой прогрессии не меньше 30.

Решение. Предположим, что разность прогрессии нечетна. Тогда в этой прогрессии будет как минимум три чётных числа, что невозможно. Аналогично, если разность прогрессии не кратна 3, то в этой прогрессии будут как минимум два числа, кратных трем. Значит, разность прогрессии кратна 2 и 3, т.е. кратна 6.

Если разность прогрессии не кратна 5, то в ней есть член, кратный 5. Тогда это простое число 5. Если 5 — первый член прогрессии, то среди оставшихся пяти членов есть еще один член, кратный 5, что невозможно. Если же 5 не является первым членом, то первый член будет отрицательным, ибо ранее доказано, что разность прогрессии не меньше 6.

Итак, разность прогрессии кратна 5 и 6, т.е. кратна 30, а значит, не менее 30. Прогрессия с разностью 30, удовлетворяющая условию задачи, существует. В качестве примера можно взять прогрессию 7 , состоящую из простых чисел.

Задачи для самостоятельного решения.

Уровень А:

1. Найти сумму первых ста общих членов арифметических прогрессий .

2. Известно, что последние члены двух арифметических прогрессий , и , совпадают и что сумма всех общих членов этих прогрессий равна 1440. Найти

3. Найти сумму чисел, одновременно являющихся членами двух арифметических прогрессий: 2, 5, 8, ..., 332 и 7, 12, 17, ..., 157.

Уровень В:

4. Сумма первых четырёх членов арифметической прогрессии равна 56. Все члены этой прогрессии - натуральные числа. Двенадцатый член больше 67, но меньше 74. Найти двадцатый член этой прогрессии.

5. Найти первый член целочисленной арифметической прогрессии, у которой сумма первых семи членов отличается от суммы следующих семи членов менее чем на 400, а сумма первых шести членов превышает более чем на 3 сумму любого другого набора различных членов этой прогрессии.

6. Сумма первых пятнадцати членов арифметической прогрессии, состоящей из натуральных чисел, больше 337, но меньше 393. Чему равен восьмой член этой прогрессии, если известно, что он кратен четырем?

7. Количество жителей поселка ежегодно возрастало в геометрической прогрессии и за шесть лет увеличилось на 37 037 человек. Найти первоначальную численность жителей поселка.

Уровень С:

8. Первый член конечной геометрической прогрессии с целочисленным знаменателем меньше последнего, но не более чем на 15, а сумма её членов со второго по последний не меньше 23. Найти знаменатель прогрессии.

9. Найти все возможные значения суммы убывающей арифметической прогрессии:

;
где — некоторое целое число.

⇐ Предыдущая 5 6 7 8 9 101112 13 14 Следующая ⇒