Minesweeper tactics

This being a mathematics blog, I’m sure a lot of readers out like to play Minesweeper. I’ve just obtained a personal best today (94 seconds on expert level) which, as Minesweeper buffs know, is nowhere close to world-class levels, but which made me happy anyway, as I’d never broken into the double digits before today!

It seems to me that world-class competitors must know some tricks with the mouse which I’ve never bothered to master, particularly because my laptop doesn’t have a mouse but rather a touchpad. This being the case, I keep my right index finger on the touchpad to guide the cursor, and the left index finger to click. I always left-click: that is, in my style of play, I [practically] never flag squares for bombs; I click only on non-bomb squares. For it’s well-known, or at least it should be, that the program doesn’t care if you identify where the bombs are — you get full credit for only identifying all the numbered squares.

To play in this style well, one needs to be fluent in a number of tactical tricks, which I don’t have good names for, but which in my personal argot I call things like “1-2-1″, “1-2-2-1″, “rule of three”, to name just a few. But that’s not what I set out to discuss, really. What I’d really like to hear from good players is: what opening strategies do you use?

The personal best I just set came after deciding on a new opening strategy. What I had been doing is clicking along border squares. Under that strategy, one could of course just keep clicking until one opens up an area, but often I would add to that the observation that if one clicked on a 1, thus leading to, e.g.,

x 1 x (–> border row)
x x x

then one could then click on the non-border square just adjacent to the 1, with only a 1 in 5 chance of setting off a bomb. If one then hits another 1:

x 1 x
x 1 x
x x x

then one can immediately open up the line of squares on the third rank, leading to a configuration such as

x 1 x
x 1 x
1 1 1

or better. This is often a cheap and quick way of opening up squares or otherwise getting a tactical toehold.

The new strategy I began using today is not to click along the border, but to click along the ranks or files adjacent to the border. Under this strategy, if one lands on a 1, leading to

x x x  (–> border row)
x 1 x
x x x

then one can click on the border square adjacent to the 1, with only a 1 in 8 chance of setting off a bomb. If one does not set off a bomb, that square has to be a 1:

x 1 x
x 1 x
x x x

and then one can proceed as before. So I’ve just lowered my odds of hitting a bomb, plus a very small fractional gain in processing time that comes with the certain knowledge that it’s a 1 if not a bomb. So far the strategy has paid off well!

I’d like to hear other people’s opening strategies, and also I’d like to know some statistics. For example, considered over the space of expert-level games, what is the probability of getting a 1, a 2, and so on? Does anyone know? (It seems this would be very difficult computing analytically — one is probably better off using a Monte Carlo simulation. But I don’t have the wherewithal to set that kind of thing up.)

Happy Co-Valentine’s Day!

Love is like PI – natural, irrational and very important!
- Lisa Hoffman

Happy Co-Valentine's Day

Valentine’s Day is usually associated with romantic love, but I think such an idea although wonderful is somewhat restrictive. This time of the year, I believe, is also about letting people close and dear to you know how much you love and care about them! Keeping that in mind, I wish my parents a Happy Valentine’s Day and hope that my younger brother, Vishant, has a great Valentine’s Day too!

I also sincerely hope that Todd gets to spend a great Valentine weekend with his wife and family! And, here’s hoping that all our readers and my friends (including Aditya, Pawan and Kenji!) will today not hesitate in expressing their love to their near and dear ones.

And very importantly, here’s wishing Carolyn an unforgettable Valentine’s Day! Thanks for being my Valentine even though you are thousands of miles away!!

[I do hope Todd will forgive me for posting something completely non-mathematical. In my defense, this post has at least a reference to PI and category theory! ]

Link to 43rd Carnival of Mathematics

I would like to quickly point out to our readers that Jason Dyer is currently hosting the 43rd Carnival of Mathematics and that the Carnival lists Todd’s POW-11 (Preserving Sums of Squares) post as one of its entries!

An integration question

A reader brought up essentially this question: does anyone happen to know a proof that does not possess an elementary antiderivative? By “elementary”, I mean a member of the class of functions which contains all constants valued in the complex numbers, the identity function, the exponential and log functions, and closed under the four basic arithmetic operations and composition.

World Chess Championship 2008!

