Какое мат. ожидание количества итераций?

Математика Комбинаторика
1

Посмотрел вот это видео: Математика помогает раскрыть преступление!.

Условие: Вы детектив и у вас есть 80 человек среди которых ОДИН преступник и ОДИН свидетель. Вы можете взять какое-то подмножество людей на допрос. Если в этом множестве людей есть свидетель, но НЕТ преступника, то свидетель говорит кто преступник. В ином же случае вы не получаете никакой инфы.

Когда прочитал условие задачи, сразу же пришла в голову идея брать случайное подмножество людей (с вероятности 50% берем i-того человека в множество). Но не совсем понятно какое будет в среднем количество дней для того чтобы раскрыть преступление. Написал код (рандом хороший), в итоге не зависимо от количества человек случайный алгоритм решает задачу за 4 хода. Чему я сильно удивился. После раздумий появилась мысль: для каждого человека мы независимо выбираем брать его или нет, всего есть 4 варианта для свидетеля и преступника (00, 01, 10, 11). И возможно из-за этого код находит ответ за 4 дня.

bool is[2000];

int main() {
	speed;
	for (int n = 1; n <= 1000; ++n) {
		int sum = 0, all = 1000;
		for (int t = 1; t <= all; ++t) {
			int k = 0;
			while (true) {
				++k;
				for (int j = 1; j <= n; ++j) {
					is[j] = 0;
					if (bruh() % 2 == 0)
						is[j] = 1;
				}
				if (is[1] && !is[2]) {
					sum += k;
					break;
				}
			}
		}
		cout << n << "\t" << fixed << setprecision(10) << double(sum) / double(all) << '\n';
	}
}

bruh() - это функция рандома)

2 лайка
2

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

1 лайк
3

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

Первое равно \sum_{i=0}^{78}C_{78}^{i} = 2^{78} (поймите почему), а второе равно 2^{80}. Выходит вероятность того, что в случайной группе мы найдем преступника равна \frac{1}{4}.

Выходит вероятность того, что после четырех попыток мы не найдем преступника равна \left(\frac{3}{4}\right)^4 \approx 31\%. Возможно поэтому за 4 дня находит ответ.

1 лайк