Prawdopodobieństwo występowania sumy modulo marek: Mam drobny problem. Mamy trzy zbiory z liczbami losowymi. Zbiór pierwszy A z n liczbami losowymi, zbiór drugi B z m liczbami losowymi i zbiór C z r liczbami losowymi. Wszystkie liczby losowe są wartościami modulo k. Jakie jest prawdopodobieństwo, że w zbiorze C występuje jakakolwiek suma którejś z liczb w zbiorze A z jakąkolwiek z zbioru B (modulo k)? Będę wdzięczny za pomoc. Oczywiście w poszczególnych zbiorach liczby się nie powtarzają. Zakładamy, że max{m,n,r}<k. Możliwych kombinacji jest (k nad m) * (k nad n) * (k nad r). Ile jest jednak kombinacji gdzie nie odnajdziemy sumy?

jc: To może być bardzo trudne, ale ciekawe zadanie. Przykład. Dla k=5 i (n,m,r) = (1,2,4) lub (2,3,3) zawsze odnajdziemy sumę. Byłoby dużo łatwiej, gdyby liczby mogły się powtarzać.

marek: Niestety nie może być to wariant z powtórzeniami Zauważ jednak, że zaprezentowałeś, przypadki z dość małymi rozbierznościami w wartościach pomiędzy k, a max(n, m, r). Jeżeli byśmy mieli np. k = 1000, a (n, m, r) = (200, 200, 200) To łatwo sobie wyobrazić kombinację gdzie nie ma rozwiązania: np. A = {0, 1, ... 199} B = {0, 1, ... 199} C = {800, 801, ... 999} Jak widać nie może istnieć suma A+B=C, ponieważ największa tak uzyskana wartość to 199+199=398 => do 800 daleka droga... Wczoraj także zauważyłem, że dla mojego zastosowania można ograniczyć się do wariantu z n = m = r. Ktoś może ma jakiś pomysł?

jc: Elementy A, B, C losujemy ze zbioru {0,1,2,...,999} Prawdpodobienstwo znalezienia trójki a+b=c będzie niezerowe, ale jak duże? Może zupełnie małe? Dla n=m=r zadanie nadal jest trudne i ciekawe.