TECH-MUSINGS

Thoughts On Algorithms, Geometry etc...

Thursday, September 06, 2012

A Further Thought on Fair Partitions

Here, we attempt to generalize the (still not fully settled) 'fair partition' conjecture for convex regions and suggest that even if it is true, it may only be 'just true'.

The original 'fair partition' conjecture:

"Given a positive integer n, any convex 2D region allows partition into n convex pieces such that all pieces have the same area and perimeter."

With n fixed at 2, let us generalize the question to: given 2 positive numbers a and b and if a convex region C is to be divided into 2 convex pieces with their areas in the ratio a:b and perimeters in the ratio sqrt(a) : sqrt(b) (obviously, if a =b=1, we have the original convex fair partition problem). Generalization of this question to general n is obvious.

A simple case where such a 'proportionately fair' partition is possible: Consider a rectangle 1 X 4 units. Say, it is to be cut into 2 *convex* pieces of areas 1:3 and perimeters in ratio 1: sqrt(3) = 0.56

1. If dividing line is parallel to the width side of the rect and the area ratio of the 2 resultant pieces is 1:3, then, perim ratio is 4:8 = 0.5.

2. If dividing line is parallel to the length side of rect and area ratio is 1:3, then, perim ratio is 8.5 : 9.5 =0.89.

Between these two extreme orientations, the dividing line has a continuous range of orientations and as it is varied, the perimeter ratio will range continuously from 0.5 to 0.89. and this interval has the required perim ratio of 0.56.

However, we see that even if C is a circle, for piece areas in the ratio 1:3, such a proportionately fair partition is not possible, the main reason being the requirement that the pieces be convex.

----------

We are led to the following guesses:

Guesses: for general n, for any other ratio than a_1: a_2:....: a_n = 1:1:....:1 (the 'basic' fair partition case where all areas are equal and all perimeters are equal), there is always some convex shape which *does not* allow a proportionately fair partition. Indeed, we suspect the circular disc might allow *only* the basic fair partition (all a's equal to 1) - and hence the basic fair partition is somehow special for some deeper reason. In other words, even if the basic fair partition conjecture is correct (for general n - values that are not prime powers - it is as of now an open question), it may only be JUST CORRECT.

Further doubt: is the circular disc the only 2D convex shape which disallows a proportionately fair partition whenever a's are not all equal to 1?