Эзотерика и оккультизм
Вы не зашли.
Задачи по математике.
Серия 2.
7/9 (Карпов). Учительница дала отличнице Кате четыре положительных числа. Катя написала на доске числа 3,4 и 7 и сказала, что каждое из них является суммой каких-то трёх из четырёх данных ей чисел. Докажите, что Катя ошиблась.
13/44 (Голованов). Каждое из двух натуральных чисел равно сумме трёх различных собственных делителей другого (собственным делителем числа называется отличный от него натуральный делитель). Докажите, что эти два числа равны.
12/39 (Ростовский). В Однобоком графстве между некоторыми (но, к сожалению, ещё не всеми) усадьбами проложены дороги с односторонним движением. При этом при появлении любой новой дороги (также с односторонним движением) между усадьбами, не соединёнными дорогой до этого, появится возможность добраться от любой усадьбы до любой другой, не нарушая правил. Докажите, что такая возможность имеется уже сейчас.
14/48 (студентам посвящается, Косовская). В роте из 109 солдат каждый день трое выходят в наряд. Докажите, что можно составить такой график нарядов, что через некоторое время любые два солдата побывают вместе ровно в трёх нарядах.
16/59 (Голованов). Число N равно произведению 200 различных натуральных числе. Докажите, что N имеет не меньше 19901 различных натуральных делителей (включая, разумеется, 1 и само себя).
17/62 (Берлов, Иванов). Будем называть натуральное число «почти простым», если оно не делится ни на одно простое число из интервала [3,19]. Будем называть число «очень непростым», если оно имеет хотя бы два простых делителя из интервала [3,19]. Какое наибольшее количество почти простых чисел можно выбрать так, чтобы любые два из них в сумме давали очень непростое число.
Неактивен
a>0; b>0; c>0; d>0
n=a+b+c+d
Выразим суммы в таком виде
n-a=3
n-b=4
n-c=7
(a,b,c выбраны произвольно, общность не нарушается)
отсюда
a=c+4
b=c+3
n=c+7
тогда сумма n=a+b+c+d запишется в виде:
c+3+c+4+c+d=c+7
d=-2c
что невозможно, т.к. с>0; d>0
От противного
1)Предположим, что есть такие усадьбы А и B, что из усадьбы A нельзя попасть в усадьбу B на данный момент. Рассмотрим множество Аi усадьб в которые можно попасть из усадьбы А (включая саму усадьбу А) и множество Bj усадьб из которых можно попасть в усадьбу B(включая B)
тогда
2) У этих множеств нет общих членов (т.к. иначе из А можно было бы попасть в общую усадьбу Аn, которая являлась бы членом множества Bm и следовательно из неё можно было бы попасть в В. Это не согласуется с предположением 1)
3) Предположим, что есть две усадьбы Ak и Bp, не соединённые дорогой тогда если мы проведём дорогу BpAk (пишем как в "векторном виде" начало и конец), то она никак не повлияет на возможность попасть из А в В, т.к. обитатель усадьбы А может воспользоваться ей только в том случае, если может попасть в Bp (что невозможно согласно пункту 2)), а по условию "при появлении любой новой дороги (также с односторонним движением) между усадьбами, не соединёнными дорогой до этого, появится возможность добраться от любой усадьбы до любой другой, не нарушая правил".
Следовательно таких двух усадеб (Ak и Bp, не соединённых дорогой) нет. И согласно пункту 2) они могут быть соединены только дорогой вида BpAk.
4) Таким образом из предположения 1) мы получили, что не можем новой дорогой соединить усадьбу подмножества Аi с усадьбой подмножества Вj, то есть мы не можем провести дорогу так, чтобы из А можно было попасть в В. Т.к. если есть усадьбы не входящие ни в одно из этих множеств, то нам придётся провести минимум 2 дороги- одну чтобы усадьба D попала в множество Аi и одну чтобы она попала в множество Bj.
Получили противоречие с условием.
как-то депрессивно получились последние пункты :/
Отредактированно Guest (29-10-2005 15:01:13)
Первая вроде бы верно решена.
Во второй - ошибка. У множеств могут быть общие члены (Вы забываете, что граф ориентированный).
Привожу контрпример (есть общие точки, однако из A в B не попасть).
p.s.
Для неориентированного графа, кстати, утверждение неверно. Возьмите дерево и выкиньте одну вершину.
Неактивен
Ориентация уже лежит в формулировках множеств
В вашем примере в множестве Bi (точек ИЗ которых можно попасть в В, включая В) только один член (только из В можно попасть в В). Соответственно, в множестве А 4 члена (считая А), но пересечения множеств нет.
Просто в решении надо было заострить внимание на этих предлогах.
Идея решения в целом проста: для любых двух усадеб Аi и Вj можно провести "бесполезную" дорогу, т.к. она направлена к множеству А. Это нарушит условие, ведь эта дорога никак не влияет на возможность добраться из А в В. Далее уже вполне обоснованные выводы... перечитайте решение.
Примечание на всякий случай: под возможностью добраться, которая лежит в нашем разделении на множества подразумевается, можно ли впринципе добраться (пусть и через другие усадьбы).
Отредактированно Guest (30-10-2005 10:26:16)
Контрпример к задаче о графствах.
Пусть есть группы усадеб A и B. Между любой парой A проложена пара односторонних путей(полный подграф) , аналогично с классом B. Также, постоены дороги из любой усадьбы из B в любую из A.
В настоящий момент ни из одной усадьбы класса A нельзя попасть ни в одну усадьбу класса B, но добавив одну _любую_(каковой может оказаться только дорога соединяющая какую-то усадьбу A с какой-то B) окажется возможным любое перемещение.
Если даже подразумевалось что между любой парой усадеб либо нет прямой дороги либо есть дорога только в одном направлении, простой пример с 3 усадьбами показывает что условие также нарушается.(Есть дорога из 1 в 2 и есть из 2 в 3, тогда единственная возможнопрокладываемая дорога будет из 3 в 1)
1apr:
Гм, это не контрпример, а ошибка.
Докажем это на Вашем примере.
Пусть у нас есть три усадьбы - Гавсфолово, Хрюкфилд и Большие Лесищи. И пусть (как Вы просите) есть дороги между Гафсфолово и Хрюкфилдом (в сторону последнего) и между Хрюкфилдом и Большими Лесищами. Вы утверждаете, что, если проложить дорогу между Большими Лесищами и Гавсфолово, то можно будет попасть откуда угодно куда угодно. Да, это верно. ОДНАКО условие ТРЕБУЕТ:
При этом при появлении ЛЮБОЙ новой дороги (также с односторонним движением) между усадьбами, не соединёнными дорогой до этого, появится возможность добраться от любой усадьбы до любой другой, не нарушая правил
Что же, проведём дорогу из Гавсфолово в Большие Лесищи. Тогда из последних нельзя будет, к примеру, попасть в Хрюкфилд. Следовательно, условие задачи нарушается.
Am I Evil:
Ваше решение не может быть верным, так как опирается на некорректные высказывания.
Решение называется верным, если оно при помощи цепочки импликаций к нему можно прийти из истинного утверждения. В Вашей цепочке есть ложное утверждение. А из лжи следует всё, что угодно. Измените указанный пункт. Быть может, решение и будет верным. РЕШЕНИЕ не может быть корректным НАПОЛОВИНУ. Оно либо корректно, либо некорретно. Иного не дано.
Евгений и Елена.
Неактивен
Елена, формально вы правы, ошибка есть, варианта в таком случае два, один из которых вовсе исключит возможность попадать куда угодно. Но суть осталась неизменной: утверждение которое требуется доказать-неверно.
Согласен, нёс ахинею, этот пример c тройкой не вписывается в условие.
Если графства могут соединяться попарно только в одну сторону то
Если А не соединёно с Б, добавив дорогу из А в Б достижимость А из Б не изменится, а по условию должно оказаться достижимо, следовательно изначально А было достижимо из Б.
Если решение идёт от противного-естественно оно будет идти от ложного утверждения.
Нам надо доказать, что такая возможность (добраться от любой до любой) есть уже сейчас. А мы предполагаем, что это неверно (что хотя бы из одной усадьбы А в другую В добраться нельзя). И показываем что такое предположение неверно. Значит на данный момент нельзя выбрать такие две усадьбы (нарушается условие). Это равносильно тому, что можно попасть из любой усадьбы в любую, что и требовалось доказать...
Или вы видите ложное утверждение в другом? Просто выделите это предложение.