Задачка с международного математического конкурса этого года - Этюды для программистов

Здравствуйте, Pushkin, Вы писали:

P>
P>

P>3   5   17   257   32769
P>- * - * -- * --- * -----... = ?
P>2   4   16   256   32768 
P>

Теперь с пятым членом проблемы? Ну да ладно.

Рассмотрим до 2^(2^N).

               i=N                i=N                          i=N
Числитель: Nom= П (2^(2^i)+1) = 3* П (2^(2^i)+1) = (2^(2^1)-1)* П (2^(2^i)+1) =
               i=0                i=1                          i=1

                          i=N                          i=N
= (2^(2^1)-1)*(2^(2^1)+1)* П (2^(2^i)+1) = (2^(2^2)-1)* П (2^(2^i)+1) = .....
                          i=2                          i=2

.... = (2^(2^N)-1)*(2^(2^N)+1) = 2^(2^(N+1))-1

                   i=N             i=N                         1
Знаменатель: Denom= П 2^(2^i) = 2^( E  2^i) = 2^(2^(N+1)-1) = --- * 2^(2^(N+1))
                   i=0             i=0                         2

 Nom         2^(2^(N+1))-1
----- = 2* ----------------- --> 2 при N --> +1/0.
Denom         2^(2^(N+1))

Здравствуйте, RS, Вы писали:

RS>Здравствуйте, Pushkin, Вы писали:

P>>
P>>

P>>3   5   17   257   32769
P>>- * - * -- * --- * -----... = ?
P>>2   4   16   256   32768 
P>>

RS>Теперь с пятым членом проблемы? Ну да ладно.

Блин,

с утра башка трещит чегой-то

Решение хорошее.

Оно только на первый взгляд пугает

Вот ещё одно.

(1-q)*(1-q^2)*(1-q^4)*(1-q^8)*(1-q^16)*...

Если "раскрыть" скобки, то будет сумма разных степеней q.
Причём видно, что каждая степень войдёт ровно 1 раз
(т.к. любое число единственным образом набирается степенями двойки).

Поэтому это просто сумма геометрической прогрессии равная 1/(1-q)

Здравствуйте, Andy77, Вы писали:

A>

A>                                         k
A>Очевидно, что для любого интервала [0 .. E 9^i] эта разность будет равна нулю.
A>                                        i=1
A>

A>P.S. "E" — это сигма

A>P.P.S. Интересно, неужели от участников требовалось только показать, что каждому числу, записанному разными цифрами в порядке возрастания, можно поставить в соответствие число, записанное этими же цифрами в порядке убывания, и наоборот?

PPS хорош

А в самом решении зачем ты этого крокодила написал?

Речь же идёт о количестве ВСЕХ чисел, записанных РАЗНЫМИ цифрами.
Эти числа, очевидно, не длиннее 10 позиций.

Вот только 0 в начале числа не может стоять.
И в этом твоя роковая ошибка

Надо таким образом найти количество чисел, в которых последняя цифра 0, а остальные стоят по убыванию. Или иными словами, количество чисел, в которых используется 9 цифр и все по убыванию.

Любая из 9 цифр может либо участвовать, либо не участвовать в этом безобразии (а уж место ей найдётся). Поэтому правильный ответ имхо 2^9=512

Найти разность между количеством всех чисел, записанный разными цифрами в порядке убывания (например 9421) и количеством всех чисел, записанных разными цифрами в порядке возрастания (например 358).

Задача для 10-11 классов. Оценивалась в 5 баллов

PS В реальной жизни, участники конкурса доступ к компам не имели

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Alik, Вы писали:

A>>Найти разность между количеством всех чисел, записанный разными цифрами в порядке убывания (например 9421) и количеством всех чисел, записанных разными цифрами в порядке возрастания (например 358).

P>А что, если разрешить ещё и десятичную точку?

А если разрешить точку, то похоже как раз 0 и будет. Потому что каждое число, заканчивающееся на "0", уравновесится числом, начинающимся с "0."

                                         k
Очевидно, что для любого интервала [0 .. E 9^i] эта разность будет равна нулю.
                                        i=1

P.S. "E" — это сигма

P.P.S. Интересно, неужели от участников требовалось только показать, что каждому числу, записанному разными цифрами в порядке возрастания, можно поставить в соответствие число, записанное этими же цифрами в порядке убывания, и наоборот?
P.P.P.S. Давайте тогда уж поинтереснее решать — брать числа можно только в промежутке [0..N], соответственно результат должен быть в виде f(N) = ... и формулу записать не более чем 30 символами

Здравствуйте, Alik, Вы писали:

A>Здравствуйте, Pushkin, Вы писали:

P>>Здравствуйте, Alik, Вы писали:

A>>>sqrt(1+2000*sqrt(1+2001*sqrt(1+2002*sqrt(1+2003*2005))))

P>>2001

A>На калькуляторе посчитал?

Вряд ли. Число 2001 занесено в Международный Каталог Замечательных Чисел.

Например, число 2732 из того же каталога, тоже обладает подобным свойством:

sqrt(1+2731*sqrt(1+2732*sqrt(1+2733*sqrt(1+2734*2736)))) = 2732

А Pushkin наверняка это знал, но молчал. А мы его раскусили.

Евгений

А вот такую задачку?

Пусть даны натуральные A>B>1 такие, что A, B, A-B, A+B все простые. Определить, будет ли
A+B+(A-B)+(A+B)

1. простым
2. четным
3. кратным 3
4. кратным 5
5. кратным 7

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Pushkin, Вы писали:

P>>Поэтому правильный ответ имхо 2^9=512

P>Чёрт, и я похоже соврал.

511
P>Надо ещё 1 отнять — хоть одна цифра перед последним нулём должна быть.

Ага, это ты сказал, сколько чисел "по убыванию". По возрастанию будет 512. А разница равна 1.

Здравствуйте, ILS, Вы писали:

ILS>Ага, это ты сказал, сколько чисел "по убыванию". По возрастанию будет 512. А разница равна 1.

Ошибаешься.
Я посчитал количество чисел "по убыванию", оканчивающихся на 0.
Соответствий всем этим числам в мире "по возрастанию" нет.
Поэтому ответ на исходный вопрос 511.

Здравствуйте, ILS, Вы писали:

ILS>Здравствуйте, Pushkin, Вы писали:

P>>Здравствуйте, Pushkin, Вы писали:

P>>>Поэтому правильный ответ имхо 2^9=512

P>>Чёрт, и я похоже соврал.

511
P>>Надо ещё 1 отнять — хоть одна цифра перед последним нулём должна быть.

ILS>Ага, это ты сказал, сколько чисел "по убыванию". По возрастанию будет 512. А разница равна 1.
У-у-пс. Облажался. Для чисел "по-возрастанию" нуль впереди стоять не может => их число 2^9 = 512. Для чисел "по-убыванию" нуль в конце стоять может => их число 2^10 = 1024. А разница = 512. Ммм. Да, так.

Здравствуйте, ILS, Вы писали:

ILS>У-у-пс. Облажался. Для чисел "по-возрастанию" нуль впереди стоять не может => их число 2^9 = 512. Для чисел "по-убыванию" нуль в конце стоять может => их число 2^10 = 1024. А разница = 512. Ммм. Да, так.

В обоих случаях ты включил в подсчёт довольно странное число без единой цифры. Но это бог с ним — сократилось. А вот "убывающее число" 0 — это явно лишняя единичка в твоём ответе.

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, ILS, Вы писали:

ILS>>У-у-пс. Облажался. Для чисел "по-возрастанию" нуль впереди стоять не может => их число 2^9 = 512. Для чисел "по-убыванию" нуль в конце стоять может => их число 2^10 = 1024. А разница = 512. Ммм. Да, так.

P>В обоих случаях ты включил в подсчёт довольно странное число без единой цифры. Но это бог с ним — сократилось. А вот "убывающее число" 0 — это явно лишняя единичка в твоём ответе.

Признаю свою ошибку. Лежачего не бьют.

Здравствуйте, Alik, Вы писали:

A>Найти разность между количеством всех чисел, записанный разными цифрами в порядке убывания (например 9421) и количеством всех чисел, записанных разными цифрами в порядке возрастания (например 358).

По заведённой традиции, на основании этой задачки, можно предложить редуцированные варианты:

1) Найти разность между количеством всех чисел, записанный разными цифрами в порядке убывания (например 9421) и количеством всех чисел, записанных разными цифрами.

1) Найти разность между количеством всех чисел, записанный разными цифрами в порядке убывания (например 9421) и количеством всех чисел.

3) Найти разность между количеством всех чисел, записанный разными цифрами и количеством всех чисел.

4) Найти сумму разностей между всеми числами.

Евгений

Здравствуйте, mrhru, Вы писали:

M>4) Найти сумму разностей между всеми числами.
M>

Забавно, что про разность сумм даже спросить нельзя

Не упел прийти на работу, а тут уже обсудили задачу со всех сторон

Мне остается только подтвердить (если кто-то в этом нуждается), что 511 — это правильный ответ

Если кому интересно, могу привести варианты неправильных ответов (имеется в виду наиболее популярных)

По убыванию популярности: 512, 513, 1024

Здравствуйте, mrhru, Вы писали:

M>По заведённой традиции, на основании этой задачки, можно предложить редуцированные варианты:

M>1) Найти разность между количеством всех чисел, записанный разными цифрами в порядке убывания (например 9421) и количеством всех чисел, записанных разными цифрами.

M>2) Найти разность между количеством всех чисел, записанный разными цифрами в порядке убывания (например 9421) и количеством всех чисел.

Ну, первые две задачи решаются простыми арифметическими действиями (с учетом уже решенной)

M>3) Найти разность между количеством всех чисел, записанный разными цифрами и количеством всех чисел.

Это типа минус бесконечность?

M>4) Найти сумму разностей между всеми числами.

Лучше так: для любых m и n из натурального ряда найти сумму всех (m-n)

Кстати, если хочется вспомнть арифметику, то вот задачка: чему равно
sqrt(1+2000*sqrt(1+2001*sqrt(1+2002*sqrt(1+2003*2005))))

Здравствуйте, Alik, Вы писали:

A>sqrt(1+2000*sqrt(1+2001*sqrt(1+2002*sqrt(1+2003*2005))))

2001

Здравствуйте, Alik, Вы писали:

P>>А что, если разрешить ещё и десятичную точку?

A>А если разрешить точку, то похоже как раз 0 и будет. Потому что каждое число, заканчивающееся на "0", уравновесится числом, начинающимся с "0."

Да, мне тоже так кажется

Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, Alik, Вы писали:

A>>sqrt(1+2000*sqrt(1+2001*sqrt(1+2002*sqrt(1+2003*2005))))

P>2001

На калькуляторе посчитал?

Здравствуйте, Alik, Вы писали:

A>>>sqrt(1+2000*sqrt(1+2001*sqrt(1+2002*sqrt(1+2003*2005))))

P>>2001

A>На калькуляторе посчитал?

Ну, кстати, вместо последнего 2005 можно поставить многоточие, устремив количество арифметических действий к бесконечности. В этом случае калькулятор не поможет, а ответ все равно будет 2001 (мне так кажется).

Здравствуйте, mrhru, Вы писали:

M>Вряд ли. Число 2001 занесено в Международный Каталог Замечательных Чисел.
M>Например, число 2732 из того же каталога, тоже обладает подобным свойством:
M>sqrt(1+2731*sqrt(1+2732*sqrt(1+2733*sqrt(1+2734*2736)))) = 2732
M>А Pushkin наверняка это знал, но молчал. А мы его раскусили.

Здравствуйте, RS, Вы писали:

A>>>>sqrt(1+2000*sqrt(1+2001*sqrt(1+2002*sqrt(1+2003*2005))))
RS>Ну, кстати, вместо последнего 2005 можно поставить многоточие, устремив количество арифметических действий к бесконечности. В этом случае калькулятор не поможет, а ответ все равно будет 2001 (мне так кажется).

По сложным ассоциациям

вспомнил это.

3   5   9   17
- * - * - * -- * ... = ?
2   4   8   16

Здравствуйте, Pushkin, Вы писали:

P>По сложным ассоциациям

вспомнил это.

P>

P>3   5   9   17
P>- * - * - * -- * ... = ?
P>2   4   8   16
P>

2,38423102903137

Евгений

Здравствуйте, Alik, Вы писали:

A>А вот такую задачку?

A>Пусть даны натуральные A>B>1 такие, что A, B, A-B, A+B все простые. Определить, будет ли
A>A+B+(A-B)+(A+B)

B=2, поэтому

простым

четным

кратным 3

кратным 5

кратным 7

Здравствуйте, mrhru, Вы писали:

P>>

P>>3   5   9   17
P>>- * - * - * -- * ... = ?
P>>2   4   8   16
P>>

M>2,38423102903137
M>

Блин, прошу пардону, третий член там лишний.
Эту я сам не знаю, как решать

Имелось в виду, что знаменатель растёт как 2^(2^n)
Т.е. каждый следующий знаменатель — квадрат предыдущего.

3   5   17   257   32769
- * - * -- * --- * -----... = ?
2   4   16   256   32768

А так как калькуляторы у вас, мерзавцев, у всех есть,

то задача просто объяснить, почему это всё равно двойке.

Здравствуйте, Pushkin, Вы писали:

P>Вот ещё одно.

P>(1-q)*(1-q^2)*(1-q^4)*(1-q^8)*(1-q^16)*...

P>Если "раскрыть" скобки, то будет сумма разных степеней q.
P>Причём видно, что каждая степень войдёт ровно 1 раз
P>(т.к. любое число единственным образом набирается степенями двойки).

P>Поэтому это просто сумма геометрической прогрессии равная 1/(1-q)

Молодец.

Решение еще проще, чем мое, я че-то не допер до прогрессий.

Здравствуйте, Alik, Вы писали:

A>А вот такую задачку?

A>Пусть даны натуральные A>B>1 такие, что A, B, A-B, A+B все простые.

A и B -- простые, следовательно, нечетные. А сумма и разность нечетных чисел -- число четное. Значит A+B и A-B простыми быть не могут.

--
Дмитрий

Здравствуйте, Дмитро, Вы писали:

A>>Пусть даны натуральные A>B>1 такие, что A, B, A-B, A+B все простые.

Д>A и B -- простые, следовательно, нечетные. А сумма и разность нечетных чисел -- число четное. Значит A+B и A-B простыми быть не могут.

Как ответил Pushkin, 2 — единственное простое и чётное. Поэтому, на часть вопросов можно ответить.

Я на этом тоже попался.

Евгений

От:	Pushkin	www.linkbit.com
Дата:	27.03.03 06:31
Оценка:	39 (3)

От:	RS	ICQ: 148844272
Дата:	27.03.03 12:54
Оценка:	26 (2)

От:	Pushkin	www.linkbit.com
Дата:	27.03.03 13:09
Оценка:	26 (2)

От:	Pushkin	www.linkbit.com
Дата:	27.03.03 06:27
Оценка:	12 (1)

	От:	Alik
	Дата:	26.03.03 20:30
	Оценка:	11 (1)

	От:	Дмитро
	Дата:	29.03.03 08:07
	Оценка:

	От:	mrhru
	Дата:	29.03.03 08:16
	Оценка: