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
You must log in or register to comment.
For the uninitiated, the monty Hall problem is a good one.
Start with 3 closed doors, and an announcer who knows what’s behind each. The announcer says that behind 2 of the doors is a goat, and behind the third door is
a carstudent debt relief, but doesn’t tell you which door leads to which. They then let you pick a door, and you will get what’s behind the door. Before you open it, they open a different door than your choice and reveal a goat. Then the announcer says you are allowed to change your choice.So should you switch?
The answer turns out to be yes. 2/3rds of the time you are better off switching. But even famous mathematicians didn’t believe it at first.
I know the problem is easier to visualize if you increase the number of doors. Let’s say you start with 1000 doors, you choose one and the announcer opens 998 other doors with goats. In this way is evident you should switch because unless you were incredibly lucky to pick up the initial door with the prize between 1000, the other door will have it.
This is so mind blowing to me, because I get what you’re saying logically, but my gut still tells me it’s a 50/50 chance.
But I think the reason it is true is because the other person didn’t choose the other 998 doors randomly. So if you chose any of the other 998 doors, it would still be between the door you chose and the winner, other than the 1/1000 chance that you chose right at the beginning.
I don’t find this more intuitive. It’s still one or the other door.
The point is, the odds don’t get recomputed after the other doors are opened. In effect you were offered two choices at the start: choose one door, or choose all of the other 999 doors.
I think the problem is worded specifically to hide the fact that you’re creating two set of doors by picking a door, and that shrinking a set actually make each individual door in that set more likely to have the prize.
Think of it this way : You have 4 doors, 2 blue doors and 2 red doors. I tell you that there is 50% chance of the prize to be in either a blue or a red door. Now I get to remove a red door that is confirmed to not have the prize. If you had to chose, would you pick a blue door or a red door? Seems obvious now that the remaining red door is somehow a safer pick. This is kind of what is happening in the initial problem, but since the second ensemble is bigger to begin with (the two doors you did not pick), it sort of trick you into ignoring the fact that the ensemble shrank and that it made the remaining door more “valuable”.
The odds you picked the correct door at the start is 1/1000, that means there’s a 999/1000 chance it’s in one of the other 999 doors. If the man opens 998 doors and leaves one left then that door has 999/1000 chance of having the prize.
Same here, even after reading other explanations I don’t see how the odds are anything other than 50/50.
read up on the law of total probability. prob(car is behind door #1) = 1/3. monty opens door #3, shows you a goat. prob(car behind door #1) = 1/3, unchanged from before. prob(car is behind door #2) + prob(car behind door #1) = 1. therefore, prob(car is behind door #2) = 2/3.
Following that cascade, didn’t you just change the probability of door 2? It was 1/3 like the other two. Then you opened door three. Why would door two be 2/3 now? Door 2 changes for no disclosed reason, but door 1 doesn’t? Why does door 1 have a fixed probability when door 2 doesn’t?
No, you didn’t change the prob of #2. Prob(car behind 2) + prob(car behind 3) = 2/3. Monty shows you that prob(car behind 3) = 0.
This can also be understood through conditional probabilities, if that’s easier for you.
The thing is, you pick the door totally randomly and since there are more goats, the chance to pick a goat is higher. That means there’s a 2/3 chance that the door you initially picked is a goat. The announcer picks the other goat with a 100% chance, which means the last remaining door most likely has the prize behind it
Edit: seems like this was already answered by someone else, but I didn’t see their comment due to federation delay. Sorry
How do we even come up with such amazing problems right ? It’s fascinating.
But even famous mathematicians didn’t believe it at first.
They emphatically did not believe it at first. Marilyn vos Savant was flooded with about 10,000 letters after publishing the famous 1990 article, and had to write two followup articles to clarify the logic involved.
First, fuck you! I couldn’t sleep. The possibility to win the car when you change is the possibility of your first choice to be goat, which is 2/3, because you only win when your first choice is goat when you always change.
x1: you win
x2: you change
x3: you pick goat at first choice
P(x1|x2,x3)=1 P(x1)=1/2 P(x3)=2/3 P(x2)=1/2
P(x1|x2) =?
Chain theory of probability:
P(x1,x2,x3)=P(x3|x1,x2)P(x1|x2)P(x2)=P(x1|x2,x3)P(x2|x3)P(x3)
From Bayes theorem: P(x3|x1,x2)= P(x1|x2,x3)P(x2)/P(x1) =1
x2 and x3 are independent P(x2|x3)=P(x2)
P(x1| x2)=P(x3)=2/3 P(x2|x1)=P(x1|x2)P(x2)/P(X1)=P(x1|x2)
P(x1=1|x2=0) = 1- P(x1=1|x2=1) = 1\3 is the probability to win if u do not change.
Why do you have a P(x1) = 1/2 at the start? I’m not sure what x1 means if we don’t specify a strategy.
Just count the number of possibilities. If you change there there two possible first choices to win + if you do not change 1 possible choice to win = 3. If you change there is one possible first choice to lose + if you do not change there two possible first choices to lose=3 P(x1)=P(x1’) = 3/6
Ah, so it’s the probability you win by playing randomly. Gotcha. That makes sense, it becomes a choice between 2 doors
Without condition would be more technically correct term but yes
deleted by creator
I know it to be true, I’ve heard it dozens of times, but my dumb brain still refuses to accept the solution everytime. It’s kind of crazy really
Let’s name the goats Alice and Bob. You pick at random between Alice, Bob, and the Car, each with 1/3 chance. Let’s examine each case.
-
Case 1: You picked Alice. Monty eliminates Bob. Switching wins. (1/3)
-
Case 2: You picked Bob. Monty eliminates Alice. Switching wins. (1/3)
-
Case 3: You picked the Car. Monty eliminates either Alice or Bob. You don’t know which, but it doesn’t matter-- switching loses. (1/3)
It comes down to the fact that Monty always eliminates a goat, which is why there is only one possibility in each of these (equally probable) cases.
From another point of view: Monty revealing a goat does not provide us any new information, because we know in advance that he must always do so. Hence our original odds of picking correctly (p=1/3) cannot change.
In the variant “Monty Fall” problem, where Monty opens a random door, we perform the same analysis:
- Case 1: You picked Alice. (1/3)
- Case 1a: Monty eliminates Bob. Switching wins. (1/2 of case 1, 1/6 overall)
- Case 1b: Monty eliminates the Car. Game over. (1/2 of case 1, 1/6 overall)
- Case 2: You picked Bob. (1/3)
- Case 2a: Monty eliminates Alice. Switching wins. (1/2 of case 2, 1/6 overall)
- Case 2b: Monty eliminates the Car. Game over. (1/2 of case 2, 1/6 overall)
- Case 3: You picked the Car. (1/3)
- Case 3a: Monty eliminates Alice. Switching loses. (1/2 of case 3, 1/6 overall)
- Case 3b: Monty eliminates Bob. Switching loses. (1/2 of case 3, 1/6 overall)
As you can see, there is now a chance that Monty reveals the car resulting in an instant game over-- a 1/3 chance, to be exact. If Monty just so happens to reveal a goat, we instantly know that cases 1b and 2b are impossible. (In this variant, Monty revealing a goat reveals new information!) Of the remaining (still equally probable!) cases, switching wins half the time.
-
To me, it makes sense because there was initially 2 chances out of 3 for the prize to be in the doors you did not pick. Revealing a door, exclusively on doors you did not pick, does not reset the odds of the whole problem, it is still more likely that the prize is in one of the door you did not pick, and a door was removed from that pool.
Imo, the key element here is that your own door cannot be revealed early, or else changing your choice would not matter, so it is never “tested”, and this ultimately make the other door more “vouched” for, statistically, and since you know that the door was more likely to be in the other set to begin with, well, might as well switch!
deleted by creator
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.
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
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.
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.
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.
Quickly a game of chess becomes a never ever played game of chess before.
Related: every time you shuffle a deck of cards you get a sequence that has never happened before. The chance of getting a sequence that has occurred is stupidly small.
I’m guessing this is more pronounced at lower levels. At high level chess, I often hear commentators comparing the moves to their database of games, and it often takes 20-30 moves before they declare that they have now reached a position which has never been reached in a professional game. The high level players have been grinding openings and their counters and the counters to the counters so deeply that a lot of the initial moves can be pretty common.
Also, high levels means that games are narrowing more towards the “perfect” moves, meaning that repetition from existing games are more likely.
Multiply 9 times any number and it always “reduces” back down to 9 (add up the individual numbers in the result)
For example: 9 x 872 = 7848, so you take 7848 and split it into 7 + 8 + 4 + 8 = 27, then do it again 2 + 7 = 9 and we’re back to 9
It can be a huge number and it still works:
9 x 987345734 = 8886111606
8+8+8+6+1+1+1+6+0+6 = 45
4+5 = 9
I suspect this holds true to any base x numbering where you take the highest valued digit and multiply it by any number. Try it with base 2 (1), 4 (3), 16 (F) or whatever.
deleted by creator
maybe this will make more sense when I watch the veritasium video, but I don’t have time to do that until the weekend. How is 3x+1 unprovable? won’t all odd numbers multiplied by 3 still be odd? and won’t adding 1 to an odd number always make it even? and aren’t all even numbers by definition divisible by 2? I’m struggling to see how there could be any uncertainty in this
Just after going through a few examples in my head, the difficulty becomes somewhat more apparent. let’s start with 3. This is odd, so 3(3)+1 = 10. 10 is even so we have 10/2=5.
By this point my intuition tells me that we don’t have a very obvious pattern that we can use to decide whether the function will output 4, 2, or 1 by recursively applying the function to its own output, other than the fact that every other number that we try appears to result in this pattern. We could possibly reduce the problem to whether we can guess that the function will eventually output a power of 2, but that doesn’t sound to me like it makes things much easier.
If I had no idea whether a proof existed, I would guess that it may, but that it is non-trivial. Or at least my college math courses did not prepare me to find one. Since it looks like plenty of professional mathematicians have struggled with it, I have no doubt that if a proof exists it is non-trivial.
deleted by creator
This is my silly contribution: 70% of 30 is equal to 30% of 70. This applies to other numbers and can be really helpful when doing percentages in your head. 15% of 77 is equal to 77% of 15.
I’ve seen this one used in the news when they want to make one side of a statistic stand out.
A/100×B=A×B/100
Seeing mathematics visually.
I am a huge fan of 3blue1brown and his videos are just amazing. My favorite is linear algebra. It was like an out of body experience. All of a sudden the world made so much more sense.
His video about understanding multiple dimensions was what finally made it click for me
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.”
This is a common one, but the cardinality of infinite sets. Some infinities are larger than others.
The natural numbers are countably infinite, and any set that has a one-to-one mapping to the natural numbers is also countably infinite. So that means the set of all even natural numbers is the same size as the natural numbers, because we can map 0 > 0, 1 > 2, 2 > 4, 3 > 6, etc.
But that suggests we can also map a set that seems larger than the natural numbers to the natural numbers, such as the integers: 0 → 0, 1 → 1, 2 → –1, 3 → 2, 4 → –2, etc. In fact, we can even map pairs of integers to natural numbers, and because rational numbers can be represented in terms of pairs of numbers, their cardinality is that of the natural numbers. Even though the cardinality of the rationals is identical to that of the integers, the rationals are still dense, which means that between any two rational numbers we can find another one. The integers do not have this property.
But if we try to do this with real numbers, even a limited subset such as the real numbers between 0 and 1, it is impossible to perform this mapping. If you attempted to enumerate all of the real numbers between 0 and 1 as infinitely long decimals, you could always construct a number that was not present in the original enumeration by going through each element in order and appending a digit that did not match a decimal digit in the referenced element. This is Cantor’s diagonal argument, which implies that the cardinality of the real numbers is strictly greater than that of the rationals.
The best part of this is that it is possible to construct a set that has the same cardinality as the real numbers but is not dense, such as the Cantor set.
deleted by creator
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: .
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
A simple one: Let’s say you want to sum the numbers from 1 to 100. You could make the sum normally (1+2+3…) or you can rearrange the numbers in pairs: 1+100, 2+99, 3+98… until 50+51 (50 pairs). So you will have 50 pairs and all of them sum 101 -> 101*50= 5050. There’s a story who says that this method was discovered by Gauss when he was still a child in elementary school and their teacher asked their students to sum the numbers.
Euler’s identity is pretty amazing:
e^iπ + 1 = 0
To quote the Wikipedia page:
Three of the basic arithmetic operations occur exactly once each: addition, multiplication, and exponentiation. The identity also links five fundamental mathematical constants:[6]
The number 0, the additive identity.
The number 1, the multiplicative identity.
The number π (π = 3.1415…), the fundamental circle constant.
The number e (e = 2.718…), also known as Euler’s number, which occurs widely in mathematical analysis.
The number i, the imaginary unit of the complex numbers.The fact that an equation like that exists at the heart of maths - feels almost like it was left there deliberately.
Here’s a fun one - you know the concept of regular polyhedra/platonic solids right? 3d shapes where every edge, angle, and face is the same? How many of them are there?
Did you guess 48?
There’s way more regular solids out there than the bog standard set of DnD dice! Some of them are easy to understand, like the Kepler-poisont solids which basically use a pentagramme in various orientations for the face shape (hey the rules don’t say the edges can’t intersect!) To uh…This thing. And more! This video is a fun breakdown (both mathematically and mentally) of all of them.
Unfortunately they only add like 4 new potential dice to your collection and all of them are very painful.
Borsuk-Ulam is a great one! In essense it says that flattening a sphere into a disk will always make two antipodal points meet. This holds in arbitrary dimensions and leads to statements such as “there are two points along the equator on opposite sides of the earth with the same temperature”. Similarly one knows that there are two points on the opposite sides (antipodal) of the earth that both have the same temperature and pressure.
Also honorable mentions to the hairy ball theorem for giving us the much needed information that there is always a point on the earth where the wind is not blowing.
Maybe a bit advanced for this crowd, but there is a three-way correspondence between logic, type theory (like in programming languages), and topology. Roughly we have
Proposition ≈ Type Proof of a prop ≈ member of a Type Implication ≈ function type and ≈ Cartesian product or ≈ disjoint union true ≈ type with one element false ≈ empty type
Once you understand it, its actually really simple and “obvious”, but the fact that this exists is really really surprising imo.
You can also add topology into the mix:
