Czy chciałby może się ktoś podzielić jakimiś trudnymi testami (liczbami do zgadnięcia)?

2137

Okrutnik

Załatwmy Świstakowi 21 łapek w górę i 37 w dół, ja mogę zacząć od łapki w dół

1000500100900

Potwierdzam oba testy.

Skoro już się runda skończyła, to mogę wyjawić tajemnicę, że w tym zadaniu nie istnieje coś takiego jak "trudny test", wszystkie są tak samo trudne nawet w pewnym prawie dowodliwym sensie. Możesz symulować zgadnięcie x pomniejszego o C poprzez dodanie C do wszystkich zapytań które zadasz

@Nadara ale jakie C będzie dobre?

@Marcin Losowe :D

To można udowodnić formalnie: jeśli mamy rozwiązanie, które działa z prawdopodobieństwem 1-ε dla losowych liczb z przedziału [1, 2n], to dodając do ukrytej liczby z przedziału [1, n] losowe C z przedziału [0, n] dostaniemy rozwiązanie, które działa z prawdopodobieństwem co najmniej 1-2ε.