BR Maths Corner-1

[Amber G.]

IIRC, she is listed as Gauss's student in Mathematics Genealogy DB. Are you sure the PhD is honorary?

Added later
Never mind - you are right - this is what the DB says -
Dissertation: Honorary degree awarded by Gottingen under pressure from Gauss

Thanks. As I said before, Gauss, even though he corresponded with her for years yet did not know her true identity till French general informed him!! .. Gauss writes:

How can I describe my astonishment and admiration on seeing my esteemed correspondent M leBlanc metamorphosed into this celebrated person. . . when a woman, because of her sex, our customs and prejudices, encounters infinitely more obstacles than men in familiarising herself with number theory's knotty problems, yet overcomes these fetters and penetrates that which is most hidden, she doubtless has the most noble courage, extraordinary talent, and superior genius

Here is one place to read about her:
http://fermatslasttheorem.blogspot.com/ ... rmain.html

[Vayutuvan]

AmberG ji, so how long have had been training kids for IMO?

"Leviculus" rhymes with calculus - might have been the impetus for the April fools joke.

[ArmenT]

The Leviculus Conjuncture for those who do not know is:

The average of any two consecutive odd primes is always a composite number

.

( For example, if you take two consecutive odd primes, say 13 and 17, the average is 15, and sure enough 15 is composite (5 times 3))

The proof, once you know it, is not very complicated. Hopefully some one here can prove or reproduce the proof.

After you finally fessed up that it was a joke, I decided to go ahead and try to prove the theorem anyway (I'm kinda stubborn like that, it is a fault of mine).

1. Let M and N be two consecutive ODD prime numbers.
2. Let P be the average between M and N. We know that M + N is even, since both M and N are odd. Therefore (M+N) is evenly divisible by 2 and the value of P is between M and N.
3. It doesn't matter if P is even or odd. P cannot be prime because this will contradict statement 1 (i.e. M and N are two consecutive odd primes -- if (P lies between M and N) AND (P is prime), then M and N are not consecutive odd primes). Therefore P has to be a composite number.

Read about Sophie Germain in the book about Fermat's Last Theorem by Simon Singh. However, since I'm not exactly a sophisticated mathematical mind, but more of a low-brow pop-culture savant, I'd like to once again dedicate this solution, not to a Lemma, but to a Lemmy, for providing me so many years of ear-splitting pleasure.

[Amber G.]

^^^ Yes, of course. The point, as you said, that some time people miss the fact that by the very definition of consecutive prime numbers, any number between them is not a prime...
Thanks for introducing Lemmy

Matrimc - I was never (at least officially or formally) a coach/leader for any IMO team. (I have worked with some of these kids at different levels and at some other events)

Added later: ArmenT,
I think you (and others) may enjoy:

Sophie Germainís grand plan to prove Fermatís Last Theorem:

http://www.math.nmsu.edu/~davidp/germain.pdf
Germain's work on Fermat's last theorem is nicely explained here, as well as a nice biography of her.

[Vayutuvan]

For your weekend pleasure I have the following problems. They are quite popular and some of you might have seen them (or even they were posted here? If so, will delete).

Problem 1: This was presented in a paper on mathematical education of the school children in one of the Indian Mathematical Congress meetings is what I was told. The proof uses a trick - either one would get it or not. But the important thing is that it uses a particular type of a proof strategy which has wide applicability. Here is the problem.

There is a biscuit factory which has 100 packing machine. Each machine is supposed to pack exactly 100 g of biscuits. The packets come out of each machine on to a conveyor belt and get dumped into one big box from which they are moved into trucks and sent out. One day the QC people find out that one of the machines has gone bad and is packing is 101 g. They do not want to stop all the machines (because stop-restart costs a lot) but want to find out very quickly which machine is packing more so that they can stop only that machine and restart it. One of them gets a bright idea. She uses a large digital weighing machine of the type where there is a pan and the digital machine shows how much weight is put into the pan. She finds out the bad machine by weighing and taking only one weight reading from the machine. How?

2. Tiling problem - tomorrow...

[ArmenT]

^^^^
Piece of cake.
Take 1 biscuit pack from 1st machine, 2 from 2nd machine, 3 from the 3rd machine, 4 from the 4th machine .... N from the Nth machine and weigh them all together. The number of grams that the weight is off the expected weight will tell you which machine is off.

AmberG: Thanks much for the link, will read up on it. By the way, I had the pleasure of meeting Lemmy in a bar a couple of years ago, when he happened to come and sit in the seat next to me. Turns out he knew the friend I was meeting there, who was also a frequent customer. The man is humble as can be and one of the nicest rock stars around. We shared a couple of tall beers and I took a picture with him.

[Vayutuvan]

Yes, the proof given by ArmenT. Nice and elegant I think. It is similar to Cantor's diagonalization argument, but applied to a finite set.

A Tiling Problem:

We are given an 8x8 standard chess board with two diagonally opposite corner squares snipped out. Let's call it a defective chess board (DCB). We are also given 31 all same dominoes, each rectangular in shape that can cover two side-by-side squares of the DCB. Is it possible to tile the DCB with 31 of these dominoes?

[Amber G.]

^^ Hint: Do think of this as a chess board with black and white squares.
(with two same color squares missing..)

[ArmenT]

I know the answer to the tiling problem as well (because I read it in a book by Simon Singh on Fermat's Last Theorem -- same book I alluded to above). I'll leave it to someone else to try and answer that one, if not I'll give it a shot in a few days.

[Vayutuvan]

The tiling problem is in CL Liu's book. Another hint - if you read AmberG's hint then effectively the solution - is that it cannot be done.

An extension to the tiling problem which I saw in a blog somewhere on the netz. Still working out the solution - What if two squares are removed from anywhere in the board? There are two cases

case1. two squares of the same color (well, this is essentially the hint AmberG gave above)
case2. two squares of opposite colors removed. My guess is that there is a solution for all boards of size 2n x 2n. trying to work out.

By the way, the graph of my original tiling problem is called a factor graph. There are lots problems in CL Liu's book on factor graphs.

Is generalizations to higher dimensions possible? For my original problem, the answer is yes. In other words, if you consider an 2n x 2n x ...k... x 2n hypercube (k-cube) where each cell is alternately black and white (we can show that this coloring is possible, which I will give in another series of problems afterwards), and you are given (2^k n^k - 1) k-parallelpipeds, same proof holds trivially.

For case2 above?

Small correction number of k-parallel pipers is 2^{k-1} n^k -1

[Vayutuvan]

There is a small mistake in the problem formulation for k-cube. Leaving it as an exercise to correct it.

[Amber G.]

Few comments about the tiling problem (Thanks for this fun problem) :

1, Crossing the t's and dotting the i's (about the domino problem - as already pointed out by me and others) - Thinking of the board as 32 black and 32 white squares, and each domino as covering 1 black and 1 white square, it is not possible to cover the board where two diagonally opposite corners (Missing two corners have to be of the same color, thus the remaining board will unequal number of black vs white squares - and, of course, 31 dominoes, no matter how one arranges them will cover 31 black and 31 white squares).

2. Can some one calculate how many different ways the board can be covered ...
(Answer is not that easy of n x n square - Computer can be used to test the answer)
( The answer for 8x8 board is 258584046368)

3. Simpler problem from above, consider just a small strip 2 x 8 of the board above, how many ways can one arrange (8 dominoes) to cover the strip? (How about the case of 2 x n )

(for n =2, there are only 2 ways - both horizontal or both vertical and for 2x3 strip the answer will be 3 - all horizontal, bottom two vertical or top two vertical etc)

If you do not know the solution of above, it will be fun to work it out,, (Again computer can help to test the answer)

4. For problem posted by Matrimc, unless I am not following the problem, seems almost trivial.. Am I correct? (If one can do it for 2 dim, (2nx2n board) 3, dim or more is trivial)

[Amber G.]

Just for fun, if some one is interested, here is some what harder (or may be very simple if you hit the right idea) problem (from a Russian Math competition, I was told)

You have a 6x6 board (instead of 8x8) and you want to cover it entirely. (with 18 dominoes (of the 2 x 1 size) as described above)

Prove that you can always find a straight line which divides the board into two (not necessarily equal) parts, such that no domino is cut by that line.

[Vayutuvan]

4. For problem posted by Matrimc, unless I am not following the problem, seems almost trivial.. Am I correct? (If one can do it for 2 dim, (2nx2n board) 3, dim or more is trivial)

Yes it is trivial only for even k. That is the mistake I made in the formulation.

For even k, one cannot tile because the two removed small k-cubes are of the same color. But for odd dimensions, it should be tilable. For one dimension (a line) a DCB can be tiled, of course.

Crossing the ts and dotting the i's

To see the color of the removed small k-cubes is same for even dimension, fix one of the corner nodes as the origin and appropriate handedness so that the DCB lies in the positive orthant. Sstarts at the origin and walk along the edge in the direction of basis vectors i in order and record the how many color switches are there. Say for 3 dimensions and starting color 0 when you come to the end walking in x direction the color switches to 1 and when you walk along y at the end it gets switched to 0 and after walking along z one ends up on color 1. If the starting color is 0, by induction (or mod 2 calculation on the path length), one can easily show that for even dimensions the ending color is 0 and for odd dimensions the ending color is 1.

[Vayutuvan]

You have a 6x6 board (instead of 8x8) and you want to cover it entirely. (with 18 dominoes (of the 2 x 1 size) as described above)

Prove that you can always find a straight line which divides the board into two (not necessarily equal) parts, such that no domino is cut by that line.

Either I do not understand the problem or you are still in April 1st mood.

[Vayutuvan]

... 31 dominoes, no matter how one arranges them will cover 31 black and 31 white squares).

small correction - shouldn't that be 32 [black|white] squares and 30 [white|black] squares?

[Amber G.]

You have a 6x6 board (instead of 8x8) and you want to cover it entirely. (with 18 dominoes (of the 2 x 1 size) as described above)

Prove that you can always find a straight line which divides the board into two (not necessarily equal) parts, such that no domino is cut by that line.

Either I do not understand the problem or you are still in April 1st mood.

No, it is a interesting and serios problem ...

Let me take a case of 8x8 board, where all lines except one, shown in red do cut some dominoes..

(In 6x6 case, no matter how you tile the board, one can always find a line which does not cut a domino - this is what problem asks us to prove) ..



(BTW, in 8x8 case, one can find a way - not shown in the above picturem but it can be a nice problem to try - to arrange the tiles in such a way that every line will cut at least one domino)

[Amber G.]

... 31 dominoes, no matter how one arranges them will cover 31 black and 31 white squares).

small correction - shouldn't that be 32 [black|white] squares and 30 [white|black] squares?

May be we are saying the same thing but I believe what is meant by me was ...

31 dominoes will cover 31 black and 31 white squares, while the board (which needs to be covered with missing squares) has "32 [black|white] squares and 30 [white|black] squares" so this can not be done...

[Vayutuvan]

I misunderstood. Just to make sure that I understand correctly, let me state the problem as I understand it.

Every 2x1 domino tiling of a 6x6 checkered board admits a straight line that separates the board into two parts (not necessarily equal) without intersecting any domino.

[Amber G.]

Yes (above is correct)

I want to see if brf teamwork can solve these two problems..So one can put the solutions or give hints. First one (to find # of ways to tile 2xn strip with dominoes) is fairly well known yet the result is beautiful. (One can easily count cases for small number of n to see the pattern)

I guerss, the 6x6 problem may be a little harder if one does not think out of the box.(Hint: Right idea can make the problem fairly easy). Feel free to ask other mathematicians for ideas or hints.. It may be interesting in other ways - A computer program-proof (# of ways are still quite small and are easy to count with a computer) to try out.. .

[Vayutuvan]

AmberG what software did you use to draw the figure? Thanks.
For the 6x6 problem, I am thinking in terms of unavoidable configurations. Let me draw some figures and see if I get somewhere.

[Vayutuvan]

AmberG ji

My other thought is use partition function for the number 36. Is that possible? Thanks

[Vayutuvan]

AmberG ji

Answer for 2xn is n'th Fibonocci number.

PS: I did not use a computer for that.

[Amber G.]

what software did you use to draw the figure?

Cut and paste (and a little editing) from Wikl ... Check out Gomorys Theorem.

BTW, I first heard of the problem, and its creative solution (Tiling when two corner pieces are missing etc) in a book by my most favorite G. Gamow's.. in around 1960. (I recommend his "one two three infinity" -)

For 2xn strip, Fibonacci number is the correct answer.
(For example see Tiling problem

You may enjoy these two from Wolfram
Placing dominoes etc ..
Fibonacci Numbers Count Domino Tilings

[abhishek_sharma]

How much math you need to do research

[Amber G.]

The tiling problem is in CL Liu's book. Another hint - if you read AmberG's hint then effectively the solution - is that it cannot be done.

An extension to the tiling problem which I saw in a blog somewhere on the netz. Still working out the solution - What if two squares are removed from anywhere in the board? There are two cases

case1. two squares of the same color (well, this is essentially the hint AmberG gave above)
case2. two squares of opposite colors removed. My guess is that there is a solution for all boards of size 2n x 2n. trying to work out.

I can think of a very simple proof of above. My father showed me how to cut a square paper and make it a big mala (garland - or in mathematical language a closed curve) -- whose length was much much bigger than the perimeter of the square.!

I am giving a picture below for 8x8 square, but any m x 2n will do to draw a simple close curve.

Much easier is to actually cut a piece of paper, along the red line, and see what I mean.

(Yellow line is the mala)





Rest is easy!

Just lay the dominoes (length-wise on the mala).. A moment's though will convince you that one can easily fill the mala with dominoes satisfying the problem conditions.. (Shift the dominoes to leave two holes where-ever is required, which one can do as long as the missing squares are of different color) .! (Just refold the mala back to chess board)

QED

[Vayutuvan]

AmberG ji, your figure did not appear. It is appearing as a broken link in my browser (Chrome on Linux).

I was thinking in two dimensions only and thinking of doing several different case. Probably eventually would have hit upon the mAlA (transform into a long strip). Thanks.

By the way the 2 x n tiling problem, there is a one off (once you apply the two base cases of the recursion). The correct answer is $f_{n+1}$ where $f_i$ is the i'th Fibonocci number.

Here are the details

T(n) = T(n-1) + T(n-2)
T(1) = 1 and T(2) = 2

First term comes from laying one domino in the first row covering the entire row. We are left with a 2x (n-1) board.
Second term comes from laying two dominoes vertically side by side (first one covers first two rows of the first column and the second one covers the firs two rows of the second column) thus covering the fist two rows entirely. This leaves a 2X(n-2) board. And for the base cases, T(1) is trivial. T(2) each of the two rows is covered by a domino, and the second way is each of the two columns is covered by a domino.

With that in hand, we can now count (correction after AmberG ji's observation and my realizing that this is only a lower bound - matrimc) give a rough lower bound on the number of ways a 2m x n checker board can be tiled. The answer is $f_{n+1}^m$. Please verify.

[Amber G.]

The link above is https://dl.dropboxusercontent.com/u/181 ... ftemp2.jpg
(Seems fine from my chrome)... may be you tried while I was updating it ..try it now..

Extending the the closed curve in 3 (or more) dimension is quite valid.. so the same proof will hold.

Yes, 2xn case gives Fibonacci !! , but for a general (m x n) case, the explicit formulas are quite complex..

For 8x8 chess board the number is 12988816 !

For square (m=n = even number), the numbers go as
1, 2, 36, 6728, 12988816 etc .. (see http://oeis.org/A004003)

(Interestingly these problems have been quite interesting in physics..or nuclear spectra .. lattices or discrete gases)

[Vayutuvan]

Yes, I realized my mistake now. What I give above could work as a rough lower bound though which can be improved. I am correcting my above post.

I am still unable to see the figure at dropbox. It is coming back with

This webpage is not available
...
Error 109 (net::ERR_ADDRESS_UNREACHABLE): Unable to reach the server.

Do you have to make it public or some such?

[Amber G.]

...
Error 109 (net::ERR_ADDRESS_UNREACHABLE): Unable to reach the server.

Do you still get that error ? Can you try using other browser (or go in new incognito window in chrome)?
Anyone else having that problem?

[Vayutuvan]

Now it is fine. I can see it. Nice pattern.

[ArmenT]

A Tiling Problem:

We are given an 8x8 standard chess board with two diagonally opposite corner squares snipped out. Let's call it a defective chess board (DCB). We are also given 31 all same dominoes, each rectangular in shape that can cover two side-by-side squares of the DCB. Is it possible to tile the DCB with 31 of these dominoes?

The way that the argument is presented in Simon Singh's book "Fermat's Enigma: The Epic Quest to Solve the World's Greatest Mathematical Problem.", he uses it to demonstrate the concept of invariants and uses this specific problem as an example.

His version of the proof is that an invariant property of the board is that a domino must always cover a white square and a black square. Therefore if you have a defective board with 32 black square and 30 white squares, there will be some place where two black squares will need to be covered. Since the invariant property of the board is that a domino can only cover a white square and a black square, therefore, it is impossible for the board to be covered with 31 dominoes. He goes on to state that mathematicians try to find invariant properties to solve certain classes of problems.

[Vayutuvan]

ArmenT ji
Thats it. For four color problem I tried reading Singhs book. It was so light on detail that it ended up not giving any insight into how the problem was solved. So I got turned off and did not read FLT book. I got Ribenboim but it is hard going and other stuff got stacked on top. For four color problem I highly recommend "Four Colors Suffice" by Robin Wilson.

[Vayutuvan]

The link above is https://dl.dropboxusercontent.com/u/181 ... ftemp2.jpg
(Seems fine from my chrome)... may be you tried while I was updating it ..try it now..

AmberG ji,

By the way a closed curve is not required. A simpler pattern is to cut into a spiral going from outer edge inside which gives a line. Once the line is tiled, two (opposing color) missing squares are given, one can push the segment forward or backward. If this explanation is not enough, I will post a picture. The fist and last squares is a special case that can be handled by assuming that they are next to each other through an extra dimension. This method is easier to visualize for 2+ dimensions.

[Amber G.]

The link above is https://dl.dropboxusercontent.com/u/181 ... ftemp2.jpg
(Seems fine from my chrome)... may be you tried while I was updating it ..try it now..

AmberG ji,

By the way a closed curve is not required. A simpler pattern is to cut into a spiral going from outer edge inside which gives a line. Once the line is tiled, two (opposing color) missing squares are given, one can push the segment forward or backward....

The reason, closed curve may not always be like a line with two ends... Think of a board with 1xn (n even) where two next-to-end pieces missing. (For example, "1234" You can not fill in with dominoes if the missing parts are 2 and 3) ...

(you are okay, if one can make the end pieces missing are at the end of the line (or even squares away from the end point..that difficulty goes away if you have closed curve, since it has no end, any two pieces with opposite parity will do - as long as total # squares in the closed curve is also even)


Armen T - Thanks for mentioning Singh's book, I have not read it, will do when I get a chance.
Invariant concept is very powerful in Physics too.. Many difficult problems, (including everyday problems) can be solved this way....The trick is to find the right invariant property..

For example, if our dominoes are 4x1 (instead of 2x1) can one cover a 6x10 board with them? (The board is to be fully covered)

[Vayutuvan]

Yes sir, there is no way to fix your counter example above for non-closed line. I tried fixing but ending up with your original patter onlee. Only thing is I am having difficulties in visualizing for 3D (leave alone > 3D). I have to close my eyes and meditate for sometime, I guess.

[Amber G.]

Today google doodle celebrates Euler's Birth day..



e^(i*pi) = -1
(One of the most beautiful formula ever given)

[Vayutuvan]

Konigsberg Bridge problem is also shown along with Euler's formula of invariance for graphs which makes showing 6-color theorem quite easy.

[Vayutuvan]

AmberG ji (sorry if you are not a Sir, I should have used Sir/Madam in a previous post)

I found a simpler pattern for the closed curve than the one you have given. Will draw and post. Also there is a connection to Matching on a bipartite graph.

Sri Kumar ji, I hope you are looking at the thread. Watch the space because I would like to link the P ?= NP explanation with this problem.

[SaiK]

math guru jis, please enlighten to some more aam explanation for moorkh me on the beautiful euler's formula, especially where it applies/example. tia