Splitting a 2 by N Rectangle (Posted on 2009-11-11)

	Submitted by Brian Smith
No Rating
Solution:	(Hide)
The possible ways to split the 2xN rectangle fall into five cases: Case 1: Straight across the length: only one way ###### ****** Case 2: Straight across the width: floor[N/2] ways ####** ####** Case 3: An L shaped cut, going from an end to a side: N-1 ways ####** ****** Case 4: Starting and ending on the same side: (N-1)(N-2)/4 + (1/2)*floor[(N-1)/2] **##** ****** Case 5: Starting and ending on opposite sides, but not straight across: (N-1)(N-2)/4 + (1/2)*floor[(N-1)/2] ####** ##**** Adding the five cases yeilds the sum N + floor[N/2] + floor[(N-1)/2] + (N-1)(N-2)/2 The expression floor[N/2] + floor[(N-1)/2] simplifies to N-1 Then the sum equals [N] + [N-1] + [(N-1)(N-2)/2] The last term is the sum of the first N-2 numbers, then the total must simplify to sum of the first N numbers, or N*(N+1)/2. You may notice that the formula fails for N=2. That is because the formula is counting the split into two 1x2 rectangles twice, once for each direction. In other 2xN rectangles those splits are correctly counted as being different.

	Subject	Author	Date
	re(2): Table	brianjn	2009-11-12 10:20:46
	re: Table	Jer	2009-11-12 10:07:14
	Table	brianjn	2009-11-11 20:29:08