Editing Birthday problem (section)

==Partition problem==
A related problem is the [[partition problem]], a variant of the [[knapsack problem]] from [[operations research]]. Some weights are put on a [[Weighing scale|balance scale]]; each weight is an integer number of grams randomly chosen between one gram and one million grams (one [[tonne]]). The question is whether one can usually (that is, with probability close to 1) transfer the weights between the left and right arms to balance the scale. (In case the sum of all the weights is an odd number of grams, a discrepancy of one gram is allowed.) If there are only two or three weights, the answer is very clearly no; although there are some combinations which work, the majority of randomly selected combinations of three weights do not. If there are very many weights, the answer is clearly yes. The question is, how many are just sufficient? That is, what is the number of weights such that it is equally likely for it to be possible to balance them as it is to be impossible?

Often, people's intuition is that the answer is above {{val|100000}}. Most people's intuition is that it is in the thousands or tens of thousands, while others feel it should at least be in the hundreds. The correct answer is 23.{{Citation needed|date=December 2016}}

The reason is that the correct comparison is to the number of partitions of the weights into left and right. There are {{math|2<sup>''N'' − 1</sup>}} different partitions for {{math|''N''}} weights, and the left sum minus the right sum can be thought of as a new random quantity for each partition. The distribution of the sum of weights is approximately [[normal distribution|Gaussian]], with a peak at {{math|{{val|500000}}''N''}} and width {{math|{{val|1000000}}{{sqrt|''N''}}}}, so that when {{math|2<sup>''N'' − 1</sup>}} is approximately equal to {{math|{{val|1000000}}{{sqrt|''N''}}}} the transition occurs.  2<sup>23 − 1</sup> is about 4 million, while the width of the distribution is only 5 million.<ref>{{cite journal |first1=C. |last1=Borgs |first2=J. |last2=Chayes |first3=B. |last3=Pittel |s2cid=6819493 |year=2001 |title=Phase Transition and Finite Size Scaling in the Integer Partition Problem |journal=Random Structures and Algorithms |volume=19 |issue=3–4 |pages=247–288 |doi=10.1002/rsa.10004 }}</ref>