Пятница. Большая пачка сложных задачек...

← →
MBo © (2004-07-23 09:59) [0]

1. 100 человек стоят у трапа самолета, у всех есть билеты, в самолете как раз
100 мест. Вдруг с места срывается сумашедшая старуха и занимает первое попавшееся
место. Дальше все идут по-очереди. Так как они нормальные люди, каждый сначала
пытается занять сво± место по билету. Ну а если оно занято, то какое попало.
Какова вероятность того, что последний пассажир сядет на свое место?

2. - Я слышу, что в саду играют дети, - сказал Иванов. - Неужели все они ваши?
- Боже упаси, конечно, нет, - воскликнул профессор Интегралов, известный специалист по теории чисел. - Там, кроме моих детей, играют еще дети троих соседей, но наша семья самая большая.
У Лавочкиных детей меньше, чем у меня, а у Скамейкиных - еще меньше, а меньше всего детей у Табуреткиных.
- А сколько всего детей? - спросил Иванов.
- На этот вопрос я так отвечу, - сказал Интегралов. - Детей меньше восемнадцати, а если перемножить между собой число детей в семьях, то получится номер моего дома, который вы видели, когда пришли.
Иванов достал из кармана блокнот и карандаш и принялся за вычисления. Через некоторое время он поднял голову и сказал:
- Нужна еще какая-то информация. У Табуреткиных больше одного ребенка?
Как только Интегралов ответил, Иванов сразу нашел решение и правильно назвал число детей в каждой семье.

Иванов получил подсказку, после которой задача стала легкой.
Но оказывается, что число детей в каждой семье можно определить и без этой дополнительной информации, что дал профессор Интегралов (сообщив о том, сколько детей у Табуреткиных - один или больше).
Как это сделать, опираясь на рассуждения Иванова?

3. Можно ли на обыкновенной бумаге в клетку нарисовать выпуклый пятиугольник так, чтобы все его вершины были в узлах, и больше ни одного узла ему не принадлежало?

4. В памяти суперкомпьютера находится заполненная некоторым образом матрица А[M,N] (M и N очень большие числа). Каждая клетка матрицы может иметь значение 0 или 1.
Необходимо придумать алгоритм для преобразования матрицы следующим образом:
- Элемент в новой матрице A[i,j]=1, если в изначальной матрице в сторке i есть хоть один элемент =1 И в столбце j есть хоть один элемент =1.
- Иначе элемент в новой матрице A[i,j]=0.
Ограничение: в памяти нет места для временного размещения еще одной такой матрицы, так как первая занимает 90% всей памяти компьютера.

5. Ниже приведён список из 10 утверждений,
позволяющий однозначно определить натуральное число N.
К сожалению, некоторые из этих утверждений неверны
Но зато все остальные верны

1. По крайней мере одно из двух последних утверждений в списке верно.
2. Это или первое верное или первое неверное утверждение в списке.
3. В списке есть 3 последовательных неверных утверждения.
4. Разность между номерами последнего и первого верных утверждений есть делитель N.
5. N равно сумме номеров всех верных утверждений.
6. Это не есть последнее_верное_утверждение.
7. Номера всех верных утверждений есть делители N.
8. N% всех утверждений верны.
9. Число делителей N, отличных от 1 и N, больше суммы номеров верных утверждений.
10.В списке нет 3-х последовательных верных утверждений.

6. Едем в автобусе, окна замёрзшие. Как подручными средствами (ничего необычного, только,
скажем, пластмассовая линейка) более-менее точно измерить толщину льда на стекле?

7. Что больше |Sin(2001^2002)| или 0.5?

8. Все знают классическую задачу о бассейне - в трубу А втекает, из трубы Б вытекает.

Теперь давайте перейдем к практике. Известно, что скорость вытекания подчиняется закону Бернулли v~sqrt(плотность*g*h).

Ну а теперь сама задача.
Вы на даче расположили переносной (надувной) бассейн. Входное и выходное отверстия на уровне земли.
Бассейн заполняется с постоянной скоростью за время t1. Время слива самотеком t2. Определить время заполнения при незакрытом сливном отверстии. Считать, что бассейн имеет постоянную по высоте площадь сечения.

9. Задача Архимеда: Два цилиндра диаметром 1 пересекаются крестом под прямым углом. Каков объём общей части?

← →
MBo © (2004-07-23 10:00) [1]

10. Животный ряд:
Собака - 3
Корова - 2
Кошка - 3
Петух - 8
Ворона - ?

11. 1) Укажите 1000 идущих подряд натуральных чисел, ни одно из которых не является простым.
2) То же самое, но с дополнительным требованием, чтобы числа непосредственно слева и справа от этого интервала были простыми.

12. Один ёжик (ежиха) бежит с постоянной скоростью по прямой. Когда расстояние до нее становится минимальным, в погоню за ней устремляется ёжик, который бежит с той же скоростью и все время держит курс на неё.
Во сколько раз он сможет сократить расстояние до неё?

13. Трактор тянет за собой бревно (вдоль).
Я хочу его измерить шагами.
Шёл за трактором - насчитал 6 шагов.
В противоположную сторону - 2 шага.
Сколько на самом деле шагов в бревне?

PS
Легко написать систему с суммой и разностью скоростей.
Фишка в том, чтобы найти простое, устное решение.

14. Мои акции 100 дней росли на 1% ежедневно.
А потом стал падать тоже на 1% ежедневно.
Через сколько дней падения я вернусь (почти точно) на прежний уровень?

Токо умоляю, не запускайте калькулятор!
Лучше воспользуйтесь тем, что скорость мала.

15. Белоснежка наливает гномам молока - всем по-разному. После этого происходит следующая забавная процедура: старший гном делит всё своё молоко поровну между 6 другими братьями, потом следующий гном делит всё своё молоко (включая долитое) между 6 другими братьями (включая старшего), и так далее все гномы. После этого у каждого оказывается ровно столько молока, сколько было вначале. По сколько (граммов) разлила Белоснежка каждому?

16. Ваш друг загадал полином с целыми неотрицательными коэффициентами и готов сообщить вам
значения этого полинома сначала в одной, а потом в другой из выбранных вами целочисленных
точек ( вторую из точек можно выбрать после того, как друг выдаст значение полинома в первой точке).
Сможете ли вы отгадать загаданный полином?

17. Иван Царевич шел за украденной Кощеем Василисой Прекрасной и наткнулся на избушку Бабы Яги. Баба Яга его накормила, а потом и говорит:
- Не то нынче время пошло. Кощей уж больно хитер стал. Теперь он усложнил охрану своей иголки жизни. Теперь на высоком дубу на цепях в сундуке, где раньше сидел только один заяц, сегодня сидят целых три – черный, белый и серый. И в каждом зайце по утке (серая шейка, ощипанная утка и утка хромоножка), а в каждой утке по яйцу (обычное яйцо, тухлое яйцо и крашеное яйцо), а в каждом яйце по иголке (обычная иголка, цыганская иголка и кощеева игла). И в каждом своя игла, яйцо и утка сидит. И только одна игла настоящая (кощеева) и несет смерть ему. И беда то в том, что если схватить одного зайца, открыв сундук, то два других убегут. Поэтому надо точно знать какого зайца хватать, в котором та самая утка, в которой то самое яйцо, в котором та самая игла. А известно очень мало:
- Настоящей иголки кощея нет в утке хромоножке и нет в обычном яйце.
- Крашеного яйца нет в утке серой шейке.
- Тухлое яйцо находится в черном зайце.
- Цыганская игла в тухлом яйце.
- А в белом зайце сидит либо утка серая шейка, либо утка хромоножка.

Иван царевич был не дурак и сказал, что завтра по утру без труда схватит нужного зайца.

В каком зайце сидит какая утка, в которой какое яйцо, где лежит кощеева игла? И как Иван Царевич это определил?

18. Какова вероятность, что два наугад выбранных натуральных числа будут взаимно простыми, т.е. без общих делителей?

← →
MBo © (2004-07-23 10:16) [2]

Пардон, забыл указать, что в задаче
>7. Что больше |Sin(2001^2002)| или 0.5?
аргумент в ГРАДУСАХ

← →
Sandman25 © (2004-07-23 10:18) [3]

4. Объявляем вектора B[M] и С[N]. Они занимают меньше 10%, если M,N > 9.
Записываем в B[I] 1, если в I-той строке есть 1.
Записываем в C[J] 1, если в J-том столбце есть 1.
Пробегаемся по A: A[I, J] = B[I] and C[J]

← →
Alx2 © (2004-07-23 10:23) [4]

7. sin больше :)))

← →
MBo © (2004-07-23 10:25) [5]

>Sandman25 © (23.07.04 10:18) [3]
ЗдОрово!
Задача, говорят, с интервью Microsoft.

← →
Sandman25 © (2004-07-23 10:25) [6]

7. Получается примерно sin (10г), то есть sin меньше.

← →
MBo © (2004-07-23 10:27) [7]

>sin (10г),
где-то ты ошибся

← →
Sandman25 © (2004-07-23 10:28) [8]

[5] MBo © (23.07.04 10:25)

:)
Сначала пытался найти решение без использования массивов, только со скалярами. ИМХО это невозможно, если в массивы нельзя записывать ничего, кроме 0 и 1.

← →
jack128 © (2004-07-23 10:37) [9]

1) Если не особо заморачиваться, то 99%

← →
Думкин © (2004-07-23 10:39) [10]

> [9] jack128 © (23.07.04 10:37)

1/2

← →
jack128 © (2004-07-23 10:41) [11]

> 9] jack128 © (23.07.04 10:37)
да, ступил..

← →
Sandman25 © (2004-07-23 10:46) [12]

7. 2001^2002=(N+X)*180, N целое, 0<=X<1
2002lg2001=lg180+lg(N+X)
lg(N+X)=6606,8413989445919237284910658068
lg(K+X)=0,8413989445919237284910658068
K+X=6,9406308230315654834043075240474
X=0,9406308230315654834043075240474

|sin(2001^2002)|=|sin(0,9406308230315654834043075240474*180)|=0,18543426182122394696410154707374 < 0.5

← →
Sandman25 © (2004-07-23 10:50) [13]

[12] Sandman25 © (23.07.04 10:46)

Опять ступил :(

← →
MBo © (2004-07-23 10:54) [14]

>Sandman25 © (23.07.04 10:28) [8]
>Сначала пытался найти решение без использования массивов, только со скалярами.

Видел псевдокод без использования доп. массивов, но еще не разбирался. Ближе к вечеру посмотрю.

← →
Sandman25 © (2004-07-23 11:08) [15]

10. Ворона - 5?

← →
MBo © (2004-07-23 11:11) [16]

>10. Ворона - 5?
нет

← →
mrcat © (2004-07-23 11:15) [17]

10. 14 ?

← →
MBo © (2004-07-23 11:18) [18]

>10. 14 ?
Нет

← →
mrcat © (2004-07-23 11:24) [19]

10. 14 ?
5 + 8 = 13 :)

← →
Sandman25 © (2004-07-23 11:29) [20]

16. Задача непонятна. Друг сообщил еще и степень полинома? Иначе найдем линейную функцию :)

← →
Fishka (2004-07-23 11:36) [21]

10. 13

← →
DimKa © (2004-07-23 11:56) [22]

2. А номер дома не указан?

← →
MBo © (2004-07-23 12:04) [23]

>5 + 8 = 13 :)
Нет.
Задачу часто легко решают дети, в отличие от взрослых.

>Sandman25 © (23.07.04 11:29) [20]
>16. Задача непонятна. Друг сообщил еще и степень полинома? Иначе найдем линейную функцию :)

Нет, степень полинома неизвестна.

>DimKa © (23.07.04 11:56) [22]
>2. А номер дома не указан?
Не указан, но нам известно, что Иванов его знает.

← →
Думкин © (2004-07-23 12:06) [24]

10. 3

← →
DimKa © (2004-07-23 12:11) [25]

14. 99 дней

← →
Sandman25 © (2004-07-23 12:25) [26]

16.
F(X)=a1*X^^n+a2*X^^(n-1)...+a(n-1)

Пусть я скажу точку 1, мне скажут Y1=a1+a2+...+a(n-1).
Потом я скажу точку 2, мне скажут Y2.
Тогда степень полинома <= [log2(Y2-Y1)].
Имеем Y2=F(X2)=2^^n*a1+2^^(n-1)*a2+..+a(n-1).
Y2-Y1=a1(2^^(n-1))+a2(2^^(n-2))...
Остается перевести число Y2-Y1 в двоичную систему и решить систему уравнений.
Например, если Y1=5, Y2=15, то
N <= 3
10=8+2

a1+a2+a3=5
4a1+2a2+a3=15

Вычитаем уравнения
3a1+a2=10
a1=3
a2=1
F(X)=3x^^2+x+1

← →
Sandman25 © (2004-07-23 12:28) [27]

"Остается перевести число Y2-Y1 в двоичную систему"
и
"10=8+2" в решении не принимают участия, ошибся

← →
Думкин © (2004-07-23 12:33) [28]

> [26] Sandman25 © (23.07.04 12:25)
> 16.
> F(X)=a1*X^^n+a2*X^^(n-1)...+a(n-1)

у = 10*x-5
y(1) = 5
y(2) = 15

[28] Думкин © (23.07.04 12:33)

Понятно. Такое ощущение, что X должны быть простыми и как можно больше :)
Например, X1=103. получаем Y=120022. Тогда X2=101^^3

5. 420. Многовато что-то, но вроде подходит.

15. последнему гному вообще не налилили?
Если это так, то я на првильном пути, если нет, ну ее задачу эту )

>DimKa © (23.07.04 12:58) [31]
Правильным путем идете, товарищ! ;)

>Agent13 © (23.07.04 12:54) [30]
5. 420. Многовато что-то, но вроде подходит.

Верно!

>Sandman25 © (23.07.04 12:25) [26]
Кое-что верно (сначала P(1) спрашиваем), и ключевая идея близко

16. Да ключевая фраза - неотрицательные. Поэтому мой пример отпадает.
P(1) - оценка, потом любое простоте болше ответа - и далее ясно.

MBo © (23.07.04 10:54) [14]
можно без массивов сделать создать теже массивы что и у Sandman25
но записать их в верхнюю строку матрицы и левый столбец
по ним заполнить "внутреннюю матрицу"
но при записи строк будет перекрытие элемента (1, 1)
надо это учесть сохранив нужные(ое) значения(ие) при "конечном" заполнении левого столбца и верхней строки

"но при записи строк будет перекрытие элемента (1, 1)"-->
но при записи верхней строки и левого столбца будет перекрытие элемента (1, 1)

11. А такое вообще возможно?

Думкин, MBo

Растолкуйте, пожалуйста, принцип отображения в 10 задаче...

Пятница. Большая пачка сложных задачек... Найти похожие ветки