» Задачки, головоломки

veprus

Цитата:

Нет, такого условия нет. Есть просто какое-то количество дорог между городами. Но условия, что каждый с каждым соединен - нет.

тогда задача вообще решения не имеет. так как вариантов может быть сколько хочешь и в одних можно это сделать в других нельзя, а общего решения под которое попадали бы все варианты нет. тогда и при нечетном нельзя если допустим все города в линию вытянуты и при четном можно. если они в кольцо соеденены.
В общем тогда ИМХО смысл вообще теряется.

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

тут связано с количеством дорог исходящих из одого города. Вроде бы

Цитата:

Необходимое условие чтобы из каждого города выходило четное количество дорог-тогда можно, во всех других случаях нельзя.

Ага, правильно. Осталось доказать, что это условие необходимое и достаточное.

Цитата:

и достаточное.

попытаемся...

на возможность положительного решения оказать влияние могут два фактора
А количество городов (четное или нечетное)
В количество дорог выходящих из каждоого города (четное или нечетное)

имеется необходимое условие
Цитата:

чтобы из каждого города выходило четное количество дорог

при четном или нечетном количестве городов это условие может как выполнятся так и не выполнятся, следовательно от четности или нечетности числа количества городов не зависит результат, он может быть как положительным так и отрицательным.
количество дорог выходящих из каждого города может принимать три вида
1. из всех нечетное
2. из всех четное
3. смешенное (из некоторых четное из некоторых нечетное)
из необходимого условия мы видим что для достижения положительного результата однозначно необходимо выполнение условия 2, при двух других вариантах решение отрецательное
следовательно:
фактор А не влияет на результат
в фактор В обнозначно положительное решение дает пункт 2,
отсюда пункт 2 фактора В является достаточным условиям для положительного решения задания, т.к. другие варианты либо приводят к отрицательному решению либо не оказывают влияния на полученный результат.

Вообще-то ета задача известна как Задача Мостов и не помню уж какой великий математик накатал целый трактат с доказатальством что и как.

Я не математик, но моя теория такая:

Если число дорог чётное, то возможны две ситуации:
1. пришёл-ушёл-пришёл...-ушёл - промежуточная станция
2. ушёл-пришёл...-пришёл - начальная и конечная станция

Если число дорог нечётное, то возможны две ситуации:
1. пришёл-ушёл-...-пришёл - конечная станция
1. ушёл-пришёл...-ушёл - начальная станция

Отсюда выводы:
1. Если городов с нечетным количеством дорог больше чем два, то задача неразрешима, ибо такие города являются либо начальной, либо конечной точкой, но не промежуточной.

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

3. Если только один город с нечетным количеством дорог, то задача неразрешима, ибо город с четными дорогами должен быть либо промежуточным, либо одновременно и начальным и конечным, а нечётный не может быть промежуточным.

4. Если городов с нечетным количеством дорог нет, то задача разрешима, один
город с четными дорогами будет и начальным и конечным, остальные города с чётными дорогами являются промежуточными.

Цитата:

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

нет, по условию надо вернуться в тот же город
т.е. у тебя остался пунк 4 а это было уже сказано

vzbzdnov

Хорошее рассуждение. Оно показывает, что если есть города с нечетным количеством дорог, то задача решения не имеет. Т.е. ты доказал НЕОБХОДИМОСТЬ условия. Теперь еще надо доказать достаточность. Т.е. если все же из каждого города выходит четное количество дорог, то можно проехать по каждой дороге по одному разу и вернуться в начальный город.

нда... алгоритм объезда городов простой, а его правильность не знаю как доказать

Цитата:

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

Предположим, что это нельзя сделать и что если по всем дорогам проехать по одному разу, то окажешься в другом городе. Тогда получится, что один город начальный, а другой конечный, что противоречит нашей лемме, что город с чётными дорогами должен быть либо промежуточным, либо одновременно начальным и конечным. Отсюда вывод - предположение ложно и такой маршрута нет. Вывод можно даже усилить - если есть только города с чётными дорогами, то ИЗ КАЖДОГО города можно объехать все дороги по разу и вернуться.