Perhaps most people are preoccupied with the global financial crisis right now, especially with people in the US much more focused on the upcoming US presidential election in November. So, for those who haven’t been following the news in chess closely I would like to bring their kind attention to the current World Chess Championship (2008) match (Bonn, Germany) between two supreme chess grandmasters, Vishwanathan Anand (India) and Vladimir Kramnik (Russia). Technically, Anand (pronounced Aa-nand and not A-naand; well, actually it is more like Aa-nundh) is the current world chess champion, but personally I think that his winning the World Chess Championship Mexico (2007) last year was a somewhat “unsatisfactory” accomplishment, if you will, given that he won the crown by winning a tournament and not a “classical” chess match. I fervently believe that a person should be crowned world chess champion (like Fischer, Kasparov, Capablanca, Kramnik, to name a few) only after he or she has won a “proper” world championship match played under “classical time controls” (remember the  Fischer-Spassky match in 1972 and the Kasparov-Kramnik match in 2000?)  Without that, the gravitas of the chess crown is somewhat diminished. 

So, here is Anand’s chance now to silence his critics, of which there are very few really, once and for all that he is indeed the undisputed world chess champion! And judging by the result of the third game, which he just won in a dramatic fashion (woohoo!), as well as the tremendous amount of home preparation it clearly seems he has done, there is no doubt that he is on a steady path to the crown. In all the first three games, Anand has demonstrated thus far that he is the superior player. Of course, there are nine more games left and the bets are not off by any means. After all, it was Kramnik who beat Kasparov convincingly in 2000 to win the crown. 

For analyses of the first two games, click here and here. 

Ok, so here is a poll that I invite our readers to participate in. (Obviously, if you choose the “wrong” answer, all your future comments on this blog will be deleted! So, think hard before you vote.)

Firefox 3.0 is now ready!

Don’t forget to download Firefox 3.0 today!

Time for another Republican President… again?

Update: Look for the ’sexism’ video at the end of this post that essentially strengthens my argument about the media treatment meted out to a woman, who was/is as capable as any other candidate, running for a very high office in America, the world’s oldest democracy and whose founding fathers, as we learn from history, were the children of The Enlightenment!

———————————

With the Democratic primary race practically over now and knowing, as we all do, who the nominee is going to be, I just couldn’t resist writing a post on this one, having avoided writing anything about politics all this while.

Well, it was quite appalling to see/hear all these months that when it came to Hillary the discussions/commentaries in the so-called “mainstream” media were similar to ones that are generally heard in men’s locker rooms, while Obama has been treated almost like a God-like figure. And while Hillary’s “racist” remarks were dissected/analyzed with great relish, no one, it seemed to me, paid any particular attention to the disgusting misogynist remarks directed at her throughout the primary campaign season, with the result that the Democratic party has managed, or so it seems, to lose its grip over white women voters now. I have a feeling that this is going to cost the Democrats another general election. (Of course, I could be wrong; I am not a political “pundit”, after all!)

So much has my mother been miffed/angry at the blatant sexist remarks openly made in the media against Hillary that she has vowed now to vote for McCain this Fall. To her, the contest has “demonstrated” yet again that women still haven’t been able to break the glass ceiling in this male-dominated world. Is anyone listening to women voters like her?

A video sample:

In mathematical parlance, this is the only instance in which Left = Right, if you know what I mean.

A proof from The Book?

The late great Paul Erdös was not a religious man (his take on religion seems to have been fairly ironic, referring for example to God as “The Supreme Fascist”), except of course when it came to mathematics. Ever the Platonist, he considered that when he died, he might finally get a chance to gaze upon “The Book” which, as if written by God, contains the most beautiful and enlightening proofs of all theorems. The highest form of praise from Erdös for a proof was, “It’s straight from The Book!” He also said, “You don’t have to believe in God, but you should believe in The Book!”

Do you believe in The Book? I’m not sure I do!

In fact, there is this book by Aigner and Ziegler, “Proofs from The Book”. In it they include the following one-sentence proof by Don Zagier on Fermat’s two square theorem (that a prime congruent to is a sum of two squares):

A One-Sentence Proof That Every Prime p congruent to 1 modulo 4 Is a Sum of Two Squares

                                        D. Zagier

      Department of Mathematics, University of Maryland, College Park, MD 20742

