2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Кошка Ксюшка и теория графов
Сообщение27.06.2011, 11:29 


01/10/10

2116
Израиль (племянница БизиБивера)
Конспиративная квартира межгалактической разведки Леншкола представляет собой

а) квадрат размером $n\times n$,
б) куб размером $n\times n\times n$,

разделённый стенами на квадратики (кубики) – комнаты размером $1\times 1$ ($1\times 1\times 1$). Между каждыми двумя соседними по стене (потолку) комнатами есть дверь (люк), но сейчас все двери заперты. Для каждого натурального $n>1$ найти, какое наименьшее число дверей нужно открыть, чтобы Кошка Ксюшка, сидевшая в одной из комнат, могла гулять по всей квартире?

 Профиль  
                  
 
 Re: Кошка Ксюшка и теория графов
Сообщение27.06.2011, 12:06 


14/01/11
3065
а)$n^2-1$,
б)$n^3-1$.

Достаточность этого количества подтверждается очевидным примером. Необходимость вытекает из факта, что в любом связном графе с n вершинами хотя бы n-1 ребро.

 Профиль  
                  
 
 Re: Кошка Ксюшка и теория графов
Сообщение27.06.2011, 12:10 


01/10/10

2116
Израиль (племянница БизиБивера)
:wink: 8-)

(Оффтоп)

Задачка, конечно, лёгкая. Но, согласитесь, условие Вам понравилось.

 Профиль  
                  
 
 Re: Кошка Ксюшка и теория графов
Сообщение27.06.2011, 12:15 


14/01/11
3065

(Оффтоп)

Да, напомнило фильм "Куб".

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

Модераторы: Модераторы Математики, Супермодераторы



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

Сейчас этот форум просматривают: mihaild, YandexBot [bot]


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group