A cake has the form of an (n x n) square composed of n^2 unit squares. Strawberries lie on some of the unit squares so that each row or column contains exacly one strawberry; call this arrangement A. Let B be another such arrangement. Suppose that every grid rectangle with one vertex at the top left corner of the cake contains no fewer strawberries of arrangement B than of arrangement A. Prove that arrangement B can be obtained from A by performing 'switches', defined as follows: A 'switch' consists in selecting a grid rectangle with only two strawberries, situated at its top right corner and bottom left corner, and moving these two strawberries to the other two corners of that rectangle. ---------------------------------------- Obvious observation: * The arrangements correspond to permutations a: n -> n, where a_i is the row index of the strawberry in the i-th column. If switch didn't have the condition (S) on the interior of the rectangle, we could get any arrangement from any arrangement: * The switch is just swap of two values in our permutation into increasing order. * So, we cannot perform the series of switches if the permutation A is "more sorted" than B. Let's try to translate the condition (C) about A and B into the language of permutations. We count the number of a_i, where a_i < c and i < r. Let's try to prove it first without the condition (S) on the interior of the rectangle in the switches. * I guess, I should try to keep the condition satisfied. * If I can always perform a switch which keeps the condition (C) satisfied, then I will eventually convert A to B because I cannot keep sorting indefinitely. (at least it is very likely that I cannot, I will try to prove it later) * Reversely, if I can convert A to B and A != B, does there must be a way how to perform a switch which keeps the condition (C) satisfied? * Not necessarily, the path to B could hypothetically lead through states in which (C) is not satisfied. It would mean that (C) is not general enough. Right, so let's try find a pair A, B that satisfies the condition but no A',B does where A' is obtained from A by applying a switch With (S). . . O . O . . O . O . . . O . -> . . O -> O . . -> . O . O . . O . . / . . O > . . O \ X / > . . O \ O . . O . . -> . . O . O . . O . Nice partially ordered set. Does it correspond to the condition (C)? Actually, is (C) transitive? If so, it would suggest that there must be a move from A to B. Ah, this is the right question: (1) Does the switch preserve (C)? (2) Is (C) transitive? If both (1), (2) are true, then everything which is reachable satisfies the condition (C), and therefore, restricting moves to only such moves which preserve (C) cannot destroy the reachability of arrangement B. (1) Does the switch preserve (C)? More precisely, if A' is made out of A by one switch, does the pair (A, A') satisfy (C)? Let u v x y denote the corner squares of the switching rectangle. Any rectangle aligned with the left-up corner of the cake can contain the following combinations of these squares: * {} * {u} * {u,v} * {u,x} * {u,v,x,y} If every of these sets contain at least as much of {u,y} as of {x,v}, (1) is confirmed. Checked -> (1) is true. (2) Is (C) transitive? Yes, it immediatelly follows by the transitivity of inequality. Also note that the reverse of (1) is always untrue since there is a rectangle aligned with the upper-left corner of the cake containing only 'u' of the four corners. Actually whenever A <=(C) B and A != B, then not B <=(C) A. This actually proves that I cannot perform the switches indefinitely, since I am always going further in the strict partial order of (C). Now, let's go back to the original problem. I want to show that if A != B and A <=(C) B, then there is available switch A -> A' such that A' <=(C) B. Could the switch use only adjacent columns? No, this edge requires non-adjacent columns. . O . . O . . . O -> O . . O . . . . O Maybe, the problem could be approached in a slightly different way. It looks like that the switches are the minimal steps in (C), that is: If A <(C) B, then exactly one of the following options is true: (a) there is A' such that A <(C) A' <(C) B (b) there is a switch making B from A. Can we find a simple way how to calculate which of these conditions is true? I don't know. Let's start with the general setup A <(C) B. This means that there is a lu-rectangle containing strictly more B than A. Let's take the minimal one, so B has a strawberry in its rd-corner, and A does not. A B ? ? ? ?|? ? ? ? ? ?|? ? ? ? ? ?|? ? ? ? ? ?|? ? ? ? ? .|? ? ? ? ? O|? ? -------+ -------+ ? ? ? ? ? ? ? ? ? ? ? ? But A must have some strawberries in the same row and column, maybe inside the lu-rectangle, maybe not. A B ? ? ? .|? ? ? ? ? ? .|? ? ? ? ? ? O|? ? ? ? ? ? .|? ? ? ? ? ? .|? ? ? ? ? ? .|? ? ? . . . .|. O . . . . O|. . . -------+ -------+ ? ? ? . ? ? ? ? ? ? . ? ? ? Well, they actually must be outside the lu-rectangle, otherwise the chosen lu-rectangle was not minimal. The following rectangle would also satisfy strict inequality: A B ? ? ?|. ? ? ? ? ? ?|. ? ? ? ? ? ?|O ? ? ? ? ? ?|. ? ? ? ? ? ?|. ? ? ? ? ? ?|. ? ? ? . . .|. . O . . . .|O . . . -----+ -----+ ? ? ? . ? ? ? ? ? ? . ? ? ? So they are outside. A B ? ? ? .|? . ? ? ? ? .|? ? ? ? ? ? .|? . ? ? ? ? .|? ? ? . . . .|. O . . . . O|. . . -------+ -------+ ? ? ? . ? . ? ? ? ? . ? ? ? . . . O . . . ? ? ? . ? ? ? ? ? ? . ? . ? ? ? ? . ? ? ? It is suggestive to make the following switch from A to A': A A' B ? ? ? .|? . ? ? ? ? .|? . ? ? ? ? .|? ? ? ? ? ? .|? . ? ? ? ? .|? . ? ? ? ? .|? ? ? . . . .|. O . . . . O|. . . . . . O|. . . -------+ -------+ -------+ ? ? ? . ? . ? ? ? ? . ? . ? ? ? ? . ? ? ? . . . O . . . . . . . . O . ? ? ? . ? ? ? ? ? ? . ? . ? ? ? ? . ? . ? ? ? ? . ? ? ? But this switch maybe does not satisfies condition (S). However, even switches not satisfying (S) still follow the partial order of (C) (the proof does not use the condition (S)). So even if it is not the elementary switch, we could have found an immediate step A' in the chain. Two remaining problems: (1) (Crucial!) Do we still have A' <=(C) B? (2) What if A' is B? -- It can happen but it makes the setup nicer. (1) Do we still have A' <=(C) B? Again, we consider the four corners u v x y of the switching rectangle. lu-rectangles which intersect the corners in {}, {u,v}, {u,x} or {u,v,x,y} do not change the number of strawberries in them. The only remaining case are lu-rectangles containing only {u}. The original lu-rectangle is safe since B contained strictly more strawberries in it. But what about the others? A' B ? ? ? .|? . ? ? ? ? .|? ? ? ? ? ? .|? . ? ? ? ? .|? ? ? . . . O|. . . . . . O|. . . ? O ? .|? . ? . . . .|? ? ? -------+ -------+ . . . . . O . ? ? ? . ? ? ? ? ? ? . ? . ? ? ? ? . ? ? ? It looks that it really breaks it. Do I have a counterexample in my 3 x 3 examples? I don't see it, let's try to just create one. A A' B . .|O . O|. . O|. ---+ ---+ ---+ O . . O . . . . O . O . . . O O . . But this does not work because not A <(C) B, because of hte following rectangle: A B .|. O .|O . O|. . .|. O -+ -+ . O . O . . Now it looks like it can not happen. Let's prove it. Assume that there is a lu-rectangle in which A' has more strawberries than B. A' B ? ? ? .|? . ? ? ? ? .|? ? ? ? ? ? .|? . ? ? ? ? .|? ? ? . . . O|. . . . . . O|. . . ? ? ? .|? . ? ? ? ? .|? ? ? -------+ -------+ ? ? ? . ? . ? ? ? ? . ? ? ? . . . . . O . ? ? ? . ? ? ? ? ? ? . ? . ? ? ? ? . ? ? ? If the last row / column of the rectangle contains the the corner 'u', also the one smaller rectangle of B contains less strawberries than A': A' B ? ? ?|. ? . ? ? ? ?|. ? ? ? ? ? ?|. ? . ? ? ? ?|. ? ? ? . . .|O . . . . . .|O . . . ? ? ?|. ? . ? ? ? ?|. ? ? ? -----+ -----+ ? ? ? . ? . ? ? ? ? . ? ? ? . . . . . O . ? ? ? . ? ? ? ? ? ? . ? . ? ? ? ? . ? ? ? But A contains the same number of strawberries in this rectangle as A', contradiction. There is a remaining case however: What if the rectangle is further from the corner 'u'? A' B ? ? ? . ?|. ? ? ? ? . ?|? ? ? ? ? . ?|. ? ? ? ? . ?|? ? . . . O .|. . . . . O .|. . ? ? ? . ?|. ? ? ? ? . .|? ? ? ? ? . O|. ? ? ? ? . .|? ? ---------+ ---------+ . . . . . O . ? ? ? . ? ? ? ? ? ? . ? . ? ? ? ? . ? ? ? This could cause a problem, there is the weird condition (S) after all. Can we make the problem concrete? A A' B .|. O O|. . O|. . -+ -+ -+ . O . . O . . . O O . . . . O . O . Yes, this is a problem. The more general switches are really insecure. The right move in this case was A A' . . O . . O . O . O . . O . . . O . (or the symmetric one). So I need to fix the general rule of which switch to apply to A: If the switch cannot be made (due to the condition (S)), we find the left-most strawberry inside the intended switching rectangle (excluding corners), and then perform the switch of the ld corner and the strawberry inside: A A' ? ? ? .|? ? ? ? . ? ? ? ? .|? ? ? ? . ? ? ? ? .|? ? ? ? . ? ? ? ? .|? ? ? ? . ? . . . .|. . . . O . . . . .|. . . . O . -------+ -------+ ? ? ? . . . ? ? . ? ? ? ? . . . ? ? . ? ? ? ? . . O ? ? . ? ? ? ? O . . ? ? . ? ? ? ? . . . ? ? . ? ? ? ? . . . ? ? . ? . . . O . . . . . . . . . . . O . . . . ? ? ? . ? ? ? ? . ? ? ? ? . ? ? ? ? . ? Is this safe? If so, we are done and we don't have to discuss the question (2) since the switch we perform already satisfies (S). So the general setup is: We want to perform a switch (satisfying S) on A and corners uvxy. We know that A <(C) B and there is a strawberry 'w' non-strictly above 'u' (in the same column) such that the least lu-rectangle containing 'w' contains one more strawberry than in B than in A. A A' B ? ? ? .|? ? . ? ? ? ? ? ? .|? ? . ? ? ? ? ? ? .|? ? ? ? ? ? ? ? ? .|? ? . ? ? ? ? ? ? .|? ? . ? ? ? ? ? ? .|? ? ? ? ? ? ? ? ? .|? ? . ? ? ? . . . .|? ? . ? ? ? . . . O|. . . . . . -------+ -------+ -------+ ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? . . . . . . O . . . . . . O . . . . . . ? ? ? . ? ? ? ? ? ? ? ? ? . . . . ? ? ? ? ? ? . . . . ? ? ? ? ? ? . ? ? ? ? ? ? ? ? ? . . . . ? ? ? ? ? ? . . . . ? ? ? ? ? ? . ? ? ? ? ? ? . . . O . . . . . . . . . . . . O . . . ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? Can there be a lu-rectangle containing more strawberries in A' than B? A A' B ? ? ? . ?|? . ? ? ? ? ? ? . ?|? . ? ? ? ? ? ? . ?|? ? ? ? ? ? ? ? . ?|? . ? ? ? ? ? ? . ?|? . ? ? ? ? ? ? . ?|? ? ? ? ? ? ? ? . ?|? . ? ? ? . . . . ?|? . ? ? ? . . . O .|. . . . . ? ? ? . ?|? . ? ? ? ? ? ? . ?|? . ? ? ? ? ? ? . ?|? ? ? ? ? . . . . .|. O . . . . . . O .|. . . . . ? ? ? . ?|? ? ? ? ? ? ? ? . .|. . ? ? ? ? ? ? . .|. . ? ? ? ? ? ? . ?|? ? ? ? ? ---------+ ---------+ ---------+ ? ? ? . . . . ? ? ? ? ? ? . . . . ? ? ? ? ? ? . ? ? ? ? ? ? . . . O . . . . . . . . . . . . O . . . ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? We know that in the following two lu-rectangles, there are at least as much strawberries in B as in A' since A' = A on them. A A' B ? ? ?|. ?|? . ? ? ? ? ? ?|. ?|? . ? ? ? ? ? ?|. ?|? ? ? ? ? ? ? ?|. ?|? . ? ? ? ? ? ?|. ?|? . ? ? ? ? ? ?|. ?|? ? ? ? ? ? ? ?|. .|. . ? ? ? ? ? ?|. .|. . ? ? ? . . .|O .|. . . . . ? ? ?|. .|. . ? ? ? ? ? ?|. .|. . ? ? ? ? ? ?|. ?|? ? ? ? ? -----+---+ -----+---+ -----+---+ . . .|. . . O . . . . . .|O . . . . . . ? ? ?|. ? ? ? ? ? ? ? ? ?|. . . . ? ? ? ? ? ?|. . . . ? ? ? ? ? ?|. ? ? ? ? ? ? -----+ -----+ -----+ ? ? ? . . . . ? ? ? ? ? ? . . . . ? ? ? ? ? ? . ? ? ? ? ? ? . . . O . . . . . . . . . . . . O . . . ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? But there is an assymetry about the B-strawberry. I would like to argue that there is at least one more strawberry in B in the union of the two rectangles. I guess I have to distinguish the cases when the B-strawberry is in the intersection (so I am using the original switch), and when it is not (so I am using the modified switch). Case analysis: * Modified switch: Let us denote the arreas as follows: B ? ? ?|. ?|? ? ? ? ? a | b | ? ? ?|. ?|? ? ? ? ? -----+---+ . . .|O .|. . . . . c | d | ? ? ?|. ?|? ? ? ? ? -----+---+ ? ? ?|. ? ? ? ? ? ? e | ? ? ?|. ? ? ? ? ? ? -----+ ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? ? ? ? ? and the numbers of strawberries in them: a_A, ..., e_A, a_B, ..., e_B note that the numbers in A' are equal to the numbers in A. a_A = a_B because the rectangle containing strawberry 'w' was minimal with strict inequality. a_A + c_A + e_A <= a_B + c_B + e_B a_A + b_A <= a_B + b_B So a_A + c_A + e_A + b_A <= a_B + c_B + e_B + b_B d_A = 0, d_B = 1 So a_A + b_A + c_A + d_A + e_A <= a_B + b_B + c_B + d_B + e_B which is what we wanted. * Original switch: Let us denote the arreas as follows: B ? ? ?|. ?|? ? ? ? ? a | b | ? ? ?|. ?|? ? ? ? ? -----+---+ . . .|O . . . . . . c | ? ? ?|. ? ? ? ? ? ? -----+ ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? ? ? ? ? a_A = a_B because the rectangle containing strawberry 'w' was minimal a_A + c_A <= a_B + c_B a_A + b_A <= a_B + b_B so again, we get the required inequality a_A + b_A + c_A <= a_B + b_B + c_B In both cases, the union of the two rectangles contains strictly more strawberries in B than in A. The remaining corner: A A' B ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? ? ? ? . . . . ? ? ? ? ? ? . . . . ? ? ? . . . O . . . . . . ? ? ? . . . . ? ? ? ? ? ? . . . . ? ? ? ? ? ? . ? ? ? ? ? ? +---+ +---+ +---+ . . .|. .|. O . . . . . .|O .|. . . . . ? ? ?|. ?|? ? ? ? ? ? ? ?|. .|. . ? ? ? ? ? ?|. .|. . ? ? ? ? ? ?|. ?|? ? ? ? ? +---+ +---+ +---+ ? ? ? . . . . ? ? ? ? ? ? . . . . ? ? ? ? ? ? . ? ? ? ? ? ? . . . O . . . . . . . . . . . . O . . . ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? contains no strawberry in A, and one strawberry in A'. So the entire lu-rectangle: A A' B ? ? ? . ?|? . ? ? ? ? ? ? . ?|? . ? ? ? ? ? ? . ?|? ? ? ? ? ? ? ? . ?|? . ? ? ? ? ? ? . ?|? . ? ? ? ? ? ? . ?|? ? ? ? ? ? ? ? . ?|? . ? ? ? . . . . ?|? . ? ? ? . . . O .|. . . . . ? ? ? . ?|? . ? ? ? ? ? ? . ?|? . ? ? ? ? ? ? . ?|? ? ? ? ? . . . . .|. O . . . . . . O .|. . . . . ? ? ? . ?|? ? ? ? ? ? ? ? . .|. . ? ? ? ? ? ? . .|. . ? ? ? ? ? ? . ?|? ? ? ? ? ---------+ ---------+ ---------+ ? ? ? . . . . ? ? ? ? ? ? . . . . ? ? ? ? ? ? . ? ? ? ? ? ? . . . O . . . . . . . . . . . . O . . . ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? . ? ? ? ? ? ? . ? ? ? ? ? ? contains at least as many strawberries in B as in A'. We proved that the switch preserves A' <=(C) B until A = B. We cannot perform switches indefinitely (it was proven before), so ultimately, we will reach B.