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

Математический форум 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
Сообщений: 2724
Cпасибо сказано: 20
Спасибо получено:
399 раз в 379 сообщениях
Очков репутации: 122

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

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

Добавить очки репутацииУменьшить очки репутации
Проще рассуждать от противного. Допустим циклов длины меньше 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
Сообщений: 15507
Откуда: Беларусь, Минск
Cпасибо сказано: 991
Спасибо получено:
3436 раз в 3176 сообщениях
Очков репутации: 666

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

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

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

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

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

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

Добавить очки репутацииУменьшить очки репутации
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
Сообщений: 670
Откуда: Москва
Cпасибо сказано: 82
Спасибо получено:
262 раз в 211 сообщениях
Очков репутации: 97

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

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

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

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

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

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

make78

1

204

21 дек 2015, 18:11

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

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

mega-ga

21

1806

02 дек 2015, 16:57

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

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

ivan1212

32

1668

27 янв 2015, 23:40

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

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

Solopa

5

245

18 ноя 2016, 13:23

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

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

Solopa

3

172

16 дек 2016, 11:49

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

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

Solopa

31

755

19 сен 2016, 15:36

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

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

scoobydog1

8

240

19 апр 2017, 20:01

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

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

Xenia1996

3

141

11 сен 2017, 15:58

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

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

Jaspe123

0

189

13 дек 2013, 23:14

Графы

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

manchester_alan

2

97

09 май 2016, 14:14


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



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

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


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

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

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

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