PUMaC 2014 · 组合（A 组） · 第 2 题
PUMaC 2014 — Combinatorics (Division A) — Problem 2
题目详情
- [ 3 ] Assume you have a magical pizza in the shape of an infinite plane. You have a magical pizza cutter that can cut in the shape of an infinite line, but it can only be used 14 times. To share with as many of your friends as possible, you cut the pizza in a way that maximizes the number of finite pieces (the infinite pieces have infinite mass, so you can’t lift them up). How many finite pieces of pizza do you have?
解析
- [ 3 ] Assume you have a magical pizza in the shape of an infinite plane. You have a magical pizza cutter that can cut in the shape of an infinite line, but it can only be used 14 times. To 1 share with as many of your friends as possible, you cut the pizza in a way that maximizes the number of finite pieces (the infinite pieces have infinite mass, so you can’t lift them up). How many finite pieces of pizza do you have? Solution: Consider a circle C that contains all points of intersection. Is is clear that all infinite pieces cannot be contained in C and there are no finite pieces outside C . Hence the number of infi- nite pieces is equal to the sectors outside of C . Since each line pass through C , there will be 2 × 14 = 28 infinite sectors outside C . When there are already n lines, we see that the next line can intersect with at most n lines which will divide it into at most n + 1 non-overlapping segments. Since each segment divide one existing area into two, there can be at most n + 1 new areas. Hence with n lines there n ( n + 1) are + 1 areas at most. (Since when n = 0, there is already an area that is the entire 2 plane. Hence with n = 14, we have 106 areas, and 106 − 28 = 78 of them are finite. Next we show that this is possible. By drawing the lines all none parallel and no three lines concurrent, each line must intersect all others at distint points and thus each line will have n + 1 distinct segments that makes n + 1 new areas. Hence this construction will have 106 areas, 78 of them finite.