BMAD 63 Report post Posted August 24, 2016 Assume an exclusive OR. Quote Share this post Link to post Share on other sites
1 mmiguel 1 Report post Posted August 26, 2016 (edited) Spoiler Consider this simpler sub-problem. Two boxes, X and Y, share a side. Another box, Z is congruent to the union of X and Y. Figure 1below shows that if X and Y have integer width or height, then so must Z. <SEE FIGURE 1> Furthermore we can replace X and Y by Z and still maintain the problem assumptions, but simplify the problem. By applying this concept multiple times, one can construct the simplified problem in figure 2. <SEE FIGURE 2> First merge C and D; then merge F and G; then merge the results of the last two merges; Then merge that third result with A to get M. Merge H and I; then merge that with J to get N Merge E and K to get O So now we have the simpler problem with B,M,N,L, and O. B (like any other rectangle,) can have either integer width or height, so let's divide our analysis into these two cases. Under those two cases we must show that we cannot assign selections of integer width/height to the other rectangles such that the entire rectangle has neither integer width nor integer height. IF B has integer width instead of height: To prevent the whole rectangle from having integer width, M must have integer height instead of width. But this means that O must have integer width instead of height; and this means that L must have integer height instead of width. We get to the case in Figure 3 <SEE FIGURE 3> If N has integer width, then so does the whole rectangle because of B and O If N has integer height, then so does the whole rectangle because of M and L So if B has integer width (our antecedent), then the whole rectangle is guaranteed to have integer width or height Alternatively, IF B has integer height instead of width: To prevent the whole rectangle from trivially having integer width/height, we must choose L to have integer width instead of height; This leads to assigning O to have integer height instead of width; This leads to assigning M to have integer width instead of height. We get to the case in Figure 4. <SEE FIGURE 4> If N has integer width, then so does the whole rectangle because of M and L If N has integer height, then so does the whole rectangle because of B and O So if B has integer height (our antecedent), then the whole rectangle is guaranteed to have integer width or height Combining the two cases above, regardless of whether B has integer width or height, the whole rectangle is guaranteed to have integer width or height. Edited August 26, 2016 by mmiguel 1 Quote Share this post Link to post Share on other sites
0 tojo928 3 Report post Posted August 25, 2016 Spoiler Firstly, there's way to many rectangles so I'm going to logic some away. Any time a rectangle shares the same full line segment that segment can either be an integer or not. By that logic, the other side of the rectangle would be the opposite. This means the combination of these 2 rectangles has the same properties as the 2 smaller rectangles. You can use this logic multiple times and end up with only 5 rectangles that look roughly like this Now the figure is effectively rotationally congruent so we only need to prove one side full side in an integer and the proof will hold for the other possibilities. So both line segments that make up the right side can be integers, on is and one isn't, and both aren't. Both integers obviously proves the theory for that case One integer and one not creates a situation where the center rectangle will either have to both sides be integers or both side not be integers which contradicts the problem requirements. Both non-integers creates a situation where both of the top have to be integers and proves the theory. Quote Share this post Link to post Share on other sites
Assume an exclusive OR.
Share this post
Link to post
Share on other sites