Количество наборов запросов для игры угадать число? - PullRequest
Новая
       28

Количество наборов запросов для игры угадать число?

0 голосов
/ 25 октября 2018

Я задавал эту проблему на math.stackexchange, но не получил никакого ответа.

Задача состоит в том, чтобы решить игру на угадывание чисел для двух игроков.Пусть первый человек будет A , а второй человек будет B .A выбирает число x между 1 и верхним пределом n. B дает запросы A в форме (L, R) и A ответит Да / Нет, если число существует в интервале (L, R) оба включительно.

B потребуется задать набор запросов, чтобы однозначно определить число x.Таким образом, проблема состоит в том, чтобы найти количество таких различных наборов запросов, чтобы B мог однозначно определить x независимо от значения x. A возвращает ответы на запросы как целую серию - B получает ответы "да / нет" в пакете, только после выполнения всех запросов.

Например, скажем, n равно 2. Наборы возможных запросов будут: 

{(1,1)}, 
{(2,2)}, 
{(1,1),(2,2)},
{(1,1),(1,2)},
{(2,2),(1,2)}, 
{(1,1),(2,2),(1,2)}

Вопрос : Как определить, какой из этих запросовнаборы будут однозначно идентифицировать любое целое число, которое A может выбрать?

Я мог бы подумать, что нам нужно в основном выделить все возможные числа от 1 до n вкаким-то образом, иначе невозможно однозначно определить номер.Но я понятия не имею, что делать с этой информацией.

1 Ответ

0 голосов
/ 25 октября 2018

Установите # 1 для обнаружения числа:

1 установите для всех одиночных пар: {{1,1},{2,2},...,{N,N}}

Установите # 2 для обнаружениячисло:

N наборы с одиночными парами, кроме одной пары: {{1,1},{2,2},..,{x-1,x-1},{x+1,x+1},..,{N,N}}

Пары, которые не могут помочь идентифицировать номер:

N-1 пары длиной 2: {1,2},{2,3},,{N-1,N}

N-2 пары длиной 3: {1,3},{2,4},,{N-2,N}

...

2 парыс длиной N-1: {1,N-1},{2,N}

1 пар с длиной N: {1,N}

Общее количество бесполезных пар: 

K = (N-1) + (N-2) + ... 2 + 1 = N*(N-1)/2

Общее количество бесполезных наборов: 

Z = C(K,0) + C(K, 1) + ... + C(K, K) = 2^K

Количество наборов запросов

Чтобы найти ответ, нам нужно объединить все правильные наборы со всеми другими типами наборов.. 

ANSWER = (Number of set #1 + Number of sets #2) * Z = (1 + N) * (2^K)

UDP : Ответ неправильный, см. Комментарий ниже

...