Забавная задачка

JAPH

Принимается Это не пройдет, если взять B в качестве константы. А если сказать, что берем B тоже случайным? (Upd: хм, тогда будет неинтересно)

 

Ну если А и В случайно выбираются из диапазона 0..2^n-1, то все равно неверно получается.
Вот, в формуле

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

 

прикольная задача, Black_mirror, молодец))))

 

в первой части надо смотреть числа ввиде: xxxxx....xx0111..11, ххххххх00 и xxxxxxx01.
со второй частью от конст вероятность зависит....... надо ещё подумать, пожалуй, надо конст. рассматривать как С=Z+1 и свести всё к решению на основе первой части задачи.

 

Хотел уже решение отправить для произвольной константы, но раз не все сразу оценили прикольность этой задачки, то я пока подожду, а кто напишет прогу, пусть скажет какая вероятность что F(A)<>F(A+3)

Еще задачка на вероятность:
Функция P(X) с вероятностью p выполняет инверсию булевой переменной. То есть с вероятностью p она вернёт NOT X и с верятностью 1-p вернёт X.
Какая вероятность того, что A&B&C <> P(A)&P(B)&P(C)?

 

Код (Text):

1. #include <stdio.h>
2. #include <stdlib.h>
3.  
4. int f(unsigned char a)
5. {
6.     int i,cnt;
7.     for (i = cnt = 0; i < 8; i++) {
8.         if (a & 1)
9.             cnt++;
10.         a >>= 1;
11.     }
12.     return cnt % 2;
13. }
14.  
15. int main()
16. {
17.     unsigned int i,k,k2,n,a;
18.     double x,y;
19.    
20.     for (k = 1, n = 1; k <= 1000000; k <<= 1) {
21.         x = y = 0;
22.         for (i = k; i < (k << 1); i++) {
23.             if (f(i+3) != f(i))
24.                 x++;
25.             y++;
26.         }
27.         printf("n = %u (%u..%u), p(F(A+3)!=F(A) = %.4f\n",n++,k,(k<<1)-1,x/y);
28.     }
29.  
30.     return 0;
31. }

результат:

Код (Text):