vzbzdnov

Цитата:

то ИЗ КАЖДОГО города можно объехать

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

Цитата:

а как быть с "объехать все дороги"?

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

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

Пропущенные дороги:
I. либо попарно соединяют города (А-Б, Б-А), то есть в следующий раз надо просто сбегать туда-сюда,
II. либо города в кольце (А-Б, Б-В, В-Г, Г-А иначе имеем нечётный город), то есть в следующий раз надо просто сбегать по кругу.

Иначе быть не может, то есть А-Б, Б-В, В-Г, Г-Д невозможно, поскольку крайние города становятся нечётными

vzbzdnov

Немного сумбурно, но пойдет. Задача с городами решена.

Добавлено
Решение задачи с многоугольником и серединами его сторон.

Первое решение. Лобовое - предложил Reagent. Пусть (v_1,u,_1),...,(v_n,u_n) - координаты середин сторон, (x_1,y_1),...,(x_n,y_n) - искомые координаты вершин. Тогда получаем систему уравнений
x_1+x_2=2v_1,
y_1+y_2=2u_1,
......................
x_n+x_1=2v_n,
y_n+y_1=2u_n.

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

Второе решение. Оно построено на следующей идее. Возьмем первую вершину и начнем ее поворачивать на 180 градусов вокруг каждой из середин. Т.е. берем первую середину - поворачиваем. Она переходит во вторую вершину. Берем теперь вторую середину и поворачиваем ее образ (т.е. вторую вершину). Она переходит в 3-ю вершину. И т.д. Когда мы повернем нашу вершину вокруг всех середин - должны вернуться в исходную вершину.

Теперь немного формул. Если мы поворачиваем точку с координатами (x,y) вокруг точки с координатами (v,u) на 180, то координаты новой точки (2v-x,2u-y).

Берем первую вершину (x_1,y_1) и поворачиваем ее последовательно вокруг всех середин. После всех поворотов ее координаты будут:
(2v_n-2v_{n-1}+...+(-1)^{n+1}2v_1+(-1)^{n+2}x_1,2u_n-2u_{n-1}+...+(-1)^{n+1}2u_1+(-1)^{n+2}y_1)=(x_1,y_1) (как мы заметили выше). Теперь, если n четное, мы получаем, что 2v_n-2v_{n-1}+...+(-1)^{n+1}2v_1=2u_n-2u_{n-1}+...+(-1)^{n+1}2u_1=0, т.е. ЛЮБАЯ точка на плоскости удовлетворяет нашим условиям, следовательно, при четном n многоугольник восстановить нельзя. Если же n нечетное, то тогда
x_1=v_n-v_{n-1}+...+(-1)^{n+1}v_1, y_1=u_n-u_{n-1}+...+(-1)^{n+1}u_1 и многоугольник восстанавливается однозначно (остальные вершины - поворотами).

Цитата:

что-то еще от Horex

Недавно мне попался отрывок пьесы современного автора.

Ммм. Что-то глухо. Посчитайте, сколько персонажей, пофантазируйте, что может быть описано таким образом...

Horex
на самом деле, имхо, трудно сообразить... слишком уж абстрактно

Что-то мне подсказывает, что это некая планета

Cдается мне ,это Земля,а домик солнечная система!

Horex
только ответ не пиши придумаю

Добавлено
ну, мурига, точно ведь такую лафу испортил )

Итак, отгадали. А теперь загадка из 4 класса без звездочки.

На крыльце стоит корзинка с грибами. Вес грибов 2 кг, влажность 99%. После того как корзинка день простояла на солнце влажность уменьшилась до 98%. Сколько стали весить грибы.

Цитата:

На крыльце стоит корзинка с грибами. Вес грибов 2 кг, влажность 99%. После того как корзинка день простояла на солнце влажность уменьшилась до 98%. Сколько стали весить грибы.

Действительно, 4 класс без *. Хотя некоторых людей, решивших посчитать на бумажке, результат удивит.

а че там считать... процент грибов возрос в два раза, соответственно, вес уменьшился в два раза

Sleepwalker
Гм... Действительно Я помнил, что ответ красивый, но в лоб решал.

