Сколько вариантов чисел?

← →
@!!ex © (2009-07-22 15:20) [0]

18 значное число.
Каждая цифра используеться минимум один раз.

← →
Anatoly Podgoretsky © (2009-07-22 15:30) [1]

> @!!ex (22.07.2009 15:20:00) [0]

2^18

← →
Anatoly Podgoretsky © (2009-07-22 15:30) [2]

> @!!ex (22.07.2009 15:20:00) [0]

10^18

← →
TIF © (2009-07-22 15:34) [3]

999 999 998 765 432 110 < x < 1 000 000 000 000 000 000
Что-то я уже сам сомневаюсь, но вроде ответ лежит где-то там )

> 10^18

См.
> Каждая цифра используеться минимум один раз.

← →
БарЛог © (2009-07-22 15:34) [4]

Смотря какая СС

← →
TIF © (2009-07-22 15:37) [5]

> используеться

Уууу, жаль что тема про математику, а не русский язык :)

← →
Anatoly Podgoretsky © (2009-07-22 15:39) [6]

> TIF (22.07.2009 15:34:03) [3]

Будет, будет, более того каждая цифра будет использована одинаковое количество раз.

← →
Bless © (2009-07-22 15:41) [7]

10! * 10^7 * 9

я так думаю :)

← →
TIF © (2009-07-22 15:47) [8]

> Будет, будет, более того каждая цифра будет использована
> одинаковое количество раз.

%-\
Не понял юмора.

По сабжу - я понял, что нужно найти количество всех чисел наподобие этого:
1234567890
Каждая цифра задействована 1 раз. Можно и несколько раз задействовать:
12345567890
и так далее... И это никак не будет равно 10^8, ибо 10^18 - это же все числа от 0 до 10^18 подряд, включая те, которые этому условию не удовлетворяют?!

> Bless © (22.07.09 15:41) [7]
> 10! * 10^7 * 9я так думаю :)

326 592 000 000 000
Уже похоже на истину

← →
Ega23 © (2009-07-22 15:48) [9]

Это не простая комбинаторика.

000 000 000 123 456 789 = 123 456 789

← →
Bless © (2009-07-22 15:57) [10]

т.е. 326 592 000 000 000

Раз уж мое число вступает в противоречие с приведенными выше и ниже вариантами, то мотивирую.

Рассмотрим 10-значные числа, в котором использована каждая из десяти цифр минимум по одному разу. Поскольку оно 10-значное, то каждая цифра использована строго ПО ОДНОМУ РАЗУ. Таких чисел будет 10!

А сколько будет 11-значных чисел, удовлетворяющих условию "каждая цифра минимум одинадцать раз"? Это легко. Берем каждое из наших 10-значных чисел и дописываем слева 1. Потом эти же 10! чисел и дописываем слева 2 и т.д. проделываем то же самое со всеми оставшимися цифрами. Т.е. количестко 11-значных чисел будет равно 10 *(количество 10-значных) = 10*10!.
Аналогично, 12-значных будет 10 * (количество 11-значных) = 10*10*10! = 10^2 * 10!

и т.д.

17-значных будет 10^7*10!
А 18-значных = 9 * 10^7*10!
Почему 9? Потому что 0, дописанный слева не считается, т.к. он не меняет число.

← →
Bless © (2009-07-22 15:58) [11]

исправление
"каждая цифра минимум одинадцать раз"
читать как
"каждая цифра минимум один раз"

← →
Anatoly Podgoretsky © (2009-07-22 16:30) [12]

> TIF (22.07.2009 15:47:08) [8]

Такого условия не было, что бы обязательно все 10 цифр в каждом числе, требование одно задействовать каждую цифру минимум один раз. Таких комбинаций 10^18 или 2^64

← →
tesseract © (2009-07-22 16:33) [13]

> Таких комбинаций 10^18

меньше должно быть - необходимо вычесть варианты где не все 10 цифр используется. Например все варианты без ноля выпадают.

← →
Дуб © (2009-07-22 16:44) [14]

Пока лидирует ответ №156: Многа!

← →
@!!ex © (2009-07-22 16:50) [15]

> [12] Anatoly Podgoretsky © (22.07.09 16:30)

Имелось ввиду как раз, чтобы обязательно все 10 цифр в каждом числе. Прошу прощения, что не точно написал.

← →
Anatoly Podgoretsky © (2009-07-22 16:54) [16]

> tesseract (22.07.2009 16:33:13) [13]

Это почему же выпадают, не надо выпадать, используй все 18 цифр, не стоит путать цифры с числом.

← →
Anatoly Podgoretsky © (2009-07-22 16:54) [17]

> @!!ex (22.07.2009 16:50:15) [15]

Ну так у тебя есть такая болезнь, а нам гадать :-)

← →
@!!ex © (2009-07-22 17:05) [18]

> [17] Anatoly Podgoretsky © (22.07.09 16:54)

Ну блин. Я вроде по русски пишу.
Есть 18 значное число, каждая цифра используеться минимум один раз. Сколько вариантов чисел?
Как еще то можно понять? :))

← →
tesseract © (2009-07-22 17:06) [19]

> не стоит путать цифры с числом.

Точно.

0...9 - цифры.
10 - число из двух цифр.

← →
SP (2009-07-22 18:27) [20]

> 0...9 - цифры.

Ну 0..9 - может быть и числом из одной цифры
Смотря в каком контексте это подразумевается...

Цифры - это сами символы для записи чисел.
А числа - это уже количественная характеристика чего-нить.

← →
Дуб © (2009-07-22 18:44) [21]

> это уже количественная характеристика чего-нить

Особенно комплексные.

← →
Sha © (2009-07-22 20:45) [22]

> @!!ex © (22.07.09 15:20)
Это число - 000000000123456789 - 18-ти значное?

← →
SP (2009-07-22 21:08) [23]

> Это число - 000000000123456789 - 18-ти значное?

хз. не думаю... Но возможно у аффтара своя классификация.

← →
palva © (2009-07-22 21:20) [24]

> Это число - 000000000123456789 - 18-ти значное?

Если это число считать 18-значным, тогда смысл значности числа пропадает. Так же точно его можно считать 17-значным. Так что, скорее всего, первая цифра числа всегда должна быть ненулевая, либо, как вариант, это число из одной цифры 0

← →
Anatoly Podgoretsky © (2009-07-22 21:25) [25]

> Это число - 000000000123456789 - 18-ти значное?

Если смотреть с фиксированым числом знаков, то конечно, наглядно видно в машинном представление. А вот о чем говорит автор мы узнаем через 30 постов или позже. Но я могу сделать упор и вопроса автора

> 18 значное число.

И ничего не говорится о значащих и не значищих цифрах, только жесткий императив, что число имеет всегда 18 цифр, любых цифр.
000 000 000 000 000 000 - 999 999 999 999 999 999
и также что каждая цифра должна быть использована не менее одного раза, правда, что за цифры также осталось за кадром, может это 60-ричная или какая то другая системы. Мы все почему то посчитали, что это десятичная система.

Короче или трепаться или в корзину.

← →
Sha © (2009-07-22 21:26) [26]

> SP (22.07.09 21:08) [23]
От этого решение зависит. А оба случая рассматривать - писать долго.

> palva © (22.07.09 21:20) [24]
> Если это число считать 18-значным, тогда смысл значности числа пропадает.
Это понятно.
Но автор, возможно имел в виду не значность числа, а длину последовательности цифр.

← →
Sha © (2009-07-22 21:32) [27]

> Anatoly Podgoretsky © (22.07.09 21:25) [25]
А про систему счисления я и не подумал даже )
Тогда это второй уточняющий вопрос.

← →
Sha © (2009-07-22 21:42) [28]

> @!!ex © (22.07.09 16:50) [15]
> Имелось ввиду как раз, чтобы обязательно все 10 цифр в каждом числе.

Судя по этому посту, система счисления все-таки десятичная.

← →
Anatoly Podgoretsky © (2009-07-22 21:43) [29]

> Sha (22.07.2009 21:32:27) [27]

Вот именно и видимо действительно путает длину с разрядностью и значинмые и незначимые цифры.

← →
Sha © (2009-07-22 22:38) [30]

Решим задачу в предположении, что автор имел в виду 18 знакомест, на каждом из которых может стоять любая цифра от 0 до 9.
Обозначим искомый результат через F(m,p). У нас m = 10, p = 18.
Обозначим число сочетаний из n по k через C(n,k) = n! / (k!(n-k)!).
Тогда F(10,18) = 10^18 – C(10,1)*9^18 – C(10,2)* 8^18 - … - C(10,9)*1^18.
Здесь вычитаемое равно количеству всевозможных последовательностей длины 18 из 10 цифр, первое вычитаемое - количеству всевозможных последовательностей длины 18, полученных при использовании 9 из 10 цифр, второе - 8 из 10 цифр, и т.д.

Теперь решим задачу в предположении, что автор имел в виду 18-тизначные числа, т.е. на первом месте в последовательности не может стоять 0.
Очевидно, ответом будет G(10,18) = 9*(F(10,17) + 9*F(9,17)),
т.к. мы можем получить искомое число, приписывая цифру 1..9 к произвольной 17-тизначной последовательности цифр, содержащей все 10 цифр, или к последовательности, содержащей все цифры, кроме приписываемой.

← →
Sha © (2009-07-22 22:42) [31]

Правка. Читать так:
Здесь уменьшаемое равно количеству...

← →
Sha © (2009-07-22 22:46) [32]

Еще одна правка, лишняя 9 вкралась в формулу.
Правильно так:
G(10,18) = 9*(F(10,17) + F(9,17)),

← →
@!!ex © (2009-07-23 01:34) [33]

> [25] Anatoly Podgoretsky © (22.07.09 21:25)
> Если смотреть с фиксированым числом знаков, то конечно,
> наглядно видно в машинном представление. А вот о чем говорит
> автор мы узнаем через 30 постов или позже. Но я могу сделать
> упор и вопроса автора

Читайте мои сообщения буквально, и будет с вами истина.

> [29] Anatoly Podgoretsky © (22.07.09 21:43)

Не надо мне опять приписывать то чего я не говорил. Я сказал ьуквально следующее: 18 значное число.
По буквам разберите:
ЧИСЛО ИЗ 18 ЗНАКОВ. Если вы это можете трактовать разными путями, трактуйте в буквальном смысле.
Можете спокойно игнорировать темы с моим авторством, если они настолько сильно вам непонятны.

← →
@!!ex © (2009-07-23 01:35) [34]

> [30] Sha © (22.07.09 22:38)

Спасибо. Имелся ввиду первый вариант.
Это количество возможных комбинаций цифрового кода из 18 знаков(надо было их символами назвать чтоли??).

← →
Sha © (2009-07-23 09:24) [35]

> Sha © (22.07.09 22:38) [30]
Еще одна правка. "Ввиду" конечно же в обоих случаях вместе пишется.
Когда думаю над задачей, отключаю ненужные участки мозга.
Отпуск опять же...

← →
Claus (2009-07-23 09:37) [36]

> Sha © (22.07.09 22:38) [30]

Интересное решение. Нравится. Но, что-то, как мне кажется, в решении, кроме сочетаний, не хватает еще и перестановок.
Хотя, скорее всего, я ошибаюсь.

← →
Bless © (2009-07-23 09:50) [37]

>Sha © (22.07.09 22:38) [30]
>Тогда F(10,18) = 10^18 – C(10,1)*9^18 – C(10,2)* 8^18 - … - C(10,9)*1^18.

Если я ничего не путаю, то это не может быть правильным ответом. Даже если отбросить все вычитаемые, кроме первого, мы уже получаем отрицательное число.
10^18 - c(10,1)*9^18 = = 10^18 - 10*9^18 = =10 * (10^17 - 9^18) Знак выражения всецело зависит от выражения в скобках. Т.е. если 10^17 меньше чем 9^18, то результат меньше 0. Сравним их (эх, школа, школа): 10^17 = e^(17*ln(10)) = e^39.14395 9^18 = e^(18*ln(9)) = e^39.55004 Т.е. 10^17 меньше, чем 9^18.

← →
Bless © (2009-07-23 10:00) [38]

Мое количество тоже неверное, кстати (меньше реального) :)

← →
Bless © (2009-07-23 10:30) [39]

> Sha © (23.07.09 09:24) [35]
>
> > Sha © (22.07.09 22:38) [30]
> Еще одна правка. "Ввиду" конечно же в обоих случаях вместе
> пишется.
> Когда думаю над задачей, отключаю ненужные участки мозга.
>
> Отпуск опять же...

Имхо, написано в [30] как раз правильно, отдельно :)
Вместе пишется только в предложениях типа "ввиду сложившихся обстоятельств..."

← →
Anatoly Podgoretsky © (2009-07-23 10:45) [40]

> @!!ex (23.07.2009 01:34:33) [33]

Не уговаривай, будем вместе мучаться.

← →
Sha © (2009-07-23 10:57) [41]

> Bless © (23.07.09 09:50) [37]
> Если я ничего не путаю, то это не может быть правильным ответом

Тут ты прав.
Я, видно, совсем расслабился на отдыхе, включение-исключение не заметил.
Там надо чередование знаков.
F(10,18) = 10^18 – C(10,1)*9^18 + C(10,2)* 8^18 - C(10,3)* 7^18 + C(10,4)* 6^18 … - C(10,9)*1^18.
Т.к. в первом слагаемом, например, числа в которых отсутствуют цифры 1 и 2, будет учтена дважды, и т.д.

> Bless © (23.07.09 10:30) [39]
> Вместе пишется только в предложениях типа "ввиду сложившихся обстоятельств..."

А тут ты не прав, "иметь ввиду" тоже вместе.

← →
Sha © (2009-07-23 10:59) [42]

Т.к. в первом вычитаемом, блин

← →
Bless © (2009-07-23 11:02) [43]

> Sha © (23.07.09 10:57) [41]
> А тут ты не прав, "иметь ввиду" тоже вместе.
>

http://gramota.ru/slovari/dic/?word=%E2+%E2%E8%E4%F3&all=x

ввиду, предлог (ввиду того что...; ввиду предстоящих расходов), но сущ. в виду (иметь в виду; бросить якорь в виду берега)

← →
palva © (2009-07-23 11:07) [44]

> F(10,18) = 10^18 – C(10,1)*9^18 – C(10,2)* 8^18 - … - C(10,9)*1^18

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

Возьмем первую порцию с мощностью C(10,1)*9^18 Она по замыслу (если я его понял) должна содержать все последовательности в записи которых не участвует одна цифра, но в ней также содержатся все последовательности в которых не участвуют две цифры, три цифры и т. д. Поэтому вычитать C(10,2)* 8^18 и т. д. уже не нужно. Все уже учтено.

Теперь о самом количестве C(10,1)*9^18 По-моему, оно подсчитано неправильно. Здесь мы пытались сосчитать отдельно те последовательности в которых не участвует цифра 0, цифра 1 и т. д. Но если в последовательности не участвует две цифры 0 и 1, то эта последовательность будет сосчитана два раза.

Есть такая комбинаторная формула включения и исключения. Скорее всего, она должна сработать. К сожалению у меня нет времени подумать на эту тему.

← →
palva © (2009-07-23 11:10) [45]

> Sha © (23.07.09 10:57) [41]

Вот это похоже на правду.
(Пока писал, тут изменения произошли)

← →
Sha © (2009-07-23 11:27) [46]

> Bless © (23.07.09 11:02) [43]
согласен

Чтобы увидеть работу формулы включения исключения, можно рассуждать так:
Обозначим через p(n1,n2, ...) число последовательностей, в которые не входят цифры n1,n2,... (может быть, еще какие-то цифры не входят, но это уже не важно). Это число равно (10-n)^18, где n - количество параметров в скобках. Тогда ответом будет:
p() - p(0) - p(1) - ... - p(9) +
p(0,1) + p(0,2) + ... + p(8,9) -
p(0,1,2) - ... - p(7,8,9) +
...
p(0,1,2,3,4,5,6,7,8,9).
Что и даст ответ, приведенный Sha

Кстати, из того, что F(m,m)=m! следует интересное соотношение:

m^m - m! = S(i:=1..m-1) (-1)^(i-1) * C(m,i) * (m-i)^m,

где через S(i:=1..m-1) обозначена сумма по i=1..m-1

Еще вариант:
Пусть f(m,n) - вероятность того, что в мощность множества (или количество уникальных) цифр в последовательности из n цифр равна m.
Каждая цифра равновероятна и вероятность ее появления равна p.
Тогда справедливо:

f(m,n) = f(m,n-1)*m*p+f(m-1,n-1)*(1-(m-1)*p)

Это получается из такиз соображений:
Пусть мы получаем на каждом шаге по одной цифре.
Тогда f(m,n) - вероятность того, что на шаге n мы имеем m уникальных цифр.
Она (вероятность) складывается из двух взаимоисключающих случаев:
1. Случай, когда m уникальных набрали уже на предыдущем шаге (номер n-1). Тогда нам на текущем шаге не нужна очередная уникальная цифра, а нужна уже встретившаяся. Вероятность этого m*p и соответствующее слагаемое есть f(m,n-1)*m*p
2. Случай, когда имеется на одну уникальную цифру меньше, чем требуется. Тогда вероятность получить новую уникальную цифру есть 1-(m-1)*p. И соответствующее слагаемое есть f(m-1,n-1)*(1-(m-1)*p)

Вот отсюда получается формула f(m,n) = f(m,n-1)*m*p+f(m-1,n-1)*(1-(m-1)*p)

Осталось подставить p = 1/10 (потому-что десятичная система счисления, и каждая цифра встречается с вероятностью 1/10),
m = 10 (потому-что уникальных цифр должно бытб 10)
n = 18 (потому-что длина цепочки = 18)

И искомое число найдем как 10^18*f(10,18) = 134672620008326400
На 10^18 домножил чтобы получить количество вариантов. Так как вероятность f(m,n) можно тут интерпретировать как долю искомых чисел от общего их количества

> Alx2 © (25.07.09 14:11) [49]
> 134672620008326400

совпало )

Вот еще один забавный факт: во всех проверенных мной случаях F(m,p) делилось на m!

← →
Readers (2009-09-04 09:20) [51]

Ты как обычно радуешь нас своими лучшими фразами спасибо, беру!

← →
Maxamans (2009-09-17 00:39) [52]

Что, что, а такой подробной статьи не видел давно. Респект и уважуха автору

> Readers (04.09.09 09:20) [51]
>
> Ты как обычно радуешь нас своими лучшими фразами спасибо,
> беру!
>
> Maxamans (17.09.09 00:39) [52]
>
> Что, что, а такой подробной статьи не видел давно. Респект
> и уважуха автору

Это новое слово в спам-технологиях?
Я что-то опять не понимаю .... какой смысл ?

На ум приходит только, что они не себя раскрутить пытаются, а какую-нибудь из внешних ссылок.
Но тут нет лишнего вроде. Или есть?

Еще вариант.
Эти фразы - метки форумов, где боту удалось пройти автоматическую регистрацию и она в настоящий момент действующая.
Потом остается погуглить и все

← →
Autodot (2009-09-17 14:06) [56]

Нелохо получилось. Есть ещё что-нибудь из этой серии?

> Autodot (17.09.09 14:06) [56]
>
> Нелохо получилось. Есть ещё что-нибудь из этой серии?

Еще один

Фразы явно подобраны для минимального риска быть удаленными.
По форумам их уж поиск выдает много.

> Sha © (17.09.09 07:59) [55]
>
> Еще вариант.
> Эти фразы - метки форумов, где боту удалось пройти автоматическую
> регистрацию и она в настоящий момент действующая.
> Потом остается погуглить и все

Похоже, повышают качество баз.

> Но тут нет лишнего вроде. Или есть?

e-mail только...
Скорее всего и правда метят территорию

> TIF © (17.09.09 17:01) [59]
> e-mail только.

Еще есть, например, сообщения других авторов.
В этом случае имеет смысл поднимать тему, чтоб не пропала.
Ну это так, чисто теоретически.

← →
AntiZOG (2009-09-17 21:17) [61]

> @!!ex © (22.07.09 15:20)
>
> 18 значное число.
> Каждая цифра используеться минимум один раз.

Посчитай для 10-значного в цикле(это при нормальном алгоритме на 20-30 сек), а далее полученное число * 10^8

> [61] AntiZOG (17.09.09 21:17)
> Посчитай для 10-значного в цикле(это при нормальном алгоритме
> на 20-30 сек), а далее полученное число * 10^8

В цикле при нормальном, говоришь.

← →
AntiZOG (2009-09-17 21:37) [63]

> Inovet © (17.09.09 21:22) [62]
>
> > [61] AntiZOG (17.09.09 21:17)
> > Посчитай для 10-значного в цикле(это при нормальном алгоритме
> > на 20-30 сек), а далее полученное число * 10^8
>
> В цикле при нормальном, говоришь.

Хотя в общем так не получится.

это было бы 1*10^8.

Ну 10 млрд итераций вполне реально(10^10). допустим на итерацию уходит 100 тактов. При производительности процессоров в 10-15 Гфлопс это займёт (100*10)/15 = 66 Секунд. Код компилировать 64-битный.

>> @!!ex © (22.07.09 15:20)
>> 18 значное число.
>> Каждая цифра используеться минимум один раз.

> AntiZOG (17.09.09 21:17) [61]
> Посчитай для 10-значного в цикле, а далее полученное число * 10^8

Это неверно.
Минимум один раз относится к любой позиции.
В твоем случае минимум один раз означает гарантированное однократное присутствие каждой цифры в первых 10 позициях,
в то время как требуется гарантированное однократное присутствие каждой цифры во всем числе.

← →
AntiZOG (2009-09-17 23:24) [65]

> AntiZOG (17.09.09 23:24) [65]
> Можно сказать только что чисел больше чем 10^8

Можно и точнее сказать (см. [41] и [49])

Сколько вариантов чисел? Найти похожие ветки