3

Part of 2009 239 Open Mathematical Olympiad

Problems(2)

Making triangles out of sticks

Source: 239 2009 S3

200

sticks are given whose lengths are

1, 2, 4, \ldots , 2^{199}

. What is the smallest number of sticks needed to be broken so that out of all the resulting sticks, several triangles could be created, if each stick could be broken only once, and each triangle can be created out of only three sticks?

Friend/Stranger graph

Source: 239 2009 J3

The company has

100

people. For any

k

, we can find a group of

k

people such that there are two (different from them) strangers, each of them knows all of these

k

people. At what maximum

k

is this possible?