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

Генерировать случайные 10-тизначных номера, каждый проверять на существование. Примерно в районе первой сотни будет сгенерирован существующий случайный номер.

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

sdf>Генерировать случайные 10-тизначных номера, каждый проверять на существование. Примерно в районе первой сотни будет сгенерирован существующий случайный номер.

Верно! Забыл упомянуть: 10-тизначное число можно сгенерировать лишь однажды. Типа лотерея такая. По телеку сто раз шарики тянуть никто не собирается...

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

C>Верно! Забыл упомянуть: 10-тизначное число можно сгенерировать лишь однажды.

Что-нибудь еще вы не забыли упомянуть? Например, то, что лотерея идет в прямом эфире, в исходном условии не было.

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

Сгенерировать 1 номер и опубликовать его. Выбрать человека с таким же или максимально похожим номером паспорта.

Например, человека с номером 1234567890 нет, значит ищем человека с номером 123456789х. Если опять нет, ищем человека с номером 12345678хх. Если таких людей несколько (их будет не более 9), провести среди них жребьёвку.

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

U>Сгенерировать 1 номер и опубликовать его. Выбрать человека с таким же или максимально похожим номером паспорта.

U>Например, человека с номером 1234567890 нет, значит ищем человека с номером 123456789х. Если опять нет, ищем человека с номером 12345678хх. Если таких людей несколько (их будет не более 9), провести среди них жребьёвку.

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

Вношу правку: генерируем 1 случайный номер и находим паспорт с таким же или наиболее близким значением. Т.е. чтобы модуль разницы сгенерированного и реального паспорта был минимальным (в идеале, равен нулю). Кандидатов может оказаться два, среди них проводится жрьебьвка.

это же частный случай задачи -- имея равномерный генератор целых чисел 1..N сгенерирвать равномерное целое 1..M
Понятно, что если N и M взаимно просты, то за гарантированно ограниченное число шагов равномерное целое 1..M сгенерировать нельзя

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

U>Вношу правку: генерируем 1 случайный номер и находим паспорт с таким же или наиболее близким значением. Т.е. чтобы модуль разницы сгенерированного и реального паспорта был минимальным (в идеале, равен нулю). Кандидатов может оказаться два, среди них проводится жрьебьвка.

нет, не может быть двух кандидатов, если увеличивать номера в одну сторону (например, в большую) пока не найдем первый существующий.

но тут все от схемы генерации нормеров зависит. я как-то уже писал в "хакере", что в "что где когда" рулетка очень сильно не случайная, а очень даже предсказуемая и для такой интеллегентной передачи -- недопустимая лажа. последовательность выпавших конвертов в занчительной мере определяется первым ходом. второй ход делает третий ход сильно предсказумым. на четвертый ход уже можно делать ставки.

т.к. здесь паспорта 10 ти значные и победитель один, то это будет работать. но только при условии, что номера распределены по диапазону равновеоятно, в чем я сильно сомневаюсь (но таковы условия задачи).

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

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

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

C>Верно! Забыл упомянуть: 10-тизначное число можно сгенерировать лишь однажды. Типа лотерея такая. По телеку сто раз шарики тянуть никто не собирается...

А если не сто, а 10?
1. Кидаем шарик в диапазоне [0..9] — это будет первая цифра в номере.
2. Кидаем ещё раз — это будет вторая.
И ... Упс! Выйдем ли мы на номер?

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

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

sdf>>Генерировать случайные 10-тизначных номера, каждый проверять на существование. Примерно в районе первой сотни будет сгенерирован существующий случайный номер.

C>Верно! Забыл упомянуть: 10-тизначное число можно сгенерировать лишь однажды. Типа лотерея такая. По телеку сто раз шарики тянуть никто не собирается...

1. Сгенерировать 10-тизначное число [N1...N10]
2. Проверить, есть ли паспорт с таким номером. Если есть — конец
3. Путем последовательной замены цифр выпавшего числа и проверки на существование паспорта с таким номером, собрать все паспорта, отличающиеся от выпавшего числа на 1 в одном из знаков. Если кандидатов несколько — выбрать из них одного случайно или по заданной процедуре, например:
— приоритет получает номер, у которого отличается младший разряд, например [N1...(N10+1)] предпочительнее чем [N1...(N9+1) N10]
— при равенстве номера отличающегося разряда, приоритет получает меньший номер, т.е. [N1...(N9-1) N10] предпочительнее чем [N1...(N9+1) N10]
4. Если в п.3 ни одного паспорта не найдено, аналогично ищутся все паспорта отличающиеся на 2 в одном разряде, на 3 и т.д. ... потом в двух разрядах и т.д. до нахождения победителя, что неизбежно.

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

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

Потому что это частный случай известной задачи -- сгенерировать равномерно распределенное случайное 1..M если в наличии есть генератор равномерно распределенных 1..N.
Решение за ограниченное число итераций (тем более всего лишь за одну итерацию) есть только в очень редких случаях (скажем, если N кратно M).

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

D>ну не будет справедливого распределения хоть ты тресни (если число владельцев паспортов не является редким круглым числом).

D>Потому что это частный случай известной задачи -- сгенерировать равномерно распределенное случайное 1..M если в наличии есть генератор равномерно распределенных 1..N.
D>Решение за ограниченное число итераций (тем более всего лишь за одну итерацию) есть только в очень редких случаях (скажем, если N кратно M).

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

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


D>это же частный случай задачи -- имея равномерный генератор целых чисел 1..N сгенерирвать равномерное целое 1..M
D>Понятно, что если N и M взаимно просты, то за гарантированно ограниченное число шагов равномерное целое 1..M сгенерировать нельзя
В этой задаче N и M известны и не являются взаимно простыми

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

D>ну не будет справедливого распределения хоть ты тресни (если число владельцев паспортов не является редким круглым числом).

D>Решение за ограниченное число итераций (тем более всего лишь за одну итерацию) есть только в очень редких случаях (скажем, если N кратно M).
Вообще-то по условию N как раз кратно M

А>с точки зрения обывателя, в чём несправедливость? Кто получает изначальное преимущество или как его можно получить?

ок, нужно тогда спросить, хотим ли мы равномерного распределения выигрыша при уже имеющейся раздаче паспортов. Или нас устроит равномерное распределение выигрыша, считая что само распределение номеров паспортов уже изначально случайно и включено в "справедливость".

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

Во втором случае собственно никаких случайных цифр и генерировать не нужно. Достаточно сказать -- победил самый маленький номер, и начать тестировать начиная с 0 пока не наткнемся на победителя.

sdf>В этой задаче N и M известны и не являются взаимно простыми

ок, я думал, что они составляют _приблизительно_ одну пятидесятую.
Если ровно, то все хорошо, удивительно точная страна, Швейцария наверно

sdf>И как предполагается искать этих двух кандидатов? Если кто-то заявит, что его паспорт достаточно близок...

...его заявку берут на учёт. Сбор заявок заканчивается через 30 дней, и определяется победитель. Кто не успел — тот опоздал.

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

sdf>>И как предполагается искать этих двух кандидатов? Если кто-то заявит, что его паспорт достаточно близок...

U>...его заявку берут на учёт. Сбор заявок заканчивается через 30 дней, и определяется победитель. Кто не успел — тот опоздал.
А почему через 30 дней, а не через 3 или, скажем, 3,1415?

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

C>Решили в некой стране разыграть некий приз между всеми её гражданами. Для этого решено было использовать номера паспортов в качестве определения призёра. Для номерования паспорта там используется десятизначное число в то время, как реально существующие номера составляют лишь одну пятидесятую от всех возможных, и они случайным образом разбросанны по всему диапазону. Получить список всех используемых номеров не представляется возможным, можно только проверять какой либо номер на существование. Как в таких условиях справедливо(равновероятно) разыграть приз между всеми гражданами сей страны?

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

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

C>Решили в некой стране разыграть некий приз между всеми её гражданами. Для этого решено было использовать номера паспортов в качестве определения призёра. Для номерования паспорта там используется десятизначное число в то время, как реально существующие номера составляют лишь одну пятидесятую от всех возможных, и они случайным образом разбросанны по всему диапазону. Получить список всех используемых номеров не представляется возможным, можно только проверять какой либо номер на существование. Как в таких условиях справедливо(равновероятно) разыграть приз между всеми гражданами сей страны?

Мне кажется тут может иметься в виду 2 варианта справедливости:
1) "истинная справедливость", т.е. у нас есть уже фиксированные номера паспортов, и нужно между ними равновероятно разыграть приз. Такая форма справедливости представляется мне затруднительной. Во-первых, соображения про теоретическую невозможность если число всех номеров не делится на число выданных паспортов, если трактовать одну пятидесятую как общую идею разрешенности без реальных цифр. Во-вторых, даже если есть строгая делимость, то кажется сложным представить метод, кроме полного пересчета всех номеров, выделения их по 50 для каждого паспорта и т.д. Например допустим, что есть номера 1, 9999999999, 9999999989, 9999999998, 9999999988, 9999999997. Нелегко придумать метод, чтобы они оказались равноправны.

2) "справедливость до рождения" т.е. сначала случайно раздаются номера паспортов, а потом разыгрывают приз. Т.е. уже случайная раздача номеров "перекашивает" вероятность получить приз на них, но так как эта раздача случайна, то это достаточно справедливо. Такая справедливость легко достижима например следующим способом:

2.1) Рассмотрим такую модель, когда позиция каждого числа одинакова, нет "углов".
Представим десятизначные числа не как куб, а как тор, введя операцию -> для цифр.
x -> 1 = x==9 ? 0 : x+1;
x <- 1 = x==0 ? 9 : x-1;

2.2) Введем любое упорядочивание по близости на этом торе. Например,
самым близким к числу abcdefghij мы считаем само число
abcdefghij
следующее по близости
abcdefghi(j->1)
дальше
abcdefghi(j->2)
abcdefghi(j->3)
..
abcdefghi(j->9)
дальше
abcdefgh(i->1)(j)
abcdefgh(i->1)(j->1)
abcdefgh(i->1)(j->2)
...
abcdefgh(i->1)(j->9)
abcdefgh(i->2)(j)
и т.д.

2.3) Выкидываем произвольное число abcdefghij, ищем к нему ближайший существующий паспорт, согласно введенному упорядочиванию.

Здравствуйте, Caracrist, Вы писали:
C>Решили в некой стране разыграть некий приз между всеми её гражданами. Для этого решено было использовать номера паспортов в качестве определения призёра. Для номерования паспорта там используется десятизначное число в то время, как реально существующие номера составляют лишь одну пятидесятую от всех возможных, и они случайным образом разбросанны по всему диапазону. Получить список всех используемых номеров не представляется возможным, можно только проверять какой либо номер на существование. Как в таких условиях справедливо(равновероятно) разыграть приз между всеми гражданами сей страны?
сгенерировать число и обявить, что финалисты это все, у кого совпадает 8 из 10 цифр, то есть две (или три в зависимости от кол-ва людей или правил проведения) может не совпадать. таким образом набирается с десяток финалистов и среди них проводится дополнительный тур.

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

C>Решили в некой стране разыграть некий приз между всеми её гражданами. Для этого решено было использовать номера паспортов в качестве определения призёра. Для номерования паспорта там используется десятизначное число в то время, как реально существующие номера составляют лишь одну пятидесятую от всех возможных, и они случайным образом разбросанны по всему диапазону. Получить список всех используемых номеров не представляется возможным, можно только проверять какой либо номер на существование. Как в таких условиях справедливо(равновероятно) разыграть приз между всеми гражданами сей страны?

IMHO, тут важно понять, что это за страна такая, что списка граждан нет, а граждан примерно 200 миллионов...
Я вижу только два кандидата:
1) Бразилия прямо сейчас
или
2) РФ + Украина + Казахстан + РБ после объединения, с учётом произошедшей за время объединения потери граждан.

С учётом результатов этого геополитического анализа, легко уточнить понятие "справедливость" присутствующее в условии.

Если 2, то надо просто поросить Владимира Путина назвать правильный номер паспорта, а если 1, то всё совсем по другому -- спросить надо у Дилмы Русеф...

E>1) Бразилия прямо сейчас
E>... а если 1, то всё совсем по другому -- спросить надо у Дилмы Русеф...

Кстати, а кто-нибудь знает, в Бразилии номера паспортов тоже 10-значные?...

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

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

Для простоты предлагаю считаь, что в лотерею разыгрывают не приз, а того, кого принесут в ежегодную жертву дракону. То есть рассчитывать на содействие владельцев паспортов не стоит...

Здравствуйте, Erop, Вы писали:
E>Для простоты предлагаю считаь, что в лотерею разыгрывают не приз, а того, кого принесут в ежегодную жертву дракону. То есть рассчитывать на содействие владельцев паспортов не стоит...
тогда после обьявления финалистов назначается приз за доставку любого из финалистов в студию первым

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

C> можно только проверять какой либо номер на существование.
Проверяем на существование все номера от 0000000000 до 9999999999. Все существующие номера записываем. Выбираем случайные. Выдаем приз.

Здравствуйте, мыщъх, Вы писали:


U>>Вношу правку: генерируем 1 случайный номер и находим паспорт с таким же или наиболее близким значением. Т.е. чтобы модуль разницы сгенерированного и реального паспорта был минимальным (в идеале, равен нулю). Кандидатов может оказаться два, среди них проводится жрьебьвка.

М>нет, не может быть двух кандидатов, если увеличивать номера в одну сторону (например, в большую) пока не найдем первый существующий.

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

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

E__>Здравствуйте, мыщъх, Вы писали:


U>>>Вношу правку: генерируем 1 случайный номер и находим паспорт с таким же или наиболее близким значением. Т.е. чтобы модуль разницы сгенерированного и реального паспорта был минимальным (в идеале, равен нулю). Кандидатов может оказаться два, среди них проводится жрьебьвка.

М>>нет, не может быть двух кандидатов, если увеличивать номера в одну сторону (например, в большую) пока не найдем первый существующий.

E__>Как владелец паспорта 0000000001, я был бы категорически против такой дискриминации. Потому как у меня достоверно возможно только точное совпадение, в то время как для остальных есть шанс, что номер совпадет с одним из диапазона свободных номеров с более низким номером.

так ведь сдвиг циклический. сколько "пустых" номеров между последним наибольшим валидным номером и MAX_NUM ? если номера распределены случайно, то у вас хорошие шансы, что выпадет номер в "дыре" на верху и ваш номер будет следующим. это же кольцо. типа круглый стол. в нем все номера равноправны.

можете смоделировать на компе