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

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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 14 ]  На страницу 1, 2  След.
Автор Сообщение
 Заголовок сообщения: Какое наибольшее число веревочек можно перерезать?
СообщениеДобавлено: 30 янв 2015, 10:16 
Не в сети
Начинающий
Зарегистрирован:
30 янв 2015, 10:05
Сообщений: 1
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Волейбольная сетка имеет вид прямоугольника размером 50×600 клеток. Какое наибольшее число веревочек можно перерезать так чтобы сетка не распалась на куски?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как решить
СообщениеДобавлено: 30 янв 2015, 10:20 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июл 2011, 09:33
Сообщений: 17580
Откуда: Беларусь, Минск
Cпасибо сказано: 1221
Спасибо получено:
3745 раз в 3466 сообщениях
Очков репутации: 710

Добавить очки репутацииУменьшить очки репутации
Tanj, нужно оставить верёвочки, которые образуют периметр прямоугольника сетки, т. е. две горизонтальные и две вертикальные верёвочки. Остальные можно перерезать. Вам остаётся только посчитать. :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как решить
СообщениеДобавлено: 30 янв 2015, 11:39 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 4006
Cпасибо сказано: 70
Спасибо получено:
855 раз в 777 сообщениях
Очков репутации: 204

Добавить очки репутацииУменьшить очки репутации
Andy, к сожалению это не подходит. Внутренность то упадет.
Задачу можно переформулировать так - найти связный граф с минимальным количеством ребер, у которого вершины расположены в целочисленных точках прямоугольника 50х600.

Upd. Даже не так, у нас же есть изначальный граф. Ну, надеюсь, понятно...

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как решить
СообщениеДобавлено: 30 янв 2015, 12:07 
Не в сети
Light & Truth
Зарегистрирован:
28 фев 2012, 19:40
Сообщений: 2209
Cпасибо сказано: 433
Спасибо получено:
1043 раз в 768 сообщениях
Очков репутации: 9

Добавить очки репутацииУменьшить очки репутации
Волейбольная сетка имеет вид прямоугольника размером 50 × 600 клеток. Какое наибольшее число веревочек можно перерезать так, чтобы сетка не распалась на куски?
Решение:
Будем рассматривать волейбольную сетку как граф, вершинами которого являются узлы сетки, а ребрами – веревочки. В этом графе нужно удалить как можно больше ребер так, чтобы он остался связным. Будем убирать ребра по очереди до тех пор, пока это возможно. Заметим, что если в графе есть цикл, то возможно удаление любого ребра этого цикла. Связный граф, не имеющий циклов, является деревом. Поэтому, только получив дерево, мы не сможем убрать ни одного ребра. Подсчитаем число ребер в нашем графе в этот момент. Количество вершин осталось тем же – 51 • 601 = 30651. Число ребер в дереве на 1 меньше числа вершин и, следовательно, в нашем дереве будет 30650 ребер. Сначала же их было 601 • 50 + 600 • 51 = 60650. Таким образом, можно удалить 30000 ребер, то есть у волейбольной сетки можно перерезать 30000 веревочек (но не более!). http://zaba.ru/cgi-bin/tasks.cgi?tour=b ... solution=1

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как решить
СообщениеДобавлено: 30 янв 2015, 12:12 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 4006
Cпасибо сказано: 70
Спасибо получено:
855 раз в 777 сообщениях
Очков репутации: 204

Добавить очки репутацииУменьшить очки репутации
Да, примерно такое решение я и имел ввиду. Надо еще только привести пример такого графа, но это просто.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Как решить
СообщениеДобавлено: 30 янв 2015, 12:13 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июл 2011, 09:33
Сообщений: 17580
Откуда: Беларусь, Минск
Cпасибо сказано: 1221
Спасибо получено:
3745 раз в 3466 сообщениях
Очков репутации: 710

