Логические задачи

     Ответ: 1130.

     Задача 3. Большая группа туристов выехала в заграничное путешествие. Из них владеют английским языком 28 человек, французским – 13, немецким – 10, английским и французским – 8, английским и немецким – 6, французским и немецким- 5, всеми тремя языками – 2, а 41 человек не владеет ни одним из трёх языков. Сколько туристов в группе?

     Решение: обозначим множество  туристов группы, которые владеют  английским, французским, немецким языком соответственно через А , В и С. По условию n (А) = 28,

                                   13 

     n (В) = 13, n (С) = 10, n (АВ) = 8, n (АС) = 6, n (ВС) = 5, n (АВС) = 2. Найдём число туристов, которые владеют, по меньшей мере , одним из трёх иностранных языков, то есть n (АВС). Применим круги Эйлера. 

     

            А - 28        В - 13

                                                                                                                                                                       С – 10     

      Подсчитаем сумму n (А)+ n (В)+ n (С). Так как в неё каждое из чисел n (АВ), n (АС), n (ВС) вошло слагаемым два раза, то от этой суммы нужно отнять сумму n (АВ)+n (АС)+n (ВС). Выясним, сколько раз в полученное выражение n (А)+ n (В)+ n (С)-n (АВ)-n (АС)-n (ВС) входит слагаемым число n (АВС). Оно входит в эту сумму три раза со знаком + (в каждое из слагаемых n (А), n (В) и n (С)) и три раза со знаком – (в каждое из слагаемых n (АВ), n (АС) и (ВС)). Следовательно, чтобы не потерять тех туристов, которые входят во множество АВС, нужно ещё прибавить число n (АВС). Получаем: n (АВС) = n (А)+ n (В)+ n (С)-n (АВ)-n (АС)-n (ВС)+ n (АВС). Будем иметь: n (АВС) = 28+13+10-8-6-5+2 = 34. Значит, общее число туристов: 34+41 = 75. Ответ: 75.

Формула в задаче 3 справедлива для любых  трёх конечных множеств А , В и С. Теперь с помощью формул из задач 2 и 3 запишем формулу в общем случае: n (A1A2…Ak) =   n (A1)+ n (A2)+…+ n (Ak) - n (A1A2) - n (A1A3)-…- n (Ak-1Ak)+ n (A1A2A3)+ n (A1A2A4)+…+(-1)^k-1* n(A1A2Ak ).

                                    14 
 

Эта формула называется формулой включений и исключений.

В частности, при k чётном, последнее слагаемое в правой части формулы имеет знак - , а при k нечётном – знак +.

Рассмотрим  уравнение с множествами.

Задача 4. Найдите множество Х, если ХА = ХА, где А – данное множество.

Решение: на основании свойства 2 операций над множествами: ХА⊂ Х ⊂  ХА. Так как ХА и ХА совпадают, то совпадают все три множества: ХА =Х= ХА. когда выполняется равенство ХА =Х? так как ХА ⊂ А, то подставляя сюда вместо ХА множество Х, получим, что Х ⊂ А. А когда выполняется равенство ХА = Х? Так как А ⊂  ХА, то А ⊂ Х. Но включения Х ⊂ А, А ⊂ Х выполняются одновременно только тогда, когда Х = А.

При Х =А на основании свойства 1: ХА = А , ХА = А.

Ответ: Х = А. 

4.Выделение  элемента множества

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

Введём  условные обозначения:

= - весы находятся в равновесии;

= - весы в неравновесии;

/ - левая чашечка весов тяжелее;

                                    15 

\ - правая чашечка весов тяжелее.

Рассмотрим  задачу, в которой известно, легче  или тяжелее фальшивая монета, чем настоящая.

Задача 1. Имеется три монеты, внешне неразличимые, из них две настоящие, одинаковой массы, одна фальшивая, легче настоящих. Можно ли найти фальшивую монету с помощью одного взвешивания на правильных чашечных весах без гирь?

Решение: занумеруем монеты числами 1,2, 3. Положим  первую монету на левую чашку весов, вторую – на правую чашку. Возможно два исхода. Весы могут оказаться в равновесии, тогда первая и вторая монеты – настоящие. Следовательно, фальшивой является третья монета. Весы могут оказаться в неравновесии. В этом случае фальшивой является или первая, или  вторая монета. Какая именно? Та, которая легче.

Ответ: можно.

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

Задача 2. Имеется три монеты, внешне неразличимые, из них 2 настоящие, одинаковой массы, одна фальшивая, отличающаяся по массе от остальных. За какое наименьшее число взвешиваний на чашечных весах без гирь можно найти фальшивую монету?

Решение: занумеруем монеты. При первом взвешивании положим на

                             16

                 =    =     

            =

левую чашку весов первую монету, на правую – вторую. В случае равновесия фальшивой является третья монета. В случае неравновесия взвешиваем одну из «старых» монет – первую или вторую с третьей. Если при втором взвешивании, например, первой монеты с третьей, получится равновесие, фальшивая монета – вторая. Если же будет неравновесие, то фальшивой является первая монета, так как неравновесие при обоих взвешиваниях можно объяснить только участием в каждом из них первой монеты.

Ответ: за два.

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

Задача 3. Имеется 4 предмета разной массы. За какое наименьшее число взвешиваний на рычажных весах без гирь можно найти самый тяжёлый и самый лёгкий из этих предметов?

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

17 

предметов этих пар (1-го и 4-го), при следующем  – двух более тяжёлых (2-го и 3-го). Самый лёгкий предмет – первый, самый тяжёлый – третий.  

                                 Ответ: за 4. 

5.Метод  перебора

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

Методом перебора широко пользуются учёные при  решении многих важных задач. Правда при этом большей частью возникает  огромное количество возможностей, что  заставляет поручить перебор ЭВМ. Для  сокращения перебора созданы специальные  методы, которые составляют новую  область математики – целочисленное  программирование.

Метод перебора широко применяется при решении задач  

                              18 
 

на  восстановление записи при выполнении действий над числами и близких  к ним задач на числовые ребусы.

Задача 1. Восстановите в примере на умножение **·**=1*1 цифры, обозначенные звёздочками. Найдите все решения.

Решение: очевидно, первые цифры множителей равны 1. Найдём их вторые цифры. Произведение двух цифр может оканчиваться единицей только в следующих трёх случаях: 1·1, 3·7, 9·9. Переберём все три возможности: 11·11=121 – подходит, 13·17=221 – не подходит, 19·19 – тем более.

Ответ: 11·11=121.

Задача 2. Восстановите запись , где каждая буква означает цифру, причём одинаковые буквы означают одинаковые цифры, разные буквы – разные цифры. Найдите все решения. (Это пример числового ребуса.)

Решение: обратим внимание на два последних  столбца. Так как в них при сложении одних и тех же цифр С и С получаются разные цифры, то в пятом столбце должно получиться в сумме на менее 10, откуда С не меньше 5. Присмотримся к третьему столбцу: когда сумма О+О может оканчиваться той же самой цифрой О? Такое возможно лишь тогда, когда О равно нулю или девяти. Но О, равный нулю быть не может, поскольку из четвёртого столбца в третий переносится 1; значит, О равно девяти. Вернёмся к цифре С. С учётом предыдущего справедливо неравенство 5 С8. Переберём все 4 возможных значения С.

Ответ: 35977+3597=71954.

                              19 
 

С помощью перебора можно решать уравнения  первой степени с двумя неизвестными в натуральных числах.

Задача 3. Решите в натуральных числах х и у уравнение 22х+13у= 1000. 

Решение: из уравнения видно, что у должно быть чётным. Кроме того, так как 22х+13у 13у, то 100013у, у =76. Следовательно, 2у76. Чтобы не перебирать все чётные числа от 2 до 76, используем соображения делимости на 11. Преобразуем следующим образом уравнение:22х+11у+2у= 1001-1, 22х+11у+(2у+1)= 1001. Так как 22х, 11у и 1001 делятся на 11, то и 2у+1 11. Первое значение у, при котором 2у+1 кратно 11, есть у=5, но оно нечётно. Следующее такое значение у, видимо, больше 5 на 11, то есть равно 16. Проверим: 2·16+1=33, а 33 делится на 11. Очередное значение у больше 16 не на 11, а на 22, значит равно 38; следующее и притом последнее значение есть 38+22= 60. Для каждого из значений у=16, 38,60 вычислим соответствующие значения х.