Yet another birthday problem

Feb 2010
Hello everyone,

I would appreciate your help on the following variant of the birthday problem:

Assume that we have a number of identical boxes which all contain N black-or-white balls each. The order of the balls is important, i.e. each box has a placeholder for ball 1 to N. All placeholders of all boxes are filled randomly with balls.

Two given boxes are considered to be "similar" if at least K *corresponding* placeholders contain balls of the same color (which placeholders are not of interest, just their number).

Given N and K, which is the number of boxes that we need in order to have a better than even (>1/2) chance that at least two of the boxes are "similar"?


N=5, K=2
box 1: B-W-B-B-B
box 2: W-B-W-W-W
box 3: B-W-B-W-B

similarity between 1 and 2 = 0
similarity between 1 and 3 = 4
similarity between 2 and 3 = 1

boxes 1 and 3 are considered "similar" (4>=K), all other combination is "dissimilar".