Изменения

*Из двух предыдущих рассуждений следует, что существует по крайней мере <tex>2^{i+1}n - 2^{i}n = 2^{i}n</tex> чисел <tex>p</tex> таких, что они не превосходят <tex>b_i</tex> и остаток от деления <tex>x^{(j)}</tex> на <tex>p</tex> не совпадает с остатком от деления любого <tex>x^{(h)}</tex> на <tex>p</tex>.  *Таким образом по крайней мере <tex>2^{i}n</tex> пар чисел <tex>0 \le p_l, r_l \le b_i</tex> отличают набор <tex>x^{(j)}</tex> от всех остальных. Заметим, что при этом множества пар отличающих чисел (<tex>p_l</tex>, <tex>r_l</tex>) для каждого выполняющего набора переменных <tex>x^{(j)}</tex> дизъюнктны. *Следовательно, всего имеется не менее <tex>2^i n \cdot D \ge 2^{2i-1}n</tex> искомых отличающих пар. В данной оценке мы использовали равенство из второго пункта. *Таким образом вероятность выбрать отличающую пару чисел (<tex>p_l</tex>, <tex>r_l</tex>) составляет не менее <tex>\frac{2^{2i-1}n}{16\cdot2^{2i}n^4}=\frac{1}{32n^3}</tex>.