Форум умных людей

Задачи и головоломки => Логические задачи и головоломки => Тема начата: Робинзон от Сентябрь 27, 2014, 18:50:00



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

Мальчики -  джентльмены, не правда ли?


Название: Re: Стоматолог
Отправлено: Робинзон от Октябрь 06, 2014, 14:24:04
Неужели, никто не решил эту задачу за столь длительное время? Конечно, изложить решение тут трудно (оно не очень короткое), но подайте сигнал о том, что вы её сделали.     


Название: Re: Стоматолог
Отправлено: Руслан Дехтярь от Октябрь 06, 2014, 15:15:02
А что тут доказывать?
Даже если бы девочка была только одна, и стояла бы на последнем месте, то переместится она могла до 1-го. И этих перемещений было бы максимум 29.


Название: Re: Стоматолог
Отправлено: семеныч от Октябрь 06, 2014, 15:53:47
стоматолог то слово неплохое

100 мат О  лог


Название: Re: Стоматолог
Отправлено: Робинзон от Октябрь 06, 2014, 18:42:34
R2D2, что значат слова "даже если 1 девочка"? Вообще, не очень понятно,что будет,когда их будет 2,3 и т. д.


Название: Re: Стоматолог
Отправлено: снн от Октябрь 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 перестановок, причем вперемешку ( т.е. уже при свершившейся как-бы перестановке) количество инверсий уменьшается.


   


Название: Re: Стоматолог
Отправлено: Руслан Дехтярь от Октябрь 08, 2014, 19:35:20
R2D2, что значат слова "даже если 1 девочка"? Вообще, не очень понятно,что будет,когда их будет 2,3 и т. д.
Максимальное число рокировок (девочка- мальчик) будет если девочек всего 2. Стоят они последними. То есть, девочки поменяются местами с каждвм мальчиком. Девочка, изначально стоящая на последнем месте, поменяется местами с 28 мальчиками и еще на первой минуте не сдвинется с места. Итого 29 мин.