0%

Problem 514


Problem 514


Geoboard Shapes

A geoboard (of order N) is a square board with equally-spaced pins protruding from the surface, representing an integer point lattice for coordinates 0 ≤ x,y ≤ N.

John begins with a pinless geoboard. Each position on the board is a hole that can be filled with a pin. John decides to generate a random number between 1 and N+1 (inclusive) for each hole in the geoboard. If the random number is equal to 1 for a given hole, then a pin is placed in that hole.

After John is finished generating numbers for all (N+1)2 holes and placing any/all corresponding pins, he wraps a tight rubberband around the entire group of pins protruding from the board. Let S represent the shape that is formed. S can also be defined as the smallest convex shape that contains all the pins.

The above image depicts a sample layout for N = 4. The green markers indicate positions where pins have been placed, and the blue lines collectively represent the rubberband. For this particular arrangement, S has an area of 6. If there are fewer than three pins on the board (or if all pins are collinear), S can be assumed to have zero area.

Let E(N) be the expected area of S given a geoboard of order N. For example, E(1) = 0.18750, E(2) = 0.94335, and E(10) = 55.03013 when rounded to five decimal places each.

Calculate E(100) rounded to five decimal places.


几何板图形

(N阶)几何板是一块方形板,板上等间距地插有大头针,分别代表坐标为0 ≤ x,y ≤ N的格点。

约翰拿出一块没有插大头针的几何板,板上的格点处均留有能够插一根大头针的小孔。对于每一个格点,约翰随机指定一个1至N+1(上下限均包含)的数,如果这个随机数恰好等于1,那么就在这个格点处的小孔内插一根大头针。

当约翰对这(N+1)2个位置都指定一个随机数,且把所有应该插上的大头针都插上之后,他拿一根橡皮筋圈住了所有板上的大头针。记S为橡皮筋此时构成的形状,S同时也是包含所有大头针的最小凸多边形。

上面这张图描绘了N = 4时的一个布局样例。绿色的标记表示有大头针的位置,蓝色的线表示橡皮筋。在这个布局中,S的面积为6。如果板上的大头针数目少于三个(或者所有的大头针在一条直线上),S的面积就是0。

记E(N)是在N阶几何板上围出的S的期望面积。例如,当四舍五入保留五位小数时,E(1) = 0.18750,E(2) = 0.94335,以及E(10) = 55.03013。

求E(100)并四舍五入保留五位小数。