What concepts or facts do you know from math that is mind blowing, awesome, or simply fascinating?
Here are some I would like to share:
- Gödel’s incompleteness theorems: There are some problems in math so difficult that it can never be solved no matter how much time you put into it.
- Halting problem: It is impossible to write a program that can figure out whether or not any input program loops forever or finishes running. (Undecidablity)
The Busy Beaver function
Now this is the mind blowing one. What is the largest non-infinite number you know? Graham’s Number? TREE(3)? TREE(TREE(3))? This one will beat it easily.
- The Busy Beaver function produces the fastest growing number that is theoretically possible. These numbers are so large we don’t even know if you can compute the function to get the value even with an infinitely powerful PC.
- In fact, just the mere act of being able to compute the value would mean solving the hardest problems in mathematics.
- Σ(1) = 1
- Σ(4) = 13
- Σ(6) > 101010101010101010101010101010 (10s are stacked on each other)
- Σ(17) > Graham’s Number
- Σ(27) If you can compute this function the Goldbach conjecture is false.
- Σ(744) If you can compute this function the Riemann hypothesis is false.
Sources:
- YouTube - The Busy Beaver function by Mutual Information
- YouTube - Gödel’s incompleteness Theorem by Veritasium
- YouTube - Halting Problem by Computerphile
- YouTube - Graham’s Number by Numberphile
- YouTube - TREE(3) by Numberphile
- Wikipedia - Gödel’s incompleteness theorems
- Wikipedia - Halting Problem
- Wikipedia - Busy Beaver
- Wikipedia - Riemann hypothesis
- Wikipedia - Goldbach’s conjecture
- Wikipedia - Millennium Prize Problems - $1,000,000 Reward for a solution
That you can have 5 apples, divide them zero times, and somehow end up with math shitting itself inside-out at you even though the apples are still just sitting there.
You try having 5 apples and divide them into 0 equal groups and you’ll shit yourself too.
Except that by dividing the total number zero times means you’re not dividing them at all, and therefore by doing nothing you are still left with 5 apples.
Not dividing at all is dividing by 1.
deleted by creator
x^n + y^n = z^n has no solutions where n > 2 and x, y and z are all natural numbers. It’s hard to believe that, knowing that it has an infinite number of solutions where n = 2.
Pierre de Format, after whom this theorem was named, famously claimed to have had a proof by leaving the following remark in some book that he owned: “I have a proof of this theorem, but there is not enough space in this margin”. It took mathematicians several hundred years to actually find the proof.
Goldbach’s Conjecture: Every even natural number > 2 is a sum of 2 prime numbers. Eg: 8=5+3, 20=13+7.
https://en.m.wikipedia.org/wiki/Goldbach’s_conjecture
Such a simple construct right? Notice the word “conjecture”. The above has been verified till 4x10^18 numbers BUT no one has been able to prove it mathematically till date! It’s one of the best known unsolved problems in mathematics.
Wtf !
How can you prove something in math when numbers are infinite? That number you gave if it works up to there we can call it proven no? I’m not sure I understand
That’s a really great question. The answer is that mathematicians keep their statements general when trying to prove things. Another commenter gave a bunch of examples as to different techniques a mathematician might use, but I think giving an example of a very simple general proof might make things more clear.
Say we wanted to prove that an even number plus 1 is an odd number. This is a fact that we all intuitively know is true, but how do we know it’s true? We haven’t tested every single even number in existence to see that itself plus 1 is odd, so how do we know it is true for all even numbers in existence?
The answer lies in the definitions for what is an even number and what is an odd number. We say that a number is even if it can be written in the form 2n, where n is some integer, and we say that a number is odd if it can be written as 2n+1. For any number in existence, we can tell if it’s even or odd by coming back to these formulas.
So let’s say we have some even number. Because we know it’s even, we know we can write it as 2n, where n is an integer. Adding 1 to it gives 2n+1. This is, by definition, an odd number. Because we didn’t restrict at the beginning which even number we started with, we proved the fact for all even numbers, in one fell swoop.
As you said, we have infinite numbers so the fact that something works till 4x10^18 doesn’t prove that it will work for all numbers. It will take only one counterexample to disprove this conjecture, even if it is found at 10^100. Because then we wouldn’t be able to say that “all” even numbers > 2 are a sum of 2 prime numbers.
So mathematicians strive for general proofs. You start with something like: Let n be any even number > 2. Now using the known axioms of mathematics, you need to prove that for every n, there always exists two prime numbers p,q such that n=p+q.
Would recommend watching the following short and simple video on the Pythagoras theorem, it’d make it perfectly clear how proofs work in mathematics. You know the theorem right? For any right angled triangle, the square of the hypotenuse is equal to the sum of squares of both the sides. Now we can verify this for billions of different right angled triangles but it wouldn’t make it a theorem. It is a theorem because we have proved it mathematically for the general case using other known axioms of mathematics.
There are many structures of proof. A simple one might be to prove a statement is true for all cases, by simply examining each case and demonstrating it, but as you point out this won’t be useful for proving statements about infinite cases.
Instead you could assume, for the sake of argument, that the statement is false, and show how this leads to a logical inconsistency, which is called proof by contradiction. For example, Georg Cantor used a proof by contradiction to demonstrate that the set of Natural Numbers (1,2,3,4…) are smaller than the set of Real Numbers (which includes the Naturals and all decimal numbers like pi and 69.6969696969…), and so there exist different “sizes” of infinity!
For a method explicitly concerned with proofs about infinite numbers of things, you can try Proof by Mathematical Induction. It’s a bit tricky to describe…
- First demonstrate that a statement is true in some 1st base case.
- Then demonstrate that if it holds true for the abstract Nth case, then it necessarily holds true for the (N+1)th case (by doing some clever rearranging of algebra terms or something)
- Therefore since it holds true for the 1th case, it must hold true for the (1+1)th case = the 2th case. And since it holds true for the 2th case it must hold true for the (2+1)=3th case. And so on ad infinitum.
Wikipedia says:
Mathematical induction can be informally illustrated by reference to the sequential effect of falling dominoes.
Bear in mind, in formal terms a “proof” is simply a list of true statements, that begin with axioms (which are true by default) and rules of inference that show how each line is derived from the line above.
Very cool and fascinating world of mathematics!
Just to add to this. Another way could be to find a specific construction. If you could for example find an algorithm that given any even integer returns two primes that add up to it and you showed this algorithm always works. Then that would be a proof of the Goldbach conjecture.
The Banach - Tarski Theorm is up there. Basically, a solid ball can be broken down into infinitely many points and rotated in such a way that that a copy of the original ball is produced. Duplication is mathematically sound! But physically impossible.
Duplication is mathematically sound!
Only if you accept the axiom of choice :P
Imagine a soccer ball. The most traditional design consists of white hexagons and black pentagons. If you count them, you will find that there are 12 pentagons and 20 hexagons.
Now imagine you tried to cover the entire Earth in the same way, using similar size hexagons and pentagons (hopefully the rules are intuitive). How many pentagons would be there? Intuitively, you would think that the number of both shapes would be similar, just like on the soccer ball. So, there would be a lot of hexagons and a lot of pentagons. But actually, along with many hexagons, you would still have exactly 12 pentagons, not one less, not one more. This comes from the Euler’s formula, and there is a nice sketch of the proof here: https://math.stackexchange.com/a/18347.
You’re missing your link, homie!
It seems that I can’t see the link from 0.18.3 instances somehow. Maybe one of these will work: https://math.stackexchange.com/a/18347 https://math.stackexchange.com/a/18347
https://math.stackexchange.com/a/18347
Godel’s incompleteness theorem is actually even more subtle and mind-blowing than how you describe it. It states that in any mathematical system, there are truths in that system that cannot be proven using just the mathematical rules of that system. It requires adding additional rules to that system to prove those truths. And when you do that, there are new things that are true that cannot be proven using the expanded rules of that mathematical system.
"It’s true, we just can’t prove it’.
Incompleteness doesn’t come as a huge surprise when your learn math in an axiomatic way rather than computationally. For me the treacherous part is actually knowing whether something is unprovable because of incompleteness or because no one has found a proof yet.
Thanks for the further detail!
How Gauss was able to solve 1+2+3…+99+100 in the span of minutes. It really shows you can solve math problems by thinking in different ways and approaches.
50*101?
Yep. N * (n + 1) / 2.
You can think of it as.
1 + 2 + 3 + 4 ... 100 + 100 + 99 + 98 + 97 + 1101 + 101 + 101 ... 101 = 2 * sum(1+2+3...100)
Small nit: you don’t compute sigma, you prove a value for a given input. Sigma here is uncomputable.
was not aware of the machines halting only iff conjectUres are true, tho. Thats a flat out amazing construction.
The four-color theorem is pretty cool.
You can take any map of anything and color it in using only four colors so that no adjacent “countries” are the same color. Often it can be done with three!
Maybe not the most mind blowing but it’s neat.
this whole thread is the shit.
I read an interesting book about that once, will need to see if I can find the name of it.
EDIT - well, that was easier than expected!
Read the author as Robin Williams
What about a hypothetical country that is shaped like a donut, and the hole is filled with four small countries? One of the countries must have the color of one of its neighbors, no?
There are some rules about the kind of map this applies to. One of them is “no countries inside other countries.”
I see.
Not true, see @BitSound’s comment.
It does have to be topologically planar (may not be the technical term), though. No donut worlds.
The regions need to be contiguous and intersect at a nontrivial boundary curve. This type of map can be identified uniquely with a planar graph by placing a vertex inside each region and drawing an edge from one point to another in each adjacent region through the bounding curve.
In that image, you could color yellow into purple since it’s not touching purple. Then, you could color the red inner piece to yellow, and have no red in the inner pieces.
I think the four small countries inside would each only have 2 neighbours. So you could take 2 that are diagonal and make them the same colour.
Looks to be that way one of the examples given on the wiki page. It is still however an interesting theory, if four countries touching at a corner, are the diagonal countries neighbouring each other or not. It honestly feels like a question that will start a war somewhere at sometime, probably already has.
In graph theory there are vertices and edges, two shapes are adjacent if and only if they share an edge, vertices are not relevant to adjacency. As long as all countries subscribe to graph theory we should be safe
The only problem with that it that it requires all countries to agree to something, and that seems to become harder and harder nowadays.
But each small country has three neighbors! Two small ones, and always the big donut country. I attached a picture to my previous comment to make it more clear.
In your example the blue country could be yellow and that leaves the other yellow to be blue. Now no identical colors touch.
You still have two red countries touching each other, what are you talking about?
Oops I meant the red one goes blue.
Whoops I should’ve been clearer I meant two neighbours within the donut. So the inside ones could be 2 or 3 colours and then the donut is one of the other 2 or the 1 remaining colour.
You’re right. Bad example from my side. But imagine this scenario:
That map is actually still quite similar to the earlier example where all 4 donut hole countries are the same. Once again on the right is the adjacency graph for the countries where I’ve also used a dashed line to show the only difference in adjacency.
Oh wow, now I feel dumb. Thanks.
Make purple yellow and one of the reds purple.
…There is no purple though?
Ok now do this one. What color is the donut country?
Someone beat me to it, so I thought I’d also include the adjacency graph for the countries, it can be easier to see the solution to colouring them.
Isn’t the proof of this theorem like millions of pages long or something (proof done by a computer ) ? I mean how can you even be sure that it is correct ? There might be some error somewhere.
If you had a 3 dimensional map, would you need more colors to achieve the same results?
Edit: it was explained in your link. It looks like for surfaces in 3D space, this can’t be generalized.
Thanks for the comment! It is cool and also pretty aesthetically pleasing!
Your map made me think how interesting US would be if there were 4 major political parties. Maybe no one will win the presidential election 🤔
Note you’ll need the regions to be connected (or allow yourself to color things differently if they are the same ‘country’ but disconnected). I forget if this causes problems for any world map.
I suspect that the Belgium-Netherlands border defies any mathematical description.
Not so much a fact, but I’ve always liked the prime spirals: https://en.wikipedia.org/wiki/Ulam_spiral
Also, not as impressive as the busy beaver, but Knuth’s up-arrow notation is cool: https://en.wikipedia.org/wiki/Knuth’s_up-arrow_notation
Thanks for sharing! (No worries, changed the title from “fact” to “thing” to be a bit more broad)
Knuth’s arrow shows up in… Magic the Gathering. There’s a challenge of “how much damage can you deal with just 3 cards and without infinitely repeating loops?”. Turns out that stacking doubler effects can get us really high. https://www.polygon.com/23589224/magic-phyrexia-all-will-be-one-best-combo-attacks-tokens-vindicator-mondrak
There are more ways to arrange a deck of 52 cards than there are atoms on Earth.
I feel this one is quite well known, but it’s still pretty cool.
An extension of that is that every time you shuffle a deck of cards there’s a high probability that that particular arrangement has never been seen in the history of mankind.
With the caveat that it’s not the first shuffle of a new deck. Since card decks come out of the factory in the same order, the probability that the first shuffle will result in an order that has been seen before is a little higher than on a deck that has already been shuffled.
Since a deck of cards can only be shuffled a finite number of times before they get all fucked up, the probability of deck arrangements is probably a long tail distribution
The most efficient way is not to shuffle them but to lay them all on a table, shift them around, and stack them again in arbitrary order.
assuming a perfect mechanical shuffle, I think the odds are near zero. humans don’t shuffle perfectly though!
perfect mechanical shuffle
What’s perfect in this context? It’s maybe a little counterintuitive because I’d think a perfect mechanical shuffle would be perfectly deterministic (assuming no mechanical failure of the device) so that it would be repeatable. Like, you would give it a seed number (about 67 digits evidently) and the mechanism would perform a series of interleaves completely determined by the seed. Then if you wanted a random order you would give the machine a true random seed (from your wall of lava lamps or whatever) and you’d get a deck with an order that is very likely to never have been seen before. And if you wanted to play a game with that particular deck order again you’d just put the same seed into the machine.
Perfect is the sense that you have perfect randomness. Like the Fisher-Yates shuffle.
In order to have a machine that can “pick” any possible shuffle by index (that’s all a seed really is, a partial index into the space of random numbers), you’d need a seed 223 bits long.
But you wouldn’t want perfect mechanical shuffles though because 8 perfect riffles will loop the deck back to it’s original order! The minor inaccuracies are what makes actual shuffling work.
I’d probably have the machine do it all electronically and then sort the physical deck to match, not sure you could control the entropy in a reliable way with actual paper cards otherwise.
deleted by creator
The one I bumped into recently: the Coastline Paradox
“The coastline paradox is the counterintuitive observation that the coastline of a landmass does not have a well-defined length. This results from the fractal curve–like properties of coastlines; i.e., the fact that a coastline typically has a fractal dimension.”
Non-Euclidean geometry.
A triangle with three right angles (spherical).
A triangle whose sides are all infinite, whose angles are zero, and whose area is finite (hyperbolic).
I discovered this world 16 years ago - I’m still exploring the rabbit hole.
Spherical geometry isn’t even that weird because we experience it on earth at large scales.
I’m not sure Earth would be a correct analogy for spherical geometry. Correct me if I’m wrong, but spherical geometry is when the actual space curvature is a sphere, which is different from just living on a sphere.
CodeParade made a spherical/hyperbolic geometry game, and here’s one of his devlogs explaining spherical curvature: https://www.youtube.com/watch?v=yY9GAyJtuJ0
A sphere is a perfect model of spherical geometry. It’s just a 2-dimensional one, the spherical equivalent of a plane we might stand on as opposed to the space we live in. A sphere is locally flat (locally Euclidean/plane-like) but intrinsically curved, and indeed can have triangles with 3 right angles (with endpoints on a pole and the equator.)
Ah, gotcha! Spherical and hyberbolic geometries always mess with my mind a bit. Thanks for the explanation!
Oh yeah I’m subscribed to codeparade! I know it’s not a perfect analogue but since it’s such a large scale, our perspective makes it look flat. So at long distances it feels like you’re moving in a straight line when you’re really not.
The birthday paradox
