The ARCTIC CIRCLE THEOREM or Why do physicists play dominoes?
Vložit
- čas přidán 31. 05. 2024
- I only stumbled across the amazing arctic circle theorem a couple of months ago while preparing the video on Euler's pentagonal theorem. A perfect topic for a Christmas video.
Before I forget, the winner of the lucky draw announced in my last video is Zachary Kaplan. He wins a copy of my book Q.E.D. Beauty in mathematical proof.
00:00 Intro
00:35 Chapter 1: mutilated chessboards
07:23 Chapter 2: Monster formula
15:12 Chapter 3: Aztec gold
20:07 Chapter 4: Square dance
30:41 Chapter 5: Ice
34:35 Chapter 6: Hexagon
38:25 Credits
40:46 Mini masterclass
In response to my challenge here are some nice implementations of the dance:
Dmytro Fedoriaka: fedimser.github.io/adt/adt.html (special feature: also calculates pi based on random tilings. First program contributed.)
Viktor Chlumský • Aztec Diamond Procedur... (no program but a VERY beautiful animation made with the software Shadron by Victor)
Cannot fit any more links in this description because of the character limit. For lots of other amazing implementations check out the list in my comment pinned to the top of the comment section of the video.
For the most accessible exposition of iterated shuffling that I am aware of have a look at the relevant chapter in the book "Integer partitions" by Andrews and Eriksson. They also have a nice set of exercises that walk you through proofs for the properties of iterated shuffling that I mention in this video.
I used Dan Romik's old Mac program "ASM Simulator" to produce the movie of the random tilings of growing Aztec diamond boards www.math.ucdavis.edu/~romik/s... Sadly this program does not work on modern Macs.
The arctic heart at the end of the video is a "chistmasized" version of an image from the article "What is a Dimer" by Richard Kenyon and Andrei Okounkov www.ams.org/notices/200503/wh... Thank you for letting me use this image.
Around the same time that Kasteleyn published the paper I showed in the video, the physicists Temperley and Fisher published similar results, Dimer problem in statistical mechanics-an exact result, Philosophical Magazine, 6:68, (1961) 1061-1063. The way Kasteleyn as well as Temperley and Fisher calculated the numbers of tilings of boards with square tiles was a bit more complicated than the nice refinement that I show in the video which is due to Jerome K. Percus, One more technique for the dimer problem. J. Mathematical Phys., 10:1881-1888, 1969.
Some great articles and websites to check out:
A very accessible introduction to domino and other tilings by Federico Adila and Richard Stanley www.claymath.org/library/senio...
An accessible article about tilings with rectangles by my colleague Norm Do at Monash Uni. In particular, it's got some more good stuff about the maths of fault lines in tilings that I only hinted at in the video:
users.monash.edu/~normd/docume...
A nice article about Kasteleyn's method by James Propp. Includes a proof of the crazy formula arxiv.org/abs/1405.2615
A fantastic survey article about enumeration of tilings by James Propp. This one's got everything imaginable domino and otherwise. Also the bibliography at the end is very comprehensive faculty.uml.edu/jpropp/eot.pdf
An introduction to the dimer model by Richard Kenyon
arxiv.org/abs/math/0310326
Alternating sign matrices and domino tilings by Noam Elkies, Greg Kuperberg, Michael Larsen, James Propp arxiv.org/abs/math/9201305
Random Domino Tilings and the Arctic Circle Theorem by William Jockusch, James Propp, and Peter Shor arxiv.org/abs/math/9801068
A website by Alexei Borodin full of amazing 3d representations of domino tilings. A must-see math.mit.edu/~borodin/aztec.html
James Propp's name pops up a couple of times throughout this video and in this description. He's one of the mathematicians who discovered all the beautiful arctic mathematics that I am talking about in this video and helped me get my facts straight. Check out his blog mathenchant.org and in particular in this post he talks a little bit about the discovery of the arctic circle phenomenon mathenchant.wordpress.com/201...
As usual the music in the video is from the free CZcams audio library: Night Snow by Asher Fulero and Fresh fallen snow by Chris Haugen.
Today's t-shirts I got ages ago. Don't think they still sell those exact same ones. Having said that just google "HO cubed t-shirt" and "i squared keep it real t-shirt" ... :)
Jokes:
1. Aztec diamond = Crytek logo; 2. no. tilings of Arctic diamond: 2^(-1/12). 3. ℝeal mathematical magic, 4. (HO)³ : joke for mathematicians (HO)₃ : joke for chemists
Bug:
Here one of the tiles magically disappears (damn :( tinyurl.com/ya6mqmhh
Nice insight:
If all holes in a mutilated board can be tiled with dominoes the determinant will work. Why is that?
Merry Christmas,
burkard
(HO)³ : A Christmas joke for mathematicians
(HO)₃ : A Christmas joke for chemists
:)
Brilliant
the chemist version of the joke is very "basic"..pun intended.
A joke for linguists: Carissimus Dei.
Hydroxide, hydroxide, hydroxide!
When he said “what a crazy, crazy year right?” I’ve been conditioned to expect him to say “Wrong!” 😂
Hahahaha yeah
Hahaa
The crazy year means Corona Virus 😭😭😭
"It gets even crazier!"
+++
20:00 Number of tilings of the Arctic Circle: 2^(-1/12). Got it. 😏
:)
#(A(n)) = 2^(n(n + 1)/2), therefore
#(A(|ℕ|)) =
= 2^(|ℕ|(|ℕ|+1)/2) =
= 2^(|ℕ|) = |ℝ|
which is about 0.94
Wait; I got stuck at A2, I see 10 possible tilings, not 8
Riemann with his lame continuations,
Mathologer is gonna need his medications,
There’ll be trouble in town tonight!
You call this steamed ζ(-1) despite the fact that it’s clearly grilled?
I feel like I watch this guy 20% for his amazing math demonstrations and 80% for him laughing at his own jokes
same here, it's adorable and endearing. I think that's one thing about the best teachers that I try to emulate, is they all unironically embrace their own cringe juuuust enough to help their audience push past discomfort and really get engaged.
Merry Christmas!
6:11 - You could pick the two blacks in the top left corner. It would isolate the corner green square, so not every combination of 4 squares removed is tileable.
10:13 - say m = 2p-1 and n=2q-1. The denominators in the cosines will be 2p and 2q. Carrying out the product, when j=p and m=q, we will have a term (4cos²(π/2)+4cos²(π/2)), which is 0, cancelling out everything else
13:50 - Lets say T(n) is the number of ways to tile a 2xn rectangle. First two are obviously T(1)=1 and T(2)=2. For the nth one, lets look at it from left to right. We can start by placing a tile vertically, which will isolate a 2x(n-1) rect. - so T(n-1) ways of doing it in this case. If we instead place a tile horizontally on the top, we will be forced to place another one directly below, so we don't isolate the bottom left square, this then isolates a 2x(n-2) - so T(n-2) ways of doing it in this case.
----
We have T(n) = T(n-1) + T(n-2). Since 1 and 2 are fibonacci numbers, the sequence will keep spitting out fibonacci numbers
14:33 - It's 666. I did it by considering all possible ways the center square can be filled and carrying out the possibilities. It was also helpful to see that the 2x3 rectangles at the edges are always tiled independently. I was determined to do all the homework in this video, but hell no I wont calculate that determinant, sorry
30:12 - I'll leave this one in the back of my mind, but for now I'm not a real math master. I'm also not a programmer, but this feels like somehting fun to program
37:28 - Just look at the cube stack straight from one of the sides, all you'll see is an nxn wall, either blue, yellow, or gray
Very, very good, more than full marks :)
The determinate is also 666 actually. Yes I calculated it.
I just realized: for the hexagon, if you turned it into a 3D broken cube, then looked at it from any of the open faces (assuming you're looking directly at the face from a single point), you would see a complete square of one color. This would be the same from all three open sides, and there would be no hidden faces. Thus, the sides being equal, there will always be an equal number of each color domino
I did it like this: with no cubes you have the same number. Everytime you place a new cube it must touch three sides (which get covered) and adds three of its own (aka, all numbers (of each color) stay the same). It is the same argument as yours, of course.
Yes, that is a nice property - and easy to understand from a spatial visualization point of view.
This also means that there is a predetermined amound of a given color in each "column", going 1, 2, 3, 4, ..., 4, 3, 2, 1 (but this works only in one way for each color if I'm not mistaken)
9:45 12 million "and change"?? I'll take your change then, thank you!
:)
more like 13 million minus change
@@SunroseStudios wouldn’t it be 13E6-(1-change).
I find really wholesome this man's dedication to speak and explain so passionly for 50+ minutes straight. As a phisicist that I am, I love how matematicians like this one continiously inspire us all everytime they can. Keep on the good work, stay amazed and happy holidays!
I love his videos, but he doesn't speak "for 50+ minutes straight". There are many cuts in the video, with unfilmed time between, and no doubt a number of bloopers we never see.
@@jursamaj well, he DOES talk for 50+ minutes straight as a uni lecturer
First challenge: The chessboard cannot always be tiled after removing 2 black & 2 green. Suppose we remove the two black squares adjacent to the upper-left corner and the two green squares adjacent to the lower-left corner. Then the left corner squares are no longer adjacent to any other squares, so the board cannot be tiled.
EDIT:
Second challenge: if m and n are odd, then ⌈m/2⌉ = (m+1)/2 and ⌈n/2⌉ = (n+1)/2. Now the j=(m+1)/2, k=(n+1)/2 term of the product is 4cos²(π/2) + 4cos²(π/2) = 0, so the product is 0. Moreover, if m is not odd, then 0 ≤ j < (m+1)/2 in all terms of the product, hence 0 ≤ jπ/(m+1) < π/2 in all terms, so cos²(jπ/(m+1)) > 0 in all terms, so each term of the product is nonzero. This means the formula gives a nonzero answer whenever m is even -- symmetrically, the answer is nonzero whenever n is even. Thus, the formula returns 0 if and only if m and n are both odd.
Beat me to it!
I do wonder if you add the condition that you do not subdivide the board in to uneven boards if it remains possible for the first challenge. I know that with sufficient tiles removed, you can create untileable even boards, but is such a configuration possible with only four removed? I can't think of a way to partition off such a section, but there may very well be a non-partitioned board that would do it
@@BandanaDrummer95 that was my question exactly
the answer to the first challenge was the same as mine by coinendence xD
Third challenge: Fibonacci
Ok, can we take a moment to appreciate the slide transition at 25:40? It's magnificent.
Na
First challenge: no, you can cut out the angle of the board
Yes, that was nice doable warmup challenge. Let's see how you fare with the other ones. Some more doable ones but also a killer or two :)
Second problem: cos(pi/2) is 0. If both m and n are odd then m+1 and n+1 are both even and when j=m/2 and k=n/2 both cos terms are 0, since we're multiplying this makes the whole thing 0
@@complainer406 its christmas
but, isn't the rest of the board in your case coverable with dominoes trivially? i mean when all dominoes are oriented in the same way
We need to cover whole board with this angle. Also, the board without it will have an odd number of squares, so it'll be impossible to cover it
For the m x n board with m and n being odd numbers:
Since m and n are odd, the denominators (m + 1, n + 1) in the fractions inside cos will always be even. And, since we round up in the expression above the PIs, j and k will in one factor both be exactly half of m + 1 and n + 1 respectively. When this happens we get cos(Pi/2) for both terms. Squaring the cos of course changes nothing. And when the product has one zero factor the entire thing will equal zero. Much fun this one!
Very good :)
I made a graph in desmos to visually see that when m and n are odd that the value is 0.
www.desmos.com/calculator/apqualyl52
Yes, I spotted that one (i.e. cos(pi/2=0) as well.
For the hexagon puzzle: looking at the picture as a 3D stack of blocks, it is obvious that each tiling can be gotten by adding one block at a time. This corresponds to rotating a hexagon with side length 1 by 180 degrees. Thus the number of tiles in each color doesn't change. But the numbers are equal when there are no stacked blocks.
Yeah makes sense. If you looked at the stacked cubes from a side, it would be completely one color. Since you can probably build each tileing by stacking cubes it would always be the case.
I got the proof by using the hexagon version of the square dance
@@angelodc1652 That's definitely the easiest way to see its true. How did I forget about it.
Implementations of the crazy dance:
In response to my challenge here are some nice implementations of the dance:
Dmytro Fedoriaka: fedimser.github.io/adt/adt.html (special feature: also calculates pi based on random tilings. First program contributed.)
Shadron czcams.com/video/CCL77BUymSY/video.html (no program but a VERY beautiful animation)
Charly Marchiaro charlymarchiaro.github.io/magic-square-dance/ (special feature: let’s you introduce a bias in the way the arrowed pairs are generated either with a horizontal or vertical orientation. 100% true to the way I did things in the video :)
Jacob Parish: jacobparish.github.io/arctic-circle/ (the first program to feature the bias idea)
chrideedee: chridd.nfshost.com/tilings/diamond(special feature: allows to go forwards and backwards)
Philip Smolen: tradeideasphilip.github.io/aztec-tiles/
Bjarne Fich: rednebula.com/html/arcticcircle.html
The Coding Fox: www.thecodingfox.com/interactive/arctic-circle/
WaltherSolis: wrsp8.github.io/ArcticCircle/index.html
ky lan: editor.p5js.org/kaschatz/sketches/GHCkS-FyN
Jacob Parish: jacobparish.github.io/arctic-circle/
Michael Houston arctic-circle.netlify.app/
Martkjn Jasperse: github.com/mjasperse/aztec_diamond
Jackson Goerner: czcams.com/video/IFMbMchj_Zo/video.html
gissehel webgiss.github.io/CanvasDrawing/arcticcircle.html (require keyboard)
pianfensi github.com/Pianfensi/arctic-circle
Lee Smith s3.eu-north-1.amazonaws.com/dev.dj-djl.com/arctic-circle-generator/index.html
Gino Perrotta github.com/ginop/AztecDiamonds
aldasundimer simonseyock.github.io/arctic_circle/
Shadron czcams.com/video/CCL77BUymSY/video.html
David Weirich github.com/weirichd/ArcticCircle
Richard Copley: bustercopley.github.io/aztec/
Pierre Baillargeon github.com/pierrebai/AztecCircle
Baptiste Lafoux github.com/BaptisteLafoux/aztec_tiling )
Peter Holzer: github.com/hjp/aztec_diamond/
TikiTDO codesandbox.io/s/inspiring-browser-6mq10?file=/src/CpArcticCircle.tsx
Christopher Phelps trinket.io/library/trinkets/5b574f6671
Rick Gove artic-circle-theorem.djit.me
Before I forget, the winner of the lucky draw announced in my last video is Zachary Kaplan. He wins a copy of my book Q.E.D. Beauty in mathematical proof. Congratulations! Zachary please get in touch with me via a comment in this video or otherwise.
I really did not think I could finish this video in time for Christmas. Just so much work at uni until the very last minute and I only got to shoot, edit, and upload the video on the 23rd, a real marathon. But it’s done :)
The arctic circle theorem, something extra special today. I’d never heard of this amazing result until fairly recently although it’s been around for more than 20 years and I did know quite a bit about the prehistory. Hope you enjoy it. As usual please let me know what you liked best. Also please attempt some of the challenges. If you only want to do one, definitely try the what’s next challenge. What’s the number of tilings of the 2x1, 2x2, 2x3, etc. boards? Fairly doable and a really nice AHA moment awaits you.
And let’s do another lucky draw for a chance to win another one of my books among those of you who come up with animations/simulators of the magical crazy dance that I talk about in this video.
Apart from that, I hope you enjoy the video. Merry Christmas, Fröhliche Weihnachten.
Is that the me Zachary Kaplan? Thats very exciting, if so! I really enjoyed this video; combinatorics is one of my favorite subjects, and the arguments used were very clever. Next up on my list is to really read about how that crazy monster formula for the square chessboards is derived!
@@fibbooo1123 It's you :)
@@Mathologer how can I contact you brother
The Arctic Circle with hexagons can also be called Q*Bert's Heaven.
Underrated comment
It's 12 : 00 AM in India
Looking forward to the following 50 minutes
And
Merry Christmas!!
same but in pakistan
From India
But I'm watching it 10 hrs later
I was wondering what could possibly be interesting about the number of ways to tile the glasses. I couldn't have guessed it would be the number of the beast! I also didn't realise that the number of the beast could be written in a neat little expression involving only the first 4 primes: 666 = 3^2(5^2+7^2)
My favourite number :)
How did you find that one? I’m struggling with it.
@@zacharyjoseph5522 It's a bit tricky to explain without diagrams, but I'll do my best. Let us call the whole shape G for glasses. First consider the pair of 2x3 rectangles at the extreme left and right of the glasses. If a domino is placed which crosses the border between the 2x3 and the rest of the glasses, then the 2x3 is left with a region of size 5, so cannot be covered.
We therefore know that the dominoes covering the pair of 2x3 areas are necessarily wholly within the 2x3 areas, so the tilings would be the same if the 2x3 regions were actually disconnected from the glasses. So if we let G' be the glasses without this pair of 2x3 regions and if we let N be the function counting the number of tilings of a shape, then we have N(G) = N(2x3)^2*N(G'), as the tilings of the pair of 2x3 regions and the tiling of G' are independent.
We'll need names for a few other things, so we'll call the boundary of a hole E for eye. So the eye is the 10 squares directly surrounding the hole. Consider the middle 2x2 in G'. Imagine a vertical line L cutting this 2x2 into two pieces. This line divides G' into two equal copies of the same shape, an eye with a 2x1 hanging off one side and a 2x2 hanging off the other. We'll call this shape E+2x2+2x1
Now if we consider tilings with no domino crossing L, then clearly the number is N(E+2x2+2x1)^2, as the tilings of the two shapes on either side of L are independent.
If instead we have a domino crossing L, then we must in fact have 2 dominoes crossing L. This is because otherwise we'd create a region of odd size, which couldn't be tiled. In this arrangement with 2 dominoes crossing L, we again have two identical regions to tile, but this time they are E+2x2, following the naming convention for the previous shape. In this case there are N(E+2x2)^2 tilings.
So we've shown that N(G') = N(E+2x2+2x1)^2+N(E+2x2)^2.
Next we consider E+2x2+2x1. If the 2x1 area is covered by one domino, then we're left with tiling E+2x2. Otherwise, then the tiling is forced all the way to a remaining 2x2 region. Therefore N(E+2x2+2x1) = N(E+2x2)+N(2x2).
Now we consider E+2x2. Imagine a line L' dividing the E from the 2x2. If no domino crosses L', then the E and 2x2 are tiled separately, so we get N(E)*N(2x2) tilings. If instead a domino crosses L', then the rest of tiling is forced, so we get 1 such tiling. Therefore N(E+2x2) = N(E)*N(2x2)+1.
The remainder is not especially hard to check. N(E) = N(2x2) = 2, so N(E+2x2) = 2*2+1 = 5, N(E+2x2+2x1) = 5+2 = 7, N(G') = 7^2+5^2 = 74. Finally N(2x3) = 3, so N(G) = 3^2*74 = 666.
I put it in a matrix calculator and it gave 666 only but I could be wrong because of typing and other mistakes
@@charlottedarroch Minor correction: the 2x3 regions contribute 3*3 possibilities, not 2*3. 666 = 2 * 3 * 3 *37, not 2 * 2 * 3 *37 which is 444.
Fun Fact: If that Hexagon tiling were blocks in Minecraft, then if that represented a sloped hill/mountain in Minecraft, it would be scalable as there is a path from the bottom to the top. Although it's not really obvious that that would be the case.
why is that? and hexagonal prisms? Instead of cubes?
@@averywilliams2140 hexagons are the bestagons
@@averywilliams2140 Visualize the hexagonal tiling as a perspective drawing of cubes.
@@qovro oh shit right. I forgot how beautiful that was
@@qovro like two sheet of hex lattice shifting over one another changing the point in a stack of cubes
Those are some pretty non-christmassy glasses if you ask me, you're a beast.
Dunno... I could see Elton John wearing them, allright!
However, near-round glasses are PERFECT! :)
@@dhpbear2 can accept that if a guy who looks like santa is saying that
Second challenge: it is obvious that in this hexagon there is the same number of dominoes of each color because transposing this 3D volume(from isometric axonometry) into projects on the XOYZ axes we obtain identical squares on OX , OY and OZ planes so an identical number at any scale of dominoes ;(and whenever we place the dominoes , the projections will always be squere).
Very good, that's it (except it's not the second challenge :)
@@Mathologer How do you know every configuration must resemble 3D cubes? Maybe some configuration might look like some strange irregular (for example, non-manifold or having holes or floating cube or other strange whatever) shape. I know that won't happen but how do you prove it?
@@cr1216Every domino points in one of three directions, so they can be interpreted in three dimensions.
Removing two black and two green cannot always work. By counterexample: you can isolate a corner square.
But sometimes you *can*: example: just remove the squares occupied by any two dominoes of a domino-filled chessboard.
Almost word for word what I would have said...
@@etienneschramm83
_Almost word for word for what I would have said..._
Nearly word for word for what I would have said...
isolating a corner equates to creating 2 odd boards, neither of which can be filled, and as such should it be considered a legal move? It's about as useful as removing 63 out of the 64 squares...
And as such some constraints would be handy. Such as one might only remove squares such that all squares on the grid must have at least 1 unique neighbor. A single rule that would suffice to make all boards complete-able.
@@livedandletdie
A diagonal neighbor won't suffice either, since you can remove two greens from one corner and isolate a black square or vice versa.
Never thought I'd see such a detailed video on this topic. I've heard a little bit about all of these concepts (Aztec squares, Kesteleyn's formula, rhombic tilings, etc.) while watching Federico Ardila's great lecture series on combinatorics on CZcams, and I really think the accessibility of this subject benefits from visual-oriented, thorough, and intuition-driven videos like these. As always, great video.
Hey there Mathologer, I had to share this with you. I presented the first 5 minutes of this video to my 8-year-old daughter, who is now immediately proceeding to find a chess board and make dominoes to experiment. This wouldn't be so remarkable but for the fact that she's never initiated a mathematical exploration, nor shown any interest in doing the same. Thanks for helping me have this moment.
I find it particularly interesting how a square grid can give rise to a circle... basically you get rotational symmetry out of something that is not... And why does it have to be L2 symmetry not some other Lp?
The determinant or closely relevant tricks are still intriguing topics nowadays. Leslie Valiant even introduced the name and opened a new subarea, “Holographic algorithms”, for these types of reductions (from seemingly irrelevant problems to linear algebraic ones).
The dance algorithm is incredibly cool. I think my favorite “aha” or maybe even a forehead-slapper in this video was “but how does the powers of two accommodate the deleting of some pairs?! Oh!!!!! Because those add a degeneracy which can be resolved exactly with a multiple of 2!” That was very satisfying.
Nuclear physicists play dominoes because they like starting chain reactions, according to my own interpretation of game theory.
Brilliant
Domino tumbling, there is another nice topic to explore ...
Good one
Lolllll
but they like the domino chains where the pushed tiles per time grow exponentionally
A fun intuition for why the frozen sections show up with high probability: Imagine the left corner of the n'th Aztec Diamond has a horizontally-oriented block on it. If you draw it on paper, you will see that this completely determines that the entire left side of the diamond is only horizontally-oriented blocks, what remains undetermined is nothing more than the (n-1)'th Aztec Diamond. So the number of configurations with a horizontal domino in the left corner is equal to A(n-1), which is fairly intuitively a small fraction of A(n).
This clears things up a lot, thanks! I was very confused by why it was always such a solid, perfect mass, since I was thinking of it as having multiple, off-center nucleation sites, so the probability of it being so perfect seemed low. But since we're not looking at just the likely tilings from placing random pieces and trying to make it work, we're looking at the whole collection of tilings, your way of looking at it is a better one.
Thanks, this really cleared it up for me as well. The algorithm for creating these tilings felt so biased. Of course if tiles always move in the direction they point, you will end up with regions full of tiles pointing that direction. I thought it was an artifact of the procedure.
This algorithm doesn't just generate *a* tiling, it seems to generate the most average random tilings. Still weirds me out that the vast majority of tilings have these solid regions to them.
I figured out the puzzle at the end! I imagined the hexagon as a cube made from cubes. If I look at any of the three sides, I will see a solid color, and each of the three sides is the same, so there is an equal amount of each color.
14:02 Yes. If I lay the leftmost domino of the 2xN rectangle on its side, there's 1 option to fill out the bottom and X(N-2) ways to fill out the N-2 columns to the right. If I put it upright, there's N-1 columns left to fill. So X(N) = X(N-2) + X(N-1), with 1 way to fill a space of 0 columns. Thus, we get the Fibonacci sequence.
37:14 There are an equal number of tiles of each colour because if you were to think about it as a 3d tiling of cubes, looking at it from above would make it look like a perfect square of orange square tiles. This is also true for looking from the other two orthogonal directions. Of course, since the squares are all the same size, they would contain the same amount of tiles.
I've just discovered there's no greater way to start a Christmas day than with a Mathologer video x
6.10. :
Me: What if you cut out 2 black and 2 green squares?
6.20. :
Mathologer: What if you cut out 2 black and 2 green squares?
It's like he read my mind.
The tiling of 2 by grids is Fibonacci series with first term 1 and second term 2
Exactly :)
By implication, the 0x2 (empty) board should be defined as having 1 tiling
Challenge 3: 14:00
The corresponding matrix is n by n with the main diagonal composed of only entries of i with the diagonal above and below consisting of 1 and all other entries are 0. Performing the cofactor expansion on the first row reveals that the determinant (d_n) is i * d_(n-1) - d_(n-2). Computing the first two values and following the formula reveals that the number of ways is precisely the nth Fibonacci number! Very neat!
Very nice :)
I am a 10 th class student from India and this high class maths are not taught to us . But amazingly I am following Mathologer from a looooong time , and his presentation is such that high class maths are not seemed to be such hard or such not understandable. Thank u Mathologer , I had started research on various topics of math just by inspirised by you ☺️☺️☺️☺️☺️☺️
animation autopilot is getting smoother day by day (I can see the damn hard work) Merry Christmas mathologer and wishes for another year of masterclasses.
The slideshow for this one is made up of 521 slides :)
@@Mathologer O_O wow
@@Mathologer what programm do you use to animate your stuff?
@mathologer i would also like to know which program do you used to animate this, it came out beautiful!!
Maybe it's just me, but I immediately identified the four corners of the diamond with the four kingdoms of Oz: Gillikins in the North, Munchkins in the East, Quadlings in the South and Winkies in the West.
Which would place the Emerald City at the center of the circle. Pretty fitting given our math wizard host's country of residence, don't you think? ;-)
I saw a variant of that tiling 2 by n board problem during a competitive programming contest, where you were allowed to use not just 2 by 1 tiles, but also 1 by 1 and L pieces. Really awesome stuff.
On puzzle 3, you can show with induction pretty easily that the n+1 case is equal to the n case + the n-1 case (for n>1): consider the top left-most tile: either that's tiled by a vertical domino, in which 1case all the spaces above can be tiled in the fashion of the n case, or it's tiled via a horizontal domino, meaning the two tiles below must be tiled similarly, and the tiles to the right can be tiled as per the n - 1 case.
That is, 2xn board can be tiled as many ways as the n+1th fibonacci number!
21:30 As soon as you started talking about magic, I knew recursion would be involved. Recursion is the basis of all reality, my friends.
maybe once explain us the Poincaré Theorem proof :D
@Mr. Virtual it's been proven
Loved finding your channel this year sir. Looking forward to many more years enjoying the content. Happy holidays!
Also, as an aside, I was very surprised you didn’t talk about these tricks as “conservation rules”. They provide a beautiful connection to Noether’s theorem via that interpretation.
31:20 That magic moment when one needs to watch the Mathologer to finally understand where the abundance of "this is the way" memes is coming from all of a sudden...
Thank you for this Christmas gift for us all.
37:30 if you look at the hexagon like a space filled with cubes, you notice that grey walls appear in every rank on every row, orange walls appear in every rank in every file, and blue walls in every file on every row; meaning for a size M hexagon, you have M^2 of each colour
Merry Christmas! & Thank you for all the fascinating videos! Can't get enough of 'em!
6:20 No, as you can isolate a corner, which clearly not be tiled over
That's it :)
Removing 2 black and 2 green can you always tile the board.
It depends on how you define "a board."
If "a board" is defined as a continuous connected surface, in other words a surface where you can get from any square to any other square via horizontal and vertical hopping from tile to tile (but not diagonal), simply put, if you cut it out of a sheet of paper, you can pick it up as 1 piece, then the answer is *"yes."*
However, if your definition of "a board" doesn't require such continuity, e.g. an isolated corner separated from the main body is ok, or if you accept corner/diagonal connection as making it continuous, then the answer is *"no,"* as you can isolate a single square.
14:40 Those glasses should work with the determinant, because you can build the matrix as given and give the 4 squares in the holes the highest numbers (23 and 24). That would give the matrix for the board without holes. For our case: Just ignore the "new" last two rows and columns, so get the sub-determinat which would be exactly the same as if we had built the matrix just as is.
So why does this not work for any holes? Where could it go wrong?
I think I got it. Think of the Laplace expansion along the first row. You get a problem, when you can't number a board with holes such that both "1s" are non-adjacent to a hole. A counter example would be a 3x3 ring, ie a 3x3 board missing it's center. It's determinant is 0 but there are 2 tilings.
Very good. One other person actually bothered to check. Evil me :) In fact the determinant will always work if you can fill the holes with dominoes (use the 2x2 switch argument in the masterclass to convince yourself of this fact). To get a board that does not work you need a hole that cannot be tiled with dominoes. For example, have a look at a 3x3 with the middle square removed.
@@Mathologer Yep, I answered myself two minutes after you did, before I just saw yours. Thank you!
@@xario2007 Ah, yes, see it now. That's great :)
12:18 I like the way that sounds: *"PAIRS OF SQUARES"*
Regarding the frozen regions in the diamonds, I would have liked to also have him showing that along any of the edges only two types of tiles can be placed (e.g. blue and red along the upper right edge), which can easily be seen of the squares are colored as chess squares as in the beginning.
And considering any of these edge pieces, as soon as you place a red piece on the upper right edge, then all other edge pieces all the way to the red corner must also be red. This means that each edge have to be subdivided in the two colors of the connected corners and any random subdivision should tend to divide the edge close to the middle.
Then the same procedure can be repeated for the squares inside the edge and so on. The farther you get from the actual edge, the likelier it is for the subdivision to stray from the middle. Also, at each change from one corner color to the other, there is a possibility for the other colors to appear, which will cause the blending in the middle.
I don't argue that the explanation given in the video is bad. It is really beautiful to connect it to the random construction of any tiling. I just would have liked to see this side as well.
The best Christmas gift
Funny piece of trivia : the Arctic circle theorem is linked to the alternate sign matrices, described by no other than Lewis Carroll
I suspect he signed that proof “C. Dodgson”.
Your video description is very thorough. An area often overlooked. Thank you for delivering top quality.
What a fascinating result. Thanks for gifting us with this masterpiece of a video!
I'm going to tile my floor with randomly generated aztec square arctic circles, in shades of grey.
First challenge: It can always be done when removing an even number of tiles as long as there is a round trip that always carves out green and black tiles one after the other and not for example two blacks before one green space is removed
Loved this video so much. Thanks for all the great content this year. Also, this was directly inspiring for my research - what a treat!
Hello Burkhard, I don't know if anyone else did the 2xn board tilings homework that you set us. I was amazed to see the Fibonacci series emerge 1,2,3,5,8,13 after calculating the determinants of the first 6...Amazing! I haven't figured out why. Thanks for a wonderful video. The Aztec diamond tilings resemble Tibetan Buddhist mandala images as the Artic Circle emerges... coincidence?
It may not be the best program but I wanted it to be a christmas gift, so it had to be done (timestamp: Germany 19:51)
github.com/Pianfensi/arctic-circle
(Press space bar when everything is initiated in python)
EDIT: Updated a couple of things
Thank you!
@@user-cn4qb7nr2m yeah somebody appreciate it. Sadly mathologer only favors html based solutions :/ so my time was not that wasted
Hi
Daddy Flammy
Hi Papa Flammy What is the set of letters after "Papa Flammy's advent calendar"?
Merry Christmas Burkard! Thanks for making this hard year a more bearable one.
I have always loved the unbridled beauty of mathematics and even studied it at university, but don’t get around to flexing that mental muscle much in my day to day. Your videos & clear passion for the field always make me fall in love again and I can’t thank you enough for that :) Merry (belated) Christmas!
6:22 Remove (0, 1) and (1, 0) (=> same color) and 2 others of the opposite color anywhere except the corner (0, 0).
That's 2 black + 2 green removed and you won't be able to tile the corner (0, 0) :-)
Proof by contradiction:
Remove A1, B2, C1, D1
Now tile B1 is a single tile which can never be tiled!
Yes, that was nice doable warmup challenge. Let's see how you fare with the other ones. Some more doable ones but also a killer or two :)
Wow, there's so many takeaways from this video(the Fibonacci one was so subtle and satisfying). Quality content, as always!
And the tshirt was so cute 😁😁 (HO)^3 😂
Happy holidays, Sir!
Stunning! Many moons ago we studied some of these patterns in a class I took at Stanford (late 80's). Nothing comes close to these results. The trick with determinants is beautiful.
Merry Christmas Prof Burkard.
Thank you for the amazing years!
I was looking forward to this whole december :). Merry Christmas from Czechia!
vesele vanoce
@@toniokettner4821 Vesele Vanoce :)
Hi everyone, I know I am a bit late to the party, but here is my implementation of the magic square dance: jarusek.wz.cz/ArcticCircle/index.html I tried to implement all steps of the animation, as seen in the video. Hopefully at least someone will see this and I wish you Happy New Year 2021! :)
"Hey programmers"
I see my work is requested.
waiting for github link
@@lumotroph github.com/selplacei/magic-square-dance here's mine, still in progress and the code is shit but i'm having fun
Also waiting for github link
Actually just finished doing this, but it needs some optimization still
@@lumotroph Made a web implementation here for those of you who don't want to run a python program jacobparish.github.io/arctic-circle/
I love the way this guy teaches! Amazing when someone loves what they do...
You need more views. Your videos are really detailed, structured and interesting. Merry Christmas!!!
8:10 that's a big ππ formula indeed
Regarding the arrangement of dominoes in a 2 by “n” grid ... I see a pattern for the first five grids that’s featured in previous Mathologer videos. Perhaps one that gave rise to a certain partition / pentagonal number theorem in recent memory? ;)
What a clever mathematical exploration! I loved seeing the circle come in the limit of both the diamond and the hexagon, it was so elegant. I suspect that this area of study has applications in metallurgy, crystallography, and materials science.
One thing I love about methologer is that Burkard always provide some accessible paper for those who willing to investigate further for the topic(s)!!!
Those glasses are beastly things.
I wonder : if one were to 3D print these pseudo3d timings into actual 3D shapes, would the « arctic circle » turn into an arctic section of a sphere of sorts? What about matching pairs? And what about higher dimensional tilings ?
I wanna know specifically if it's possible to move into 3D with the triangular grid. The first problem is that there isn't an obvious, clean analogy to the triangular tiling in 3D; the tetrahedron in particular cannot tesselate 3D space. Well, let's look at that quirk of the triangular domino tiling: that it looks like an isometric view of a certain kind of stack of cubes. Particularly, the envelope of any side of a cube at a particular orientation is a sqrt(2) rhombus (that is, a rhombus made from two triangles). We might think to find a polyhedron which is an envelope of a hypercube, and then more specifically the envelopes of each cubic cell of the hypercube.
Without knowing a whole lot about higher-dimensional geometry, I think our best bet is the sqrt(2) Trigonal Trapezohedron for our "dominos." Four of these can pack together into a Rhombic Dodecahedron, which is an envelope for the hypercube, and that will fill the same role as a hexagon does in the triangular grids with rhombic dominos. Our trapezohedron can be constructed from two tetrahedrons and an octahedron, all regular.
Now, while our "dominos" and hexagon-stand-ins both tile 3D space, the Trapezohedron can't be split into two shapes that are very symmetrical like the 2D rhombus could into triangles. However, we can tile space using _both_ tetrahedrons and octahedrons together. This, for unclear reasons, is known as the tetrahedral-octahedral honeycomb.
Using this honeycomb as a grid, we can define our particular Trapezohedron as a 'Tromino' (polyomino of 3 elements, like a _d_omino or _tetr_omino).
[Actually, it's not called a domino on the triangular grid, it's called a 'diamond,' which is the 2-polyiamond, and you've got the triamond and the tetriamond. But this is 3D, not 2D. There's a bunch of names for poly_cubes_, so like with a cubic grid. Not quite what we're doing. Really, it's too many names. I'll call this a Tromino, because it's easier.]
I think, but I don't know for sure, that you can make a Rhombic Dodecahedron by tiling together these trominos inside the tetrahedral-octahedral grid. This would be like making a hexagon from the rhombuses in a triangular grid. Put like that it sounds reasonable, but not obvious. I have a hunch that just using the tetrahedral-octahedral honeycomb isn't enough, and you actually need the _gyrated_ tetrahedral-octahedral honeycomb. The difference is as wierd as it sound, but not complicated. In the normal such honeycomb, you can think of the two different shapes, the tetrahedron and the octahedron, as the two colors of a checkers board: they alternate when you move from one to the next. The graphics on Wikipedia use red tetrahedra and blue octahedra. Now picture a checkers board, but you switch the colors part-way up. Now you have two squares of the same color next to each other, for each pair along the whole row. This is what's done in the gyrated honeycomb; along a whole plane, the tetrahedra to one side are next to tetrahedra on the other side, and likewise octahedra.
My hunch is that the strange way the trapezohedra need to be placed to make a Rhombic Dodecahedron would put an octahedron next to an octahedron, which would symmetrically happen twice, and also with a bunch of tetrahedra. Using the gyrated honeycomb would allow this. You'd then want to have this switch actually happen repeatedly, every other 'layer,' as they're called. This gyrated form has less symmetry, though (remember that there was one plane, or layer, that was preferred for this 'switching' of shapes), so I'd hope it could be done without.
That's about all I can wrap my head around without making any models, graphical or physical, and I'm not much of a modeler, graphical or physical.
Wow, this video really blew my mind! Some very amazing combinatorics! Now I think I know how to solve one of the projecteuler problems that stumped me for several years, namely figuring out the number of domino tilings of a 3 x 2n board.
Thank you so much for sharing such an amazing and beautiful result. I hope that you all have a merry Christmas and get plenty of rest.
Really appreciate the perspective of a determinant as a sum of permutations, I've never seen that before. I feel like an actual intuition for the determinant may not be too far behind. Trace has been similarly confusing for me my whole life - what possible simple interpretation could it have, and why is it so conserved?
It might also help to notice that both the determinant and the trace are coefficients in the characteristic polynomial.
You probably won't find this helpful but the trace is the linear map End(V) ≅ V* ⨂ V → K where K is the base field.
The isomorphism V* ⨂ V ≅ End(V) is given by φ ⨂ v ↦ (x ↦ φ(x)∙v).
The linear map V* ⨂ V → K is given by φ ⨂ v ↦ φ(v).
Since both of these are base-independent, the trace is also base-independent. That's why it is conserved.
@@usernamenotfound80 Nice i will learn that fact prolly next semester since we learned duality in this one :)
But that with permutations is basically how we built up the determinant formula, with the leibniz formula and then proving that it is equal to develop it to a row or column or how you say that in english
It's 12:05 AM here, what a Christmas gift mathologer thanks! 😍
same
It's currently 5:53 am here in Melbourne (25 Dec). I feel so relieved. Got the video published in time for Christmas :)
@@Mathologer 😍thank you for making christmas so lovely. Merry Christmas!
A lot of kudos for the description below your videos, the links you provided are very useful.
What a fabulous video.The thing I liked the most in this video is how we approached to solve the problem, and that is absolutely we all need to know to sharpen our brains.
That Hex board Reminds me of One qbert video game.
Same
7:52
"Kasteleyn's watching you"
i'm... genuinely scared now, im sitting in a dark room
THE BIGGEST HONOR A MATHOLOGER VIEWER CAN GET, A HEART FROM THE BIG M HIMSELF
Thank you for the beautiful Christmas gift. This video should be under my Christmas tree! Congratulations and continue with your work!
Christmas glasses:
The squares numbered 20r and 20g must be part of their outer 2x3 "arms", or they'd leave a 5-square board that can't be tiled. These two 2x3 sections can be tiled 3 ways each.
So far: 3 x 3 = 9 ways to tile the outer two rectangles.
Then, the red and green squares numbered '8' and '15' can only be part of 4 different pairings (e.g. 8r and 15g must both be paired to their left or their right), otherwise they'd isolate a section with an odd number of squares. Call these 4 pairings First, Outside, Inside, Last (like FOIL). EG: 'First' = both sets of pairs made with the left neighbour.
Using 'First': Working left-to-right, we get a 2x3 grid (3 ways), then 13g-9r and 14g-10r must be paired, then another 2x3 grid (3 ways), then 17r-7g and 16r-6g must be paired, then a 2x2 grid (2 ways). This multiplies to a total of 3x3x2 = 18 ways.
Using 'Outside': Working left-to-right, we get the same 2x3 grid (3 ways), then 13g-9r and 14g-10r must be paired, leaving a 2x2 grid in the middle (2 ways) and a 2x3 grid on the right (3 ways). This makes a total of 3x2x3 = 18 ways.
Using 'Inside': 17g-7r and 16g-6r must be paired, leaving a 2x2 grid to the left (2 ways); likewise, 17r-7g and 16r-6g must pair, leaving a 2x2 grid to their right (2 ways). This all leaves a 2x4 grid in the middle (5 ways). Total: 2x2x5 = 20 ways.
Using 'Last': Same as 'First', but mirrored. Total: 18 ways.
Multiplying all this together gives:
3 x 3 x (18 + 18 + 20 + 18)
= 9 x 74
= 666
Truly a 'beast' of a solution.
Nice evil :) Have a look at the current subscriber count :)
@@Mathologer Nice! That is a sick, sick, sick subscriber count ;D
No. The counterexample is easy, remove a2, a3, b1, c1. a1 is isolated and therefore no tiling is possible
I don’t understand why, when you are explaining how to grow a random tiling at 22:41, you split up the empty 2x4 region into two 2x2 regions. Wouldn’t there be more possible tilings if you were allowed to also split it into 2x1 + 2x2 + 2x1? It seems to me that there would be. And while the tiling you get would be identical in tile positions to one you could have gotten another way, the arrow directions would be different and they would grow into different tilings at the next step.
I think splitting into 2x1+2x2+2x1 after expanding the 2x2 vertical-vertical baby diamond introduces an overcounting. The seemingly new ways of tiling are actually already included by the other choice of the initial 2x2 baby diamond (horizontal-horizontal) because the two 2x1's at the start and end of 2x1+2x2+2x1 would correspond to having top and bottom being horizontal, which would've resulted from expanding an initial horizontal-horizontal 2x2 baby diamond.
@@lezhilo772 No, there's one tiling that can't be reached from doing two 2x2's. If you use 2x1 for each end, then swap the orientation of the 2x2 in the middle so it's opposite the ends, you can't get that tiling from just using two 2x2's.
@@Xeridanus Let me try to type out all the tilings, hopefully the formatting works. Im going to use
HH
for a horizontal tile, and
V
V
for a vertical tile.
So we start from a 2x2 baby diamond, which is either
VV
VV
or
HH
HH
For the VVVV baby diamond, after expanding, we get
__
V__V
V__V
__
and using the two 2x2 block formalism, there will be four possible outcomes
HH
VHHV
VHHV
HH
HH
VHHV
VVVV
VV
VV
VVVV
VHHV
HH
VV
VVVV
VVVV
VV
For the other baby diamond, we have four more cases
HH
VVVV
VVVV
HH
HH
HHVV
HHVV
HH
HH
VVHH
VVHH
HH
HH
HHHH
HHHH
HH
Suppose you take one of these 8 cases, and switch the middle 2x2 blocks, it will be sent to another case. Example: if I take case 8
HH
HHHH
HHHH
HH
and switch the middle 2x2 block so I end up with
HH
HVVH
HVVH
HH
then it would seem like I have a different case. But a vertical HH is not possible: it's actually just a vertical VV, so we cannot just rotate the middle 2x2 block, instead, it would be
HH
VVVV
VVVV
HH
which is just case 5.
So I think the key to answering your question is that it is impossible to just rotate any 2x2 block without affecting others, unless they are in some special positions, defined by the expanding diamond algorithm. I think what the algorithm does is that by expanding the diamond like this, all these superfluous degrees of freedom will be eliminated.
@@lezhilo772 No, you don't get it at all. You're right but you're misunderstanding the problem.
HH
HHHH
HHHH
HH
You can't swap the two in the middle because they're joined to the two on the outside.
HH
VVVV
VVVV
HH
can be swapped to this:
HH
VHHV
VHHV
HH
Which does produce a different tiling that can't be reached by the method in the video.
@@Xeridanus This tiling can be reached by the method in the video: start with a VVVV 2x2 baby diamond, expand, and pick both 2x2s to be HHHH (case 1 in my list).
Absolutely outstanding! Great presentation as always.
First two challenges I saw solutions to, but the third challenge seems to be 1, 2, 3, 5, 8 so I'm guessing the fibbanoci sequence minus the first 1(or if you think about it, it's like 0! when there's no chessboard the only way to tile it is with nothing.)
Edit: for the final puzzle, we can see that on the smallest hexagon board, we need exactly one of each piece to tile it. Expanding the board like with the previous dance leaves us with three smaller boards uncovered in the larger regular hexagon. all of which need exactly one of each piece to be filled. While you may be able to swap pieces, they'll all still be needed.
Is it a known fact that you can get from any domino tiling to any other tiling by rotating 2x2 squares? Seems true for non-hole boards...
And indeed if you look at the formula for rectangular boards, it always spits out an even number.
He mentions this at 49:00
Yes, very good insight :)
was that an arctic cardioid at the end? how... cold-hearted of you :P
The arctic heart at the end of the video is a "chistmasized" version of an image that appeared in the article "What is a Dimer" by Richard Kenyon and Andrei Okounkov www.ams.org/notices/200503/what-is.pdf
for the challenge at 13:58 - it's very cool how the 2xN chessboards produce Fibonacci numbers - 1,2,3,5,8,13,etc. - but even cooler is how, if you separate the totals for each chessboard into subsets based on the number of vertical dominoes, you get Pascal's triangle.
I loved the hexagonal tilings. This is yet another great video. Well done and thank you.
What an unexpected fibonacci 'aha' moment!
Very good that was fast :)
Can you tell me how to derive this myself? I love math but I'm kinda bad at it 😅
@@averagemilffan Take the upper left corner of the 2xn board. There are two ways to cover that square with a domino. One results in a 2x(n-1) board, the other results in a 2x(n-2) board with a domino shaped region hanging off which can only be covered in the obvious way.
My brain took 10 minutes to get the HO^3 joke.
Another grand video brimming with Mathologer's characteristic good cheer and containing several playful challenges for the audience. The content is quite accessible, despite coming from relatively recent mathematical literature. "This is not the Discovery Channel" was my favorite quote. Kudos to Bjarne Fich for rising to Burkard's challenge and creating such a professional Arctic Circle animation.
Here is my response to Mathologer's request for feedback.
Challenge 1: No, removing 2 black & 2 green squares will not always yield a tile-able board. For example, removing (2,1) and (1,2) leaves (1,1) isolated.
Challenge 2: If m & n are odd, then ( j, k ) = ( (m+1)/2, (n+1)/2 ) yields a zero term in the product.
Challenge 3: 2xn squares yield (1,2,3,5,8,...) tilings for n=(1,2,3,4,5). This sequence follows the Fibonacci rule. To see why, observe that T(n+1), the number of tilings for n+1, can be computed by adding the number of tilings with the last domino vertical, which is T(n), and the number of tilings with the last two dominoes horizontal, which is T(n-1). Aha!
Challenge 4: The determinant for Tristan's glasses gives 666. By drawing the 4 ways of tiling around the holes I get the same result, but have yet to see why the determinant formula should work when the holes themselves can be tiled.
Challenge 5: Previous comments allowed me to see why a hexagon tiling must be split evenly into the 3 tile orientations. Unfortunately, I did not see this for myself.
Most of the video was clear. However, I am mystified as to why the dance yields all possible tilings, and why, for example, a pair of adjacent 2x2 squares don't count as a 2x4 rectangle. Mathologer dropped some clues, but I guess I need to consult the references.
Looking forward to more great content in 2021!
Mathologer what a way to close this year. Thanks for the fascinating and (thanks to you) accesible material you share with all of us. really great!