The involution on a finite set S = {(x,y,z) \in N^3 : x^2 +4yz = p } defined by

                      ( x+2z, z, y-x-z )  if   x < y-z
       (x,y,z) ---> { ( 2y-x, y, x-y+z )  if y-z < x < 2y
                      ( x-2y, x-y+z, y )  if   x > 2y

has exactly one fixed point, so |S| is odd and the involution defined by 

       (x,y,z) ---> (x,z,y)

also has a fixed point.

I plucked this off the Web from here; the author of the page prefaces it with a comment:

The following constitutes the essential text of a complete research article; I have
omitted only some comments at the end concerning the history of this type of argument.
The author reproves a famous result.  He builds his proof into a single sentence
as simply a tour-de-force.  In fact, he has left many straightforward steps for
the reader to verify.

1.  As an exercise in critical reading, list all the implicit claims that the
reader must verify in order to accept this argument as a proof.

2.  As an exercise in logic and algebra, supply all the details necessary to
support these claims.   Package all this as a long-winded rewrite of Zagier's
article written so that any high school algebra student could easily read it
with comprehension.

You should expect to expand Zagier's single sentence to a full page or more.

Um, yeah.

My own reaction to this proof: it is surely dazzling in its compression, although one’s first reaction is likely to be “WTF?!?” — what just happened here? The underlying idea is that the number of fixed points of an involution on a finite set (i.e., a function equal to its own inverse) has the same parity as itself; it follows that if has odd parity, then any involution on has at least one fixed point; such a fixed point of the involution on Zagier’s set yields a solution to , whence the theorem. So the bulk of the proof is in showing that has odd parity, by showing that his nontrivial involution has exactly one fixed point.

And I guess you can see, by staring at his casewise-defined involution for a while, that its only fixed point is where . It then remains to check that this really is a well-defined function from to , and it really is an involution. The full verification probably does take up at least a page.

It truly is a jaw-dropping proof. My problem though is that it looks like black magic. I mean, I can construct a line-by-line verification that the proof does what it purports to do, but in a deeper sense I still don’t get it. How Zagier cooked up this involution is a mystery to me, and unless I made a concerted effort to memorize it, it would remain unmemorable to me (that is, unless someone were to reveal the underlying mystery to me — I suspect that that would take a few sentences or more! Can anyone help me?).

What do you think — does it qualify as a Book proof? Me personally, I prefer proofs which are enlightening — arguments that I can really understand, proofs that stick, proofs I can take with me to the grave. Put it this way: if God were to write a proof which consumed an absolute minimum number of bytes in some optimal language, it still wouldn’t be much of a Book proof to me unless I (a limited human) could really understand it, and if it were really better in that sense than its closest competitors.

I don’t think I believe too strongly in the reality of “Book proofs”, or at least I’m skeptical that every theorem can be said to have a Book proof. Every mathematical statement and proof is embodied in some larger context or matrix of ideas, many requiring patient assimilation before a light suddenly flashes on. I tend to believe that’s the rule rather than the exception, and the idea that we should believe in a Book proof for every theorem, possessing a snappy immediacy which cries “Behold!”, is based on a dangerous and even crazy fallacy concerning the nature of mathematics.

[At the same time: we can all agree that Erdös was an absolute genius at finding Book proofs! ]

Boolean algebras, Boolean rings, and baby Stone duality

In this post, I’d like to move from abstract, general considerations of Boolean algebras to more concrete ones, by analyzing what happens in the finite case. A rather thorough analysis can be performed, and we will get our first taste of a simple categorical duality, the finite case of Stone duality which we call “baby Stone duality”.

Since I have just mentioned the “c-word” (categories), I should say that a strong need for some very basic category theory makes itself felt right about now. It is true that Marshall Stone stated his results before the language of categories was invented, but it’s also true (as Stone himself recognized, after categories were invented) that the most concise and compelling and convenient way of stating them is in the language of categories, and it would be crazy to deny ourselves that luxury.

I’ll begin with a relatively elementary but very useful fact discovered by Stone himself — in retrospect, it seems incredible that it was found only after decades of study of Boolean algebras. It says that Boolean algebras are essentially the same things as what are called Boolean rings:

Definition: A Boolean ring is a commutative ring (with identity ) in which every element is idempotent, i.e., satisfies .

Before I explain the equivalence between Boolean algebras and Boolean rings, let me tease out a few consequences of this definition.

Proposition 1: For every element in a Boolean ring, .

Proof: By idempotence, we have . Since , we may additively cancel in the ring to conclude .

This proposition implies that the underlying additive group of a Boolean ring is a vector space over the field consisting of two elements. I won’t go into details about this, only that it follows readily from the proposition if we define a vector space over to be an abelian group together with a ring homomorphism to the ring of abelian group homomorphisms from to itself (where such homomorphisms are “multiplied” by composing them; the idea is that this ring homomorphism takes an element to scalar-multiplication ).

Anyway, the point is that we can now apply some linear algebra to study this -vector space; in particular, a finite Boolean ring is a finite-dimensional vector space over . By choosing a basis, we see that is vector-space isomorphic to where is the dimension. So the cardinality of a finite Boolean ring must be of the form . Hold that thought!

Now, the claim is that Boolean algebras and Boolean rings are essentially the same objects. Let me make this more precise: given a Boolean ring , we may construct a corresponding Boolean algebra structure on the underlying set of , uniquely determined by the stipulation that the multiplication of the Boolean ring match the meet operation of the Boolean algebra. Conversely, given a Boolean algebra , we may construct a corresponding Boolean ring structure on , and this construction is inverse to the previous one.

In one direction, suppose is a Boolean ring. We know from before that a binary operation on a set that is commutative, associative, unital [has a unit or identity] and idempotent — here, the multiplication of — can be identified with the meet operation of a meet-semilattice structure on , uniquely specified by taking its partial order to be defined by: iff . It immediately follows from this definition that the additive identity satisfies for all (is the bottom element), and the multiplicative identity satisfies for all (is the top element).

Notice also that , by idempotence. This leads one to suspect that will be the complement of in the Boolean algebra we are trying to construct; we are partly encouraged in this by noting , i.e., is equal to its putative double negation.

Proposition 2: is order-reversing.

Proof: Looking at the definition of the order, this says that if , then . This is immediate.

So, is an order-reversing map (an order-preserving map ) which is a bijection (since it is its own inverse). We conclude that is a poset isomorphism. Since has meets and , also has meets (and the isomorphism preserves them). But meets in are joins in . Hence has both meets and joins, i.e., is a lattice. More exactly, we are saying that the function takes meets in to joins in ; that is,

or, replacing by and by ,

whence , using the proposition 1 above.

Proposition 3: is the complement of .

Proof: We already saw . Also

using the formula for join we just computed. This completes the proof.

So the lattice is complemented; the only thing left to check is distributivity. Following the definitions, we have . On the other hand, , using idempotence once again. So the distributive law for the lattice is satisfied, and therefore we get a Boolean algebra from a Boolean ring.

Naturally, we want to invert the process: starting with a Boolean algebra structure on a set , construct a corresponding Boolean ring structure on whose multiplication is the meet of the Boolean algebra (and also show the two processes are inverse to one another). One has to construct an appropriate addition operation for the ring. The calculations above indicate that the addition should satisfy , so that if (i.e., if and are disjoint): this gives a partial definition of addition. Continuing this thought, if we express as a disjoint sum of some element and , we then conclude , whence by cancellation. In the case where the Boolean algebra is a power set , this element is the symmetric difference of and . This generalizes: if we define the addition by the symmetric difference formula , then is disjoint from , so that

after a short calculation using the complementation and distributivity axioms. After more work, one shows that is the addition operation for an abelian group, and that multiplication distributes over addition, so that one gets a Boolean ring.

Exercise: Verify this last assertion.

However, the assertion of equivalence between Boolean rings and Boolean algebras has a little more to it: recall for example our earlier result that sup-lattices “are” inf-lattices, or that frames “are” complete Heyting algebras. Those results came with caveats: that while e.g. sup-lattices are extensionally the same as inf-lattices, their morphisms (i.e., structure-preserving maps) are different. That is to say, the category of sup-lattices cannot be considered “the same as” or equivalent to the category of inf-lattices, even if they have the same objects.

Whereas here, in asserting Boolean algebras “are” Boolean rings, we are making the stronger statement that the category of Boolean rings is the same as (is isomorphic to) the category of Boolean algebras. In one direction, given a ring homomorphism between Boolean rings, it is clear that preserves the meet and join of any two elements [since it preserves multiplication and addition] and of course also the complement of any ; therefore is a map of the corresponding Boolean algebras. Conversely, a map of Boolean algebras preserves meet, join, and complementation (or negation), and therefore preserves the product and sum in the corresponding Boolean ring. In short, the operations of Boolean rings and Boolean algebras are equationally interdefinable (in the official parlance, they are simply different ways of presenting of the same underlying Lawvere algebraic theory). In summary,

Theorem 1: The above processes define functors , , which are mutually inverse, between the category of Boolean rings and the category of Boolean algebras.

• Remark: I am taking some liberties here in assuming that the reader is already familiar with, or is willing to read up on, the basic notion of category, and of functor (= structure-preserving map between categories, preserving identity morphisms and composites of morphisms). I will be introducing other categorical concepts piece by piece as the need arises, in a sort of apprentice-like fashion.

Let us put this theorem to work. We have already observed that a finite Boolean ring (or Boolean algebra) has cardinality — the same as the cardinality of the power set Boolean algebra if has cardinality . The suspicion arises that all finite Boolean algebras arise in just this way: as power sets of finite sets. That is indeed a theorem: every finite Boolean algebra is naturally isomorphic to one of the form ; one of our tasks is to describe in terms of in a “natural” (or rather, functorial) way. From the Boolean ring perspective, is a basis of the underlying -vector space of ; to pin it down exactly, we use the full ring structure.

is naturally a basis of ; more precisely, under the embedding defined by , every subset is uniquely a disjoint sum of finitely many elements of : where : naturally, iff . For each , we can treat the coefficient as a function of valued in . Let denote the set of functions ; this becomes a Boolean ring under the obvious pointwise definitions and . The function which takes to the coefficient function is a Boolean ring map which is one-to-one and onto, i.e., is a Boolean ring isomorphism. (Exercise: verify this fact.)

Or, we can turn this around: for each , we get a Boolean ring map which takes to . Let denote the set of Boolean ring maps .

Proposition 4: For a finite set , the function that sends to is a bijection (in other words, an isomorphism).

Proof: We must show that for every Boolean ring map , there exists a unique such that , i.e., such that for all . So let be given, and let be the intersection (or Boolean ring product) of all for which . Then

.

I claim that must be a singleton for some (evidently unique) . For , forcing for some . But then according to how was defined, and so . To finish, I now claim for all . But iff iff iff . This completes the proof.

This proposition is a vital clue, for if is to be isomorphic to a power set (equivalently, to ), the proposition says that the in question can be retrieved reciprocally (up to isomorphism) as .

With this in mind, our first claim is that there is a canonical Boolean ring homomorphism

which sends to the function which maps to (i.e., evaluates at ). That this is a Boolean ring map is almost a tautology; for instance, that it preserves addition amounts to the claim that for all . But by definition, this is the equation , which holds since is a Boolean ring map. Preservation of multiplication is proved in exactly the same manner.

Theorem 2: If is a finite Boolean ring, then the Boolean ring map

is an isomorphism. (So, there is a natural isomorphism .)

Proof: First we prove injectivity: suppose is nonzero. Then , so the ideal is a proper ideal. Let be a maximal proper ideal containing , so that is both a field and a Boolean ring. Then (otherwise any element not equal to would be a zero divisor on account of ). The evident composite

yields a homomorphism for which , so . Therefore is nonzero, as desired.

Now we prove surjectivity. A function is determined by the set of elements mapping to under , and each such homomorphism , being surjective, is uniquely determined by its kernel, which is a maximal ideal. Let be the intersection of these maximal ideals; it is an ideal. Notice that an ideal is closed under joins in the Boolean algebra, since if belong to , then so does . Let be the join of the finitely many elements of ; notice (actually, this proves that every ideal of a finite Boolean ring is principal). In fact, writing for the unique element such that , we have

(certainly for all such , since , but also belongs to the intersection of these kernels and hence to , whence ).

Now let ; I claim that , proving surjectivity. We need to show for all . In one direction, we already know from the above that if , then belongs to the kernel of , so , whence .

For the other direction, suppose , or that . Now the kernel of is principal, say for some . We have , so

from which it follows that for some . But then is a proper ideal containing the maximal ideals and ; by maximality it follows that . Since and have the same kernels, they are equal. And therefore . We have now proven both directions of the statement ( if and only if ), and the proof is now complete.

• Remark: In proving both injectivity and surjectivity, we had in each case to pass back and forth between certain elements and their negations, in order to take advantage of some ring theory (kernels, principal ideals, etc.). In the usual treatments of Boolean algebra theory, one circumvents this passage back-and-forth by introducing the notion of a filter of a Boolean algebra, dual to the notion of ideal. Thus, whereas an ideal is a subset closed under joins and such that for , a filter is (by definition) a subset closed under meets and such that whenever (this second condition is equivalent to upward-closure: and implies ). There are also notions of principal filter and maximal filter, or ultrafilter as it is usually called. Notice that if is an ideal, then the set of negations is a filter, by the De Morgan laws, and vice-versa. So via negation, there is a bijective correspondence between ideals and filters, and between maximal ideals and ultrafilters. Also, if is a Boolean algebra map, then the inverse image is a filter, just as the inverse image is an ideal. Anyway, the point is that had we already had the language of filters, the proof of theorem 2 could have been written entirely in that language by straightforward dualization (and would have saved us a little time by not going back and forth with negation). In the sequel we will feel free to use the language of filters, when desired.

For those who know some category theory: what is really going on here is that we have a power set functor

(taking a function between finite sets to the inverse image map , which is a map between finite Boolean algebras) and a functor

which we could replace by its opposite , and the canonical maps of proposition 4 and theorem 2,

are components (at and ) of the counit and unit for an adjunction . The actual statements of proposition 4 and theorem 2 imply that the counit and unit are natural isomorphisms, and therefore we have defined an adjoint equivalence between the categories and . This is the proper categorical statement of Stone duality in the finite case, or what we are calling “baby Stone duality”. I will make some time soon to explain what these terms mean.

Milk and Tea puzzle

[Update: Look for another (slicker) solution I found after coming up with the first one.]

My friend, John, asked me today if I had a solution to the following (well-known) problem which may be found, among other sources, in Chapter Zero (!) of the very famous book, Mathematical Circles (Russian Experience).

Three tablespoons of milk from a glass of milk are poured into a glass of tea, and the liquid is thoroughly mixed. Then three tablespoons of this mixture are poured back into the glass of milk. Which is greater now: the percentage of milk in the tea or the percentage of tea in the milk?

Note that there is nothing special about transferring three tablespoons of milk and/or tea from one glass to another – the problem doesn’t really change if we transfer one tablespoon of milk/tea instead, and that there is nothing special about transferring “volumes” – we could instead keep a count of, say, the number of molecules transferred.  We may, therefore, pose ourselves the following analogous “discrete” problem whose solution provides more “insight” into what’s really going on.

Jar W contains white objects (and no other objects) and jar B contains black objects (and no other objects.) We transfer objects from jar W to jar B. We then thoroughly mix -  in fact, we don’t have to – the contents of jar B, following which we transfer objects, this time, from jar B to jar W. Which is greater now: the percentage of black objects in jar W or the percentage of white objects in jar B?

Solution 1: Let us keep track of the number of black and white objects in both the jars before and after the transfers of objects from one jar to another. So, initially, in jar W,

# of white objects = , and # of black objects = .

Also, in jar B,

# of white objects = , and # of black objects = .

Now, we transfer objects from jar W to jar B. So, in jar W,

# of white objects = , and # of black objects = .

Also, in jar B,

# of white objects = , and # of black objects = .

Finally, we transfer objects from jar B to jar W. Let the number of white objects out of those objects be . Then, the number of black objects transferred equals . Therefore, now, in jar W,

# of white objects = , and # of black objects = .

Also, in jar B,

# of white objects = , and # of black objects = .

From here, it is easy to see that the percentage of black objects in jar W is the same as the percentage of white objects in jar B! And, we are done.

Solution 2: (I think this is a slicker one, and I found it after pondering a little over the first solution I wrote above!) This one uses the idea of invariants, and there are, in fact, two of ‘em in this problem! Note that at any given time,

# of white objects = # of black objects = .

The above is the first invariant.

Also, note that after we transfer objects from jar W to jar B and then objects from jar B to jar W, the number of objects in each jar is also . This is the second invariant. And, now the problem is almost solved!

Suppose, after we do the transfers of objects from jar W to jar B and then from jar B to jar W, the # of white objects in jar W is . Then it is easy to see that the # of black objects in jar W is (using the second invariant mentioned above.) Similarly, using the first invariant, the # of white objects in jar B = . Therefore, using the second invariant again, the # of black objects in jar B = . And, from this the conclusion immediately follows!