Страниц: [1]
  Печать  
Автор Тема: Стоматолог  (Прочитано 4412 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Робинзон
Давненько
**
Offline Offline

Сообщений: 75

СПАСИБО
-вы поблагодарили: 63
-вас поблагодарили: 9


Просмотр профиля
: Сентябрь 27, 2014, 18:50:00 �

В очереди к стоматологу стоят 30 ребят: мальчики и девочки. Часы на стене показывают 8:00. Как только начинается новая минута, каждый мальчик, за которым стоит девочка, пропускает ее вперед. Докажите, что перестановки в очереди закончатся до 8:30, когда откроется дверь кабинета.

Мальчики -  джентльмены, не правда ли?
Записан
Робинзон
Давненько
**
Offline Offline

Сообщений: 75

СПАСИБО
-вы поблагодарили: 63
-вас поблагодарили: 9


Просмотр профиля
Ответ #1 : Октябрь 06, 2014, 14:24:04 �

Неужели, никто не решил эту задачу за столь длительное время? Конечно, изложить решение тут трудно (оно не очень короткое), но подайте сигнал о том, что вы её сделали.     
Записан
Руслан Дехтярь
Гость
Ответ #2 : Октябрь 06, 2014, 15:15:02 �

А что тут доказывать?
Даже если бы девочка была только одна, и стояла бы на последнем месте, то переместится она могла до 1-го. И этих перемещений было бы максимум 29.
Записан
семеныч
Ум
*****
Offline Offline

Сообщений: 9210

СПАСИБО
-вы поблагодарили: 2
-вас поблагодарили: 2467



Просмотр профиля Email
Ответ #3 : Октябрь 06, 2014, 15:53:47 �

стоматолог то слово неплохое

100 мат О  лог
Записан

звездовод-числоблуд
Робинзон
Давненько
**
Offline Offline

Сообщений: 75

СПАСИБО
-вы поблагодарили: 63
-вас поблагодарили: 9


Просмотр профиля
Ответ #4 : Октябрь 06, 2014, 18:42:34 �

R2D2, что значат слова "даже если 1 девочка"? Вообще, не очень понятно,что будет,когда их будет 2,3 и т. д.
Записан
снн
Гений-Говорун
*
Offline Offline

Сообщений: 1570

СПАСИБО
-вы поблагодарили: 1786
-вас поблагодарили: 1202


Просмотр профиля
Ответ #5 : Октябрь 06, 2014, 20:52:55 �

Если 1-мальчик, 0 - девочка, а число 30 сократить для показательности "выступления" до 10, то ситуацию можно представить следующими способами:
1. мальчиков и девочек поровну и стоят они не вперемешку.
    1111100000
  перестановки:
    1111010000
    1110101000
    1101010100
    1010101010
    0101010101
    0010101011
     0001010111
    0000101111
    0000011111
всего 9 перестановок ( соответствует 29 для 30 ребят) как видно, любой вид перемешивания равного количества девочек и мальчиков уменьшает число перестановок, т.е. в таких комбинациях тоже до 8.30 уложатся.

2. число мальчиков больше ( меньше) девочек.
    1111000000
    перестановки:
    1110100000
    1101010000
    1010101000
    0101010100
    0010101010
    0001010101
    0000101011
    0000010111
    0000001111
тоже 9 перестановок, причем вперемешку ( т.е. уже при свершившейся как-бы перестановке) количество инверсий уменьшается.


   
Записан
Руслан Дехтярь
Гость
Ответ #6 : Октябрь 08, 2014, 19:35:20 �

R2D2, что значат слова "даже если 1 девочка"? Вообще, не очень понятно,что будет,когда их будет 2,3 и т. д.
Максимальное число рокировок (девочка- мальчик) будет если девочек всего 2. Стоят они последними. То есть, девочки поменяются местами с каждвм мальчиком. Девочка, изначально стоящая на последнем месте, поменяется местами с 28 мальчиками и еще на первой минуте не сдвинется с места. Итого 29 мин.
Записан
Страниц: [1]
  Печать  
 
Перейти в: