Название: Стоматолог Отправлено: Робинзон от Сентябрь 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 мин. |