1. n = 1 (1..1), p(F(A+3)!=F(A) = 0.0000
2. n = 2 (2..3), p(F(A+3)!=F(A) = 0.5000
3. n = 3 (4..7), p(F(A+3)!=F(A) = 0.5000
4. n = 4 (8..15), p(F(A+3)!=F(A) = 0.2500
5. n = 5 (16..31), p(F(A+3)!=F(A) = 0.3750
6. n = 6 (32..63), p(F(A+3)!=F(A) = 0.3125
7. n = 7 (64..127), p(F(A+3)!=F(A) = 0.3438
8. n = 8 (128..255), p(F(A+3)!=F(A) = 0.3359
9. n = 9 (256..511), p(F(A+3)!=F(A) = 0.3359
10. n = 10 (512..1023), p(F(A+3)!=F(A) = 0.3359
11. n = 11 (1024..2047), p(F(A+3)!=F(A) = 0.3359
12. n = 12 (2048..4095), p(F(A+3)!=F(A) = 0.3359
13. n = 13 (4096..8191), p(F(A+3)!=F(A) = 0.3359
14. n = 14 (8192..16383), p(F(A+3)!=F(A) = 0.3359
15. n = 15 (16384..32767), p(F(A+3)!=F(A) = 0.3359
16. n = 16 (32768..65535), p(F(A+3)!=F(A) = 0.3359
17. n = 17 (65536..131071), p(F(A+3)!=F(A) = 0.3359
18. n = 18 (131072..262143), p(F(A+3)!=F(A) = 0.3359
19. n = 19 (262144..524287), p(F(A+3)!=F(A) = 0.3359
20. n = 20 (524288..1048575), p(F(A+3)!=F(A) = 0.3359

Вобщем, при возрастании n вер-сть p -> const, причем независимо от константы,которую добавляем:
+1: p->0.6641
+2: p->0.6719
+3: p->0.3359
+4: p->0.6563
и т.д.

 

Ra!N
У тебя в программе есть ошибка: for (i = k; i < (k << 1); i++) - должно быть i=0.
А не перебирая все 2^n значений эту задачу можно решить?

 

Black_mirror

почему?! прога перебирает значения одинаковой разрядности, т.е. 1 (n=1); 2..3 (n=2); 4..7 (n=3); 8..15 (n=4). Начальное значение: 2^(n-1) = k = 1{n-нулей}b, конечное: 2^n-1 = (k << 1)-1 = 1{n-едениц}b

даже в ручную если посчитать (n=3):
А; F(A); A+3; F(A+3); F(A+3)!=F(A)
-----------
100; 1; 111; 1; false
101; 0; 1000; 1; true
110; 0; 1001; 0; false;
111; 1; 1010; 0; true;
p(F(A+3)!=F(A)) = 0.5

ps. если надо посчитать вер-сть того, что ф-ция F(А) от двоичного числа A, разрядностью <= n изменится при добавлении константы, то тогда действительно надо for(i=0;...) писать. Но в исходном задаче было сказано что разрядность равна n.

added:
увеличил точность в проге и заметил, что независимо от прибавляемой константы C, при n>=8, p=const и дальше не изменяется. К примеру:

С=1

Код (Text):

1. n = 1 (1..1), p(F(A+1)!=F(A) = 0.0000000000000000
2. n = 2 (2..3), p(F(A+1)!=F(A) = 1.0000000000000000
3. n = 3 (4..7), p(F(A+1)!=F(A) = 0.5000000000000000
4. n = 4 (8..15), p(F(A+1)!=F(A) = 0.7500000000000000
5. n = 5 (16..31), p(F(A+1)!=F(A) = 0.6250000000000000
6. n = 6 (32..63), p(F(A+1)!=F(A) = 0.6875000000000000
7. n = 7 (64..127), p(F(A+1)!=F(A) = 0.6562500000000000
8. n = 8 (128..255), p(F(A+1)!=F(A) = 0.6640625000000000 = 85/128
9. n = 9 (256..511), p(F(A+1)!=F(A) = 0.6640625000000000
10. n = 10 (512..1023), p(F(A+1)!=F(A) = 0.6640625000000000
11. n = 11 (1024..2047), p(F(A+1)!=F(A) = 0.6640625000000000
12. n = 12 (2048..4095), p(F(A+1)!=F(A) = 0.6640625000000000
13. n = 13 (4096..8191), p(F(A+1)!=F(A) = 0.6640625000000000
14. n = 14 (8192..16383), p(F(A+1)!=F(A) = 0.6640625000000000
15. n = 15 (16384..32767), p(F(A+1)!=F(A) = 0.6640625000000000
16. n = 16 (32768..65535), p(F(A+1)!=F(A) = 0.6640625000000000
17. n = 17 (65536..131071), p(F(A+1)!=F(A) = 0.6640625000000000
18. n = 18 (131072..262143), p(F(A+1)!=F(A) = 0.6640625000000000
19. n = 19 (262144..524287), p(F(A+1)!=F(A) = 0.6640625000000000
20. n = 20 (524288..1048575), p(F(A+1)!=F(A) = 0.6640625000000000

С=5

Код (Text):

1. n = 1 (1..1), p(F(A+5)!=F(A) = 1.0000000000000000
2. n = 2 (2..3), p(F(A+5)!=F(A) = 0.5000000000000000
3. n = 3 (4..7), p(F(A+5)!=F(A) = 0.7500000000000000
4. n = 4 (8..15), p(F(A+5)!=F(A) = 0.2500000000000000
5. n = 5 (16..31), p(F(A+5)!=F(A) = 0.6250000000000000
6. n = 6 (32..63), p(F(A+5)!=F(A) = 0.4375000000000000
7. n = 7 (64..127), p(F(A+5)!=F(A) = 0.5312500000000000
8. n = 8 (128..255), p(F(A+5)!=F(A) = 0.5078125000000000 = 65/128
9. n = 9 (256..511), p(F(A+5)!=F(A) = 0.5078125000000000
10. n = 10 (512..1023), p(F(A+5)!=F(A) = 0.5078125000000000
11. n = 11 (1024..2047), p(F(A+5)!=F(A) = 0.5078125000000000
12. n = 12 (2048..4095), p(F(A+5)!=F(A) = 0.5078125000000000
13. n = 13 (4096..8191), p(F(A+5)!=F(A) = 0.5078125000000000
14. n = 14 (8192..16383), p(F(A+5)!=F(A) = 0.5078125000000000
15. n = 15 (16384..32767), p(F(A+5)!=F(A) = 0.5078125000000000
16. n = 16 (32768..65535), p(F(A+5)!=F(A) = 0.5078125000000000
17. n = 17 (65536..131071), p(F(A+5)!=F(A) = 0.5078125000000000
18. n = 18 (131072..262143), p(F(A+5)!=F(A) = 0.5078125000000000
19. n = 19 (262144..524287), p(F(A+5)!=F(A) = 0.5078125000000000
20. n = 20 (524288..1048575), p(F(A+5)!=F(A) = 0.5078125000000000

С=100

Код (Text):

1. n = 1 (1..1), p(F(A+100)!=F(A) = 1.0000000000000000
2. n = 2 (2..3), p(F(A+100)!=F(A) = 1.0000000000000000
3. n = 3 (4..7), p(F(A+100)!=F(A) = 0.0000000000000000
4. n = 4 (8..15), p(F(A+100)!=F(A) = 1.0000000000000000
5. n = 5 (16..31), p(F(A+100)!=F(A) = 0.5000000000000000
6. n = 6 (32..63), p(F(A+100)!=F(A) = 0.6250000000000000
7. n = 7 (64..127), p(F(A+100)!=F(A) = 0.4375000000000000
8. n = 8 (128..255), p(F(A+100)!=F(A) = 0.5312500000000000 = 17/32
9. n = 9 (256..511), p(F(A+100)!=F(A) = 0.5312500000000000
10. n = 10 (512..1023), p(F(A+100)!=F(A) = 0.5312500000000000
11. n = 11 (1024..2047), p(F(A+100)!=F(A) = 0.5312500000000000
12. n = 12 (2048..4095), p(F(A+100)!=F(A) = 0.5312500000000000
13. n = 13 (4096..8191), p(F(A+100)!=F(A) = 0.5312500000000000
14. n = 14 (8192..16383), p(F(A+100)!=F(A) = 0.5312500000000000
15. n = 15 (16384..32767), p(F(A+100)!=F(A) = 0.5312500000000000
16. n = 16 (32768..65535), p(F(A+100)!=F(A) = 0.5312500000000000
17. n = 17 (65536..131071), p(F(A+100)!=F(A) = 0.5312500000000000
18. n = 18 (131072..262143), p(F(A+100)!=F(A) = 0.5312500000000000
19. n = 19 (262144..524287), p(F(A+100)!=F(A) = 0.5312500000000000
20. n = 20 (524288..1048575), p(F(A+100)!=F(A) = 0.5312500000000000

таким образом не имеет смылса вычислять вер-сти для n>8, все они равны вер-стям при n=8

 

Про последнюю не так:
1/8 *( 1-(1-p)^3) + 3/8*(p^2*(1-p) )+ 3/8*(p(1-p)^2) +1/8*(p^3) ?

 

1-p^3 ?

 

Ra!N
Почему у тебя функция f в качестве параметра принимает байт? Из-за этого после n=8 результат не меняется.

Но не сказано что старший разряд 1. В общем условие нужно понимать так, что A, C, A+C имеют разрядность n, а перенос игнорируется. Хотя можно порешать и другую задачку:

Какая вероятность того, что при прибавлении к числу А(от 0 до +бесконечности) фиксированной константы C, количество единиц в нём изменится?


Velheart
Правильно, но можно было и упростить.

 

Black_mirror

я идиот )

Кстати, мозговые гиганты, подскажите где я ошибся в последней задаче. Я думал так:
сначала найдем вер-сть A&B&C = p(A)&p(B)&p(C) (1). Я предположил что от значений A,B и C версть не зависит. примем A=B=C=1, тогда A&B&C=1, то (1) будет верно, если p(A)&p(B)&p(C)=1, p(A)=p(B)=p(C)=p по условию, тогда p(A)&p(B)&p(C)=p^3. Если так, то исходная вер-сть того что A&B&C != p(A)&p(B)&p(C) будет 1-p^3. Где ошибка.

 

1/2 т.к. бесконечно много чисел для которых количество единиц как изменится, так и останется прежним(если С не ноль), а значит мощности этих множеств равны мощности счетного множества а значит и вероятность 1/2 =))

 

А для С=3, случайно не так получается:
1/2*( p(n)*( 1-p(n-1) ) + p(n-1)*( 1-p(n) ) ) +1/2 ( p(n)*( 1-p(n-2) ) + p(n-2)*( 1 - p(n) ) ), где P(n) -- вероятность для С=1 ??

 

Ra!N
Там нужно рассматривать сколько среди A,B,C единиц, и считать какая вероятность того что значение изменится, а потом просуммировать.

Velheart
1/2 - Это не правильно.
А для C=3 лучше числом, потому что такая формула совсем не наглядна. [add]К тому же еще не правильная.[/add]

Что-то меня еще заинтересовал вопрос, с какой вероятностью
XOR(A,B,C,...)<>XOR(P(A),P(B),P(C),...),
то есть если XOR'им бесконечное количество булевых переменных. Пока даже ряд не желает составляться, хотя я думаю что тут либо константа, либо какая-то простая функция от p.

 

Хех, так про 1/2 была шутка..
А про 3 может так: если К3(n) -- количество n-разрядных чисел, для которых F(x)<>F(x+3), то можем разбить их на две группы: заканчивающиеся на 0 и на 1, тогда из первой группы числа, при сложении с 3 меняют последний бит, а тк переноса не происходит, то F(x)<>F(x+3) будет верно только если F(x div 2)=F(x div 2 +1), те таких чисел
N1=2^(n-1)-((2^(n-1)*2+1) div 3), а для чисел заканчивающихся на 1, сложение с 11b, изменит последний разряд,
второй оставит тем же и прибавит 1 к третьему разряду, те для них F(x)<>F(x+3), только если
F(x div 4)=F(x div 4 +1), те таких чисел N2=2^(n-2)-((2^(n-2)*2+1) div 3), те вероятность получается (N1+N2)/2^n
(я использовал, что P(n)=((2^(n-2)*2+1) div 3)/2^n)?

 

Black_mirror

Если вероятность XOR(...) <> XOR (P(..)) для n переменных обозначить PX(n), то вроде бы PX(1) = p, PX(n) = PX(n-1)(1-2p) + p, если не обсчитался?

 

У меня тоже так получилось, тогда PX(n)=1/2 + ( (1/2-p)^n ) *( (-1)^(n-1) ), а значит при n стремещемся к бесконечности PX=1/2

 

Velheart

Вряд ли, PX должна зависеть от p.

PX(n) = p*(SUM_{i=0}^{n-1}(1-2p)^{i}) = p*(1-(1-2p)^{n})/(2p) = (1-(1-2p)^{n})/2

а здесь уже нужно рассматривать три случая для p (0, 1 и все остальное)

 

Ага, сорри, забыл на 2^n умножить, когда упрощал, но в итоге все равно PX(n)->1/2 для р!=0 или 1,а для них и так очевидно все..