Aritra Banik
We consider the following puzzle that Peter Winkler has popularized and though the creator of the puzzle remains unknown, Winkler has traced the earliest documentation of the problem to IBM's puzzle webpage. We quote "Given n distinct points in the unit square [0,1]^2, including the origin (0,0) as one of the n points. Can you construct n rectangles, contained in the unit square, with sides parallel to the coordinate axes, pairwise non-intersecting, such that each of our n given points is the lower-left-hand corner of one of the rectangles, and such that the total area of the rectangles is at least 1/2?"
Dumitrescu and Toth give a two-player one-round game interpretation of the above problem where Alice chooses the n-point set P and Bob chooses axis-parallel interior-disjoint rectangles whose left bottom corners are anchored at points chosen by Alice, i.e. Bob chooses anchored-rectangles. The conjecture has been that Bob can choose anchored-rectangles such that the rectangles jointly cover at least half of R. There was no known algorithm for constructing such a set of rectangles; even nothing was known about whether a set of anchored-rectangles can be constructed that can cover any constant fraction, however small. Dumitrescu and Toth gave fairly non trivial methods that can cover at least 0.09121 of the area, i.e. roughly 9% of the area. We give an existential proof of the conjecture that whatever P be, there always exists a covering of more than half of R with anchored-rectangles.