Добавить очки репутацииУменьшить очки репутации
swan писал(а):
Andy, к сожалению это не подходит. Внутренность то упадет.
Задачу можно переформулировать так - найти связный граф с минимальным количеством ребер, у которого вершины расположены в целочисленных точках прямоугольника 50х600.

Upd. Даже не так, у нас же есть изначальный граф. Ну, надеюсь, понятно...

swan, по-моему, ещё одна задача с "нехорошей" формулировкой... Мне бы и в голову не пришло рассматривать граф как модель волейбольной сетки. :o

Что значит "внутренность ... упадёт"? Волейбольная сетка привязывается к стойкам в четырёх углах.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Какое наибольшее число веревочек можно перерезать?
СообщениеДобавлено: 30 янв 2015, 12:38 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 4006
Cпасибо сказано: 70
Спасибо получено:
855 раз в 777 сообщениях
Очков репутации: 204

Добавить очки репутацииУменьшить очки репутации
Тут стойки вообще не рассматриваются. Здесь имеется ввиду сетка как самостоятельный объект. А волейбольная говорит лишь о ее виде.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Какое наибольшее число веревочек можно перерезать?
СообщениеДобавлено: 30 янв 2015, 12:41 
Не в сети
Light & Truth
Аватара пользователя
Зарегистрирован:
16 июл 2011, 09:33
Сообщений: 17580
Откуда: Беларусь, Минск
Cпасибо сказано: 1221
Спасибо получено:
3745 раз в 3466 сообщениях
Очков репутации: 710

Добавить очки репутацииУменьшить очки репутации
swan, тогда и надо говорить о графе в виде сетки, а не о волейбольной сетке. Впрочем, ладно. Главное, чтобы автор вопроса поняла суть задачи.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Какое наибольшее число веревочек можно перерезать?
СообщениеДобавлено: 30 янв 2015, 12:55 
Не в сети
Light & Truth
Зарегистрирован:
28 фев 2012, 19:40
Сообщений: 2209
Cпасибо сказано: 433
Спасибо получено:
1043 раз в 768 сообщениях
Очков репутации: 9

Добавить очки репутацииУменьшить очки репутации
Там мысль такая: если из полного графа на n вершинах удалить (n – 2) рёбер, то граф останется связным.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Какое наибольшее число веревочек можно перерезать?
СообщениеДобавлено: 30 янв 2015, 13:17 
Не в сети
Light & Truth
Зарегистрирован:
06 дек 2014, 10:11
Сообщений: 4006
Cпасибо сказано: 70
Спасибо получено:
855 раз в 777 сообщениях
Очков репутации: 204

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

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
На какое число можно было бы разрезать моток верёвки?

в форуме Алгебра

ilonka

1

387

11 апр 2014, 18:58

Какое наибольшее количество равнобедренных треугольников

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

Anchikov

3

844

22 дек 2013, 11:39

Какое число зашифровано?

в форуме Алгебра

roman4rever

17

733

16 сен 2013, 18:38

Какое число больше?

в форуме Алгебра

Talanov

12

674

29 дек 2013, 05:43

Какое число могла написать Юля?

в форуме Размышления по поводу и без

Xenia1996

2

77

02 окт 2017, 16:45

Какое число больше -1 в два раза

в форуме Размышления по поводу и без

Supermega Tro-lo-lo

9

221

10 окт 2017, 14:36

Какое наибольшее количество верных ответов может быть у Миши

в форуме Алгебра

VICTORQQQQ

1

111

02 мар 2017, 16:06

Какое наименьшее число раз подбросить игральную кос

в форуме Теория вероятностей

mari123

1

259

19 авг 2015, 23:30

Задача на логику: определить, какое число зашифровано

в форуме Алгебра

roman4rever

1

403

12 сен 2013, 20:07

Дана последовательность Какое число не появится в этой после

в форуме Алгебра

VICTORQQQQ

3

88

11 апр 2017, 22:01


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



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

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


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

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

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

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