Задачи на собеседовании в одну небезызвестную контору

[CDR]

Задачки, которые были предложены одному моему знакомому, работающему за бугром, на собеседовании в Google .

Чувак в автобусе.
На остановке в ожидании 71-местного автобуса стоит 71 пассажир. У каждого из пассажиров есть билетик с номером места, которое ему необходимо занять при посадке в автобус. Для простоты пусть номер пассажира в очереди равен номеру его места в автобусе (1-ый чел должен занять место №1, 2-ой - №2, ... 71-ый - место №71 ). Однако первый стоящий в очереди пассажир - чувак, и при посадке в автобус он плюхается в кресло, которое ему понравилось больше всего (случайным образом от 1 до 71). Какова вероятность того, что последний (71-ый) пассажир займет свое (71-ое) место?
UPDATED: Упустил предложение, что каждый последующий пассажир, после первого, садится на свое место, если оно не занято, в противном случае ему достается случайное место из свободных.

100 лампочек.
На длинном щитке сигнализации в ряд вкручены 100 изначально выключенных лампочек. Охранник делает 100 обходов мимо этого щитка каждый раз в одном и том же направлении. В процессе каждого обхода охранник переключает (включает, если лампочка выключена; и выключает, если включена) определенные лампочки. При первом обходе переключаются все лампочки, при втором - каждая вторая (2, 4, 6, 8 ... 98, 100), при третьем - каждая третья (3, 6, 9 ... 96, 99) и т.д. Какие лампочки будут включены после того, как охранник завершит все обходы?

Краско.
Есть две бочки с одинаковым объемом краски в каждой из них. В первой находится синяя краска, во второй - красная. Из первой бочки во вторую перелили какое-то количество синей краски, перемешали ее с красной, а за тем это же количество полученной смеси перелили обратно в первую бочку. Чего оказалось больше: в первой бочке красной краски или во второй бочке синей?

Четыре беглеца.
Под покровом ночи 4 беглеца, спасаясь от погони, оказались на краю пропасти. Для окончательного спасения им осталось по натянутому веревочному мостику перебраться на противоположный край пропасти. Для этого у них есть всего 17 минут и один фонарик, который обязательно нужно иметь при себе при переходе по мостику, чтобы не оступиться и не упасть. Первый беглец может перебраться по мостику на противоположный край за 1 минуту, 2-ой - за 2 мин, 3-ий за 5, 4-ый - за 10. Одновременно мостик может выдержать не более двух беглецов. При этом если по мостику начнут перебираться два человека, они смогут двигаться лишь со скоростью самого медленного из них двоих. Как бедолагам уложиться в 17 минут?

Зеркало.
Почему у отражения в зеркале меняется местами только левая и правая сторона, а верх и низ остаются на своих местах?

Написать программулину.
Есть массив из n различных элементов. Необходимо вывести все перестановки этих элементов. Допускается использование не более одного вложенного цикла.
Например, n = 3. Соответственно, массив может иметь вид [a, b, c]. Необходимо вывести следующие варианты:

[a, b, c]
[a, c, b]
[b, a, c]
[b, c, a]
[c, a, b]
[c, b, a]

ПС: вложенный цикл - цикл, выполняющийся внутри другого цикла.

Предложенные задачки предлагают решить в течение полутора часов...
Я вот только на написание программки потратил почти полдня