Тема заглохла, пора оживить, не слишком сложная штучка!
На арене небольшого цирка выступает группа наездников.Если подсчитать участников номера(лошадей и всадников) по головам и ногам, то всего наберётся 18 голов и 50 ног.Кроме того,в зверинце при цирке содержаться дикие животные.Если пересчитать их по головам и ногам, то получиться 11 голов и 20 ног.Среди них четвероногох вдвое больше ,чем двуногих.Сколько наездников и лошадей выступает в цирке и сколко животных содержится в зверинце?

Цитата:

11 голов и 20 ног

чегото я не въехал, там пару животных одноногие? 11*2=22 ???????

Цитата:

18 голов и 50 ног

7 лошадей и 11 всадников

Цитата:

11 голов и 20 ног.Среди них четвероногох вдвое больше ,чем двуногих

4 четвероногих, 2 двуногих и 5 змей

vzbzdnov
Правильно!

Добавлено
Корова стоит 10 $ ,свинтя - $, овца - 0,5 $. Фермер купил по крайней мере 1 корову,1 свинью и 1 овцу,израсходоваыв на покупку всего 100 $.Сколько и каких животных он купил?

Добавлено
Имеем 10 монет и 3 стакана,надо разложить монеты в стаканы так, чтобы в каждом было нечётное количество монет?всего 15 решений!приведите все !

Добавлено
Один мальчик с увлечением занимался разведением золотых рыбок,потом это занятие ему надоело и он решил продать всех своих рыбок.Своё решение он осуществил в следующем порядке:
1.Продал половину всех своих рыбор и ещё полрыбки.
2.Продал треть оставшихся рыбок и ещё треть рыбки.
3.Продал четверть оставшихся рыбок и ещё четверть рыбки.
4.Продал пятую часть оставшихся рыбок и ещё одну пятую рыбки.
После этого у него осталось 19 рыбок.Разумеется,с золотыми рыбками он оброщался бережно и ему не приходило в голову делить рыбку на части.сколько рыбок у него было в начале?

Цитата:

Корова стоит 10 $ ,свинтя - $, овца - 0,5 $. Фермер купил по крайней мере 1 корову,1 свинью и 1 овцу,израсходоваыв на покупку всего 100 $.Сколько и каких животных он купил?

А где прикол? Уж очень вольное условие. Наверное. ещё что-то должно быть и об общем количестве. А так мульён решений.
9 Коров, 9 свиней 2 овцы или 1 корову, 89 свиней, 2 овцы или 1 корову 1 свинью и 196 овец и т.д.

Цитата:

Имеем 10 монет и 3 стакана,надо разложить монеты в стаканы так, чтобы в каждом было нечётное количество монет?всего 15 решений!приведите все !

Я так понимаю, что поскольку не сказано, что надо разложить все монеты, то решений ещё больше 111 113 115 117 131 133 135 151 153 171 311 313 315 331 333 511 513 531 711
А вот если все, то задача не решается

Про рыбок пусть второклассники решают, они дроби проходят

О! Вспомнил, как надо! Задачка для 2го класса.
Корова стоит 10$,свинья - 1$, курица - 0,1$. Фермер купил 100 животных и по крайней мере 1 корову,1 свинью и 1 курицу, израсходовав на покупку 100$. Сколько и каких животных он купил? [/q]

vzbzdnov

Цитата:

Я так понимаю, что поскольку не сказано, что надо разложить все монеты, то решений ещё больше 111  113 115 117 131 133 135 151 153 171 311  313 315 331 333 511 513 531 711  
А вот если все, то задача не решается

Ты не прав!!!Задача именно в том ,что-бы разложить ВСЕ монеты, и имеет как минимум 15 решений!

Muriga
делим 10 монет на 2 нечетные кучки, одну из них кладем в стакан другую делим на четные и нечетные, кладем четные в другой стакан и в этот же стакан, вставляем стакан с нечетным числом.

количество вариантов считать влом, но задача решена.

nsadm
У меня так 10 только выходило..

короче 15 вариантов там (+5 вариантов с пустым стаканом)