Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 10 ] 
Автор Сообщение
 Заголовок сообщения: Олимпиада 8 класс (графы)
СообщениеДобавлено: 16 дек 2016, 12:53 
Не в сети
Начинающий
Зарегистрирован:
07 дек 2015, 22:26
Сообщений: 30
Cпасибо сказано: 17
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Добрый день!

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

В стране 120 городов. Некоторые пары городов соединены дорогами, не проходящими через другие города. Из каждого города выходит хотя бы три дороги. Докажите, что существует несамопересекающийся циклический маршрут, состоящий не более, чем из 11 городов.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Олимпиада 8 класс (графы)
СообщениеДобавлено: 16 дек 2016, 12:59 
Не в сети
Light & Truth
Зарегистрирован:
15 мар 2016, 16:08
Сообщений: 2221
Cпасибо сказано: 17
Спасибо получено:
331 раз в 316 сообщениях
Очков репутации: 116

Добавить очки репутацииУменьшить очки репутации
По моему надо искать максимальное число рёбер у графа, который не содержит циклов длины меньше 12.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Олимпиада 8 класс (графы)
СообщениеДобавлено: 16 дек 2016, 14:02 
Не в сети
Light & Truth
Зарегистрирован:
15 мар 2016, 16:08
Сообщений: 2221
Cпасибо сказано: 17
Спасибо получено:
331 раз в 316 сообщениях
Очков репутации: 116

Добавить очки репутацииУменьшить очки репутации
Проще рассуждать от противного. Допустим циклов длины меньше 12 нет. Допустим за каждый шаг мы передвигаемся к новому городу. Тогда за один шаг мы можем добраться до 3 новых городов. за два шага - до 9 новых городов и т.д. Легко видеть. что скоро новые города исчерпаются.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Олимпиада 8 класс (графы)
СообщениеДобавлено: 16 дек 2016, 14:54 
Не в сети
Начинающий
Зарегистрирован:
07 дек 2015, 22:26
Сообщений: 30
Cпасибо сказано: 17
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
searcher писал(а):
Проще рассуждать от противного. Допустим циклов длины меньше 12 нет. Допустим за каждый шаг мы передвигаемся к новому городу. Тогда за один шаг мы можем добраться до 3 новых городов. за два шага - до 9 новых городов и т.д. Легко видеть. что скоро новые города исчерпаются.


а можно поподробнее? Пока не понимаю.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Олимпиада 8 класс (графы)
СообщениеДобавлено: 16 дек 2016, 18:06 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июл 2011, 09:33
Сообщений: 15084
Откуда: Беларусь, Минск
Cпасибо сказано: 946
Спасибо получено:
3318 раз в 3066 сообщениях
Очков репутации: 642

Добавить очки репутацииУменьшить очки репутации
Solopa
Насколько мне известно, изучение теории графов не предусмотрено школьной программой. Эту теорию школьники изучают в математических кружках. Если Вы претендуете на участие в математической олимпиаде, то должны посещать такой кружок, а его руководитель должен рассматривать на занятиях те темы, которые будут использованы на олимпиаде. Это обычный подход. Необычный подход возможен, если участник олимпиады - математическое дарование... :)

Поэтому не расстраивайтесь, что Вы не понимаете, как решить эту задачу. Менее счастливым при этом быть совсем не обязательно!

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Олимпиада 8 класс (графы)
СообщениеДобавлено: 16 дек 2016, 20:19 
Не в сети
Гений
Аватара пользователя
Зарегистрирован:
14 дек 2013, 15:03
Сообщений: 653
Откуда: Москва
Cпасибо сказано: 78
Спасибо получено:
259 раз в 209 сообщениях
Очков репутации: 97

Добавить очки репутацииУменьшить очки репутации
Andy

..."Теория графов" в таких задачах используется для придания важности, задачка реально - пустяковая, если не пытаться оперировать терминологией этой самой "теории графов"...
...У каждого города - 1 вход, 2 выхода. Через 11 проходов - 2 в одиннадцатой =128 >120 вариантов проходов, т.е., по крайней мере, в одном проходе будут задействованы одинаковые города (цикл)... Или от противного, как предложил searcher, что то же самое...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Олимпиада 8 класс (графы)
СообщениеДобавлено: 16 дек 2016, 20:20 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июл 2011, 09:33
Сообщений: 15084
Откуда: Беларусь, Минск
Cпасибо сказано: 946
Спасибо получено:
3318 раз в 3066 сообщениях
Очков репутации: 642

Добавить очки репутацииУменьшить очки репутации
Dotsent
Может быть. Но явно не для обычного ученика восьмого класса.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Олимпиада 8 класс (графы)
СообщениеДобавлено: 17 дек 2016, 17:59 
Не в сети
Начинающий
Зарегистрирован:
17 дек 2016, 17:57
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Данный человек, который просил задачу учится в 8 классе Физмат школы 2007... Задача по практикуму(сложной математике) От этого пользователя уже 3 задачи за сегодня попрошено на данном сайте! :ROFL: :D1 :) А всего задач в домашеней работе 6 :good:

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Олимпиада 8 класс (графы)
СообщениеДобавлено: 17 дек 2016, 18:09 
Не в сети
Начинающий
Зарегистрирован:
17 дек 2016, 17:57
Сообщений: 2
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Andy писал(а):
Solopa
Насколько мне известно, изучение теории графов не предусмотрено школьной программой. Эту теорию школьники изучают в математических кружках. Если Вы претендуете на участие в математической олимпиаде, то должны посещать такой кружок, а его руководитель должен рассматривать на занятиях те темы, которые будут использованы на олимпиаде. Это обычный подход. Необычный подход возможен, если участник олимпиады - математическое дарование... :)

Поэтому не расстраивайтесь, что Вы не понимаете, как решить эту задачу. Менее счастливым при этом быть совсем не обязательно!

Данный человек, который просил задачу учится в 8 классе Физмат школы 2007... Задача по практикуму(сложной математике) От этого пользователя уже 3 задачи за сегодня попрошено на данном сайте! :ROFL: :D1 :) А всего задач в домашеней работе 6 :good:

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Олимпиада 8 класс (графы)
СообщениеДобавлено: 17 дек 2016, 20:16 
Не в сети
Гений
Аватара пользователя
Зарегистрирован:
14 дек 2013, 15:03
Сообщений: 653
Откуда: Москва
Cпасибо сказано: 78
Спасибо получено:
259 раз в 209 сообщениях
Очков репутации: 97

Добавить очки репутацииУменьшить очки репутации
7heAgres писал(а):
Данный человек, который просил задачу учится в 8 классе Физмат школы 2007... Задача по практикуму(сложной математике) От этого пользователя уже 3 задачи за сегодня попрошено на данном сайте! :ROFL: :D1 :) А всего задач в домашеней работе 6 :good:

Спасибо за информацию! Очень интересно! А Вы , вероятно, из пед.коллектива этой школы?...

Интересный факт... На днях писал олимпиаду (интернет-тур) один мой знакомый ученик Л2Ш. Когда время заканчивалось, я предложил ему своё решение той одной задачки, с которой он не справился... Отказался. В том смысле, что решение то я ему в конце концов рассказал, но он его не публиковал... Отношу такое его поведение на совесть педагогов Л2Ш...

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Олимпиада. Задача на графы

в форуме Задачи со школьных и студенческих олимпиад

make78

1

170

21 дек 2015, 18:11

Олимпиада 5 класс

в форуме Задачи со школьных и студенческих олимпиад

mega-ga

21

1726

02 дек 2015, 16:57

Олимпиада 6 класс (делимость)

в форуме Задачи со школьных и студенческих олимпиад

Solopa

2

123

16 дек 2016, 11:49

Олимпиада 6 класс (площади)

в форуме Задачи со школьных и студенческих олимпиад

Solopa

5

219

18 ноя 2016, 13:23

Олимпиада по математике 3 класс

в форуме Задачи со школьных и студенческих олимпиад

ivan1212

32

1592

27 янв 2015, 23:40

Олимпиада 3й класс, очень сложно

в форуме Задачи со школьных и студенческих олимпиад

scoobydog1

8

212

19 апр 2017, 20:01

Докажите неравенство (11 класс, олимпиада)

в форуме Задачи со школьных и студенческих олимпиад

Solopa

31

646

19 сен 2016, 15:36

На Марсе 2000 стран (Городская Олимпиада, 8 класс, 1997 год)

в форуме Задачи со школьных и студенческих олимпиад

Xenia1996

3

110

11 сен 2017, 15:58

Графы.Циклы.Частичные графы

в форуме Дискретная математика, Теория множеств и Логика

Jaspe123

0

176

13 дек 2013, 23:14

Графы

в форуме Дискретная математика, Теория множеств и Логика

ksenechkaj

0

235

28 дек 2011, 19:13


Часовой пояс: UTC + 4 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved