If you don't assume any background knowledge in the reader, and try to prove everything from first principles, you end up needing hundreds of pages to prove 1+1=2. The proof is very difficult to follow, because it spends so much time in the detail that you don't get a sense of the bigger picture.
Again, I don't think that the last part of the "proof" is such a trivial everyday thing that it can be simply glossed over without so much as a brief cursory argument of why it's true.
As said, the original argument by Euclid doesn't actually gloss over it. Here's one translation of it:
"Call the primes in our finite list p1, p2, ..., pr. Let P be any common multiple of these primes plus one (for example, P = p1p2...pr+1). Now P is either prime or it is not. If it is prime, then P is a prime that was not in our list. If P is not prime, then it is divisible by some prime, call it p. Notice p can not be any of p1, p2, ..., pr, otherwise p would divide 1, which is impossible. So this prime p is some prime that was not in our original list. Either way, the original list was incomplete."
(Granted that this version just makes the claim that "otherwise p would divide 1" without explain why, but at least it's much closer to a complete proof.)
"Notice p can not be any of p1, p2, ..., pr, otherwise p would divide 1"
Suppose p is some of the listed p's and p is a divisor of p1p2...pr+1. That means that
p*A = p1p2... * p * ...pr+1
p*A - p1p2... * p * ...pr = 1
p*(A - B) = 1
p*k = 1 (impossible)
Suppose p is some of the listed p's and p is a divisor of p1p2...pr+1. That means that
p*A = p1p2... * p * ...pr+1
p*A - p1p2... * p * ...pr = 1
p*(A - B) = 1
p*k = 1 (impossible)
It becomes much clearer when shown like that. But I have seldom seen that being explained in the "proof" in practice.
Btw, about an earlier post I made, for some reason I have a really hard time proving this:
"If the positive whole number M divides the positive whole number N, then all the factors of M are also factors of N."
(which would be the final step in the proof that all positive whole numbers larger than 1 have at least one prime factor.)
This sounds like a completely intuitive, trivial and self-evident thing, but I have a hard time figuring out a way to "prove" it methodically. I suppose there's a reason why I'm not a mathematician.
"If the positive whole number M divides the positive whole number N, then all the factors of M are also factors of N."
It helps to break it down to fundamental definitions.
By definition, an integer x divides an integer y if there exists an integer k such that y=kx. We also call x a factor of y.
So if M divides N, then there exists an integer k such that N=kM. Let d be a factor of M. Then there exists an integer b such that M=bd. So then N=kM=kbd=d(kb), and so d is also a factor of N, as required.
It would be sometimes useful to have a concise name for what I otherwise call "high school math" (or, dare I say, "practical math"; at least practical in graphical programming).
Obviously this goes beyond mere arithmetic, but not too far into calculus (and, in practice, calculus can be left out completely). It would include things like analytic geometry (without going to complex subjects like topology), vector math and trigonometry, as well as equation solving.
I suppose "elementary algebra" might encompass most of that, although I'm not sure it encompasses analytic geometry. So maybe "elementary algebra and analytic geometry"?
A nice problem from the brazillian mathematical olympiad (2016, senior and junior).
Let ABC be a triangle. The line r is the bisector of ∠ABC and line s is the bisector of ∠ACB. D is onto r and AD||s. E is onto s and AE||r. The lines BE and CD meet at point F. I is the incenter of ABC. Prove that F, A and I are collinear if, and only if, AB = AC.
When programming, sometimes I need to select randomly from a set of elements, but the probability of each element being chosen is not the same. Instead, each element is specified a probability factor.
Normally probability factors add up to 1.0 (or to 100% if they are expressed as percentages), but this is quite inconvenient and not very practical. If you were to add or remove an element, or change the probability factor of any of the elements, you would need to go and manually calculate and adjust the factors of all the other elements. (Obviously the more elements there are, the more tedious work it would be.)
Thus it's much more convenient to just specify an arbitrary weight value for each element, and use them as a relative factor compared to all the weights. In other words, the magnitude of the given weight relative to the sum of all weights.
For example, if you have, let's say, five elements, you could define their probability weights as [3, 1, 10, 8, 4]. You can then calculate the actual probability factor of any element by dividing its weight by the sum of all weights. For example, the probability for the first element would be 3/(3+1+10+8+4) = 0.1154 = 11.54%.
I wonder if there's a name for that operation. It kind of resembles calculating a weighted average, but we are not calculating the average of the elements here, but rather the relative weight of a given element in relation to all the elements, given their weights.
The article linked from the Riddler Classic problem says the maximum board size is 6x6, but I haven't bothered to figure out a draw configuration for that size, or to check why it doesn't work for larger sizes: http://fivethirtyeight.com/features/dont-throw-out-that-calendar/#ss-1Amaraticando wrote:
A nice problem from the brazillian mathematical olympiad (2016, senior and junior).
Let ABC be a triangle. The line r is the bisector of ∠ABC and line s is the bisector of ∠ACB. D is onto r and AD||s. E is onto s and AE||r. The lines BE and CD meet at point F. I is the incenter of ABC. Prove that F, A and I are collinear if, and only if, AB = AC.
If AB=AC, then angles ACB and ABC are congruent, and then, angles ACE and ABD are congruent.
Marking the intersection between AC and BD as G, and between AB and CE as H, by ASA we have triangles CAH and BAG congruent, which means CH=BG, AH=AG, and the angles AHC and AGB are congruent.
Then angles AHE and AGD are congruent, and by alternate interior angles, angles HAD and GAE are congruent. Then because m(HAD)=m(HAG)+m(GAD) and m(GAE)=m(HAG)+m(HAE), it follows by elimination that angles GAD and HAE are congruent; then by ASA, triangles GAD and HAE are congruent, which means AE=AD.
Then by SAS, triangles ABE and ACD are congruent, which means angles ABE and ACD are congruent; by adding congruent angles, this means that angles FBC and FCB are congruent, so FB=FC.
This means that angles BAC and BFC are vertex angles of the respective isosceles triangles BAC and BFC, so their angle bisectors are also the perpendicular bisector of the base, BC, which means that F, A, and I are collinear.
---
Conversely, if F, A, and I are collinear, then angles CAF and BAF are congruent (being supplementary to the congruent angles CAI and BAI). Angles DAE and DIE, being opposite angles in a parallelogram, are congruent; by alternate interior angles, angles IAD and EIA are congruent, as are angles AID and IAE.
Again marking the intersection of AC and BD as G, and AB and CE as H, it is clear that by SAS, triangles HAI and AIG are congruent, so angles AHI and AGI are congruent, so their supplementary angles AHE and AGD are congruent. Then by alternate interior angles, angles HAD and GAE are congruent, and by subtracting a common angle, angles HAE and GAD are congruent; then by adding congruent angles, angles EAI and DAI are congruent; their supplementary angles, EAF and DAF, are also congruent.
Then AI is the base of two congruent isosceles triangles EAI and DAI, so EA=DA and EI=DI. By ASA, triangles EAF and DAF are congruent, so EF=DF and angles EFA and DFA are congruent, which means AI, which F is also on, is actually the bisector of angle BFC.
By ASA, triangles HAE and GAD are congruent, so AH=AG and EH=DG. Also by ASA, triangles AHI and AGI are congruent, so HI=GI. By alternate interior angles, angles EIB and DIC are congruent. By adding congruent angles, angles CEF and BDF are congruent, and then by ASA, triangles CEF and BDF are congruent, which means CE=BD, and by subtracting congruent line segments, CH=BG.
Then by ASA, triangles HIB and GIC are congruent, so HB=GC; adding congruent segments, AB=AC.
Because 2100 *isn't* a leap year, we can have a 40 year gap in the otherwise regular 28 year cycle of the calendar. Which means the only possible years are 2072, 2076, 2080, 2084, 2088
Of those 5, we can check each and eliminate the ones that cycled in 1900, 1800, etc in the same way.
2080 is the same as 1872 which cycled 40 years through 1900.
2084 is the same as 1876 which cycled 40 years through 1900.
2088 is the same as 1880 which cycled 40 years through 1900.
2076 is the same as 1772 which cycled 40 years through 1800.
2072 is unique in that it couldn't cycle through 1900, 1800. It normally would have done the 40 year cycle in 1700, but because England adopted the Gregorian calendar in 1752 I guess it doesn't count.
This is what 2072's calendar looks like:
https://www.timeanddate.com/calendar/?year=2072&country=1
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
The article linked from the Riddler Classic problem says the maximum board size is 6x6, but I haven't bothered to figure out a draw configuration for that size, or to check why it doesn't work for larger sizes: http://fivethirtyeight.com/features/dont-throw-out-that-calendar/#ss-1
It is a computation question, pretty much.
There are four base solutions for draw configurations (three if you consider color switching the same), invariant under rotation and reflection:
The C program which I used to confirm this is at http://pastebin.com/LjigMYGX .
The site at http://www.di.fc.ul.pt/~jpn/gv/hip.htm says that there are no 7x7 (or 6x7) draw configurations. The program I posted above confirms this for 7x7 if you replace "#define SIZE 6" with "#define SIZE 7".
Also,
The Riddler wrote:
On snowy afternoons, you like to play a type of solitaire game. You deal out cards from a randomly shuffled standard deck, face up, into a pile. With each card you deal, you say the faces of the cards, in order: ace, two, three, up to king, then starting over at ace. If you get through the deck without what you say ever matching what you deal, you win. What are the chances that you win? They’re about 1.6 percent.
In a standard deck, there are four cards of each rank — four aces, four twos, four threes and so on. So when you randomize the deck by shuffling it, there is a 4/52 (or 1/13) chance that you will place a card in a position that will match what you eventually speak aloud. Put another way, before you start the game, there is a 12/13 chance that any card will not match what you will speak aloud. In order to win, you have to get through the deck with zero matches, so you need to “win” these 12/13 shots 52 times in a row. The chances of that are (12/13)52≈0.01557, or about 1.6 percent. Good luck!
is wrong based on my understanding of the problem, but I don't care to figure out the exact number.
Edit: Close enough, but random trials (C++ program at http://pastebin.com/YDSWF9UR) appear to give a winning percentage of about 1.62%.
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
FractalFusion wrote:
Also,
The Riddler wrote:
On snowy afternoons, you like to play a type of solitaire game. You deal out cards from a randomly shuffled standard deck, face up, into a pile. With each card you deal, you say the faces of the cards, in order: ace, two, three, up to king, then starting over at ace. If you get through the deck without what you say ever matching what you deal, you win. What are the chances that you win? They’re about 1.6 percent.
In a standard deck, there are four cards of each rank — four aces, four twos, four threes and so on. So when you randomize the deck by shuffling it, there is a 4/52 (or 1/13) chance that you will place a card in a position that will match what you eventually speak aloud. Put another way, before you start the game, there is a 12/13 chance that any card will not match what you will speak aloud. In order to win, you have to get through the deck with zero matches, so you need to “win” these 12/13 shots 52 times in a row. The chances of that are (12/13)52≈0.01557, or about 1.6 percent. Good luck!
is wrong based on my understanding of the problem, but I don't care to figure out the exact number.
Edit: Close enough, but random trials (C++ program at http://pastebin.com/YDSWF9UR) appear to give a winning percentage of about 1.62%.
A way to proof the (12/13)52 answer is wrong is too look at the denominator of the chance.
There is a total of 52 cards. Thus, the amount of ways they can be organized in is 52!. When you play the game, you will win when the cards are displayed in X of these ways, and you will lose when the cards are displayed in (52! - X) of these ways. Thus, the fraction X/52! represents this chance, and has both an integer nominator and denominator. 52! is a multiple of 134, but not of 135. So, since the fraction (12/13)52 is irreducible, it can't be equal to X/52! if X is an integer.
is wrong based on my understanding of the problem, but I don't care to figure out the exact number.
Edit: Close enough, but random trials (C++ program at http://pastebin.com/YDSWF9UR) appear to give a winning percentage of about 1.62%.
The flaw in the reasoning is pretty obvious if you consider a card with only 2 ranks (eg, ace and two) and only 2 suits. The Riddler website would say that we have 50% of probability to be wrong in the 1st card, 50% in the 2nd card, etc. The chance of winning would be (1/2)^4 = 1/16
However, by listing the possible outcomes:
1 1 2 2 lose
1 2 1 2 lose
1 2 2 1 lose
2 1 1 2 lose
2 1 2 1 win
2 2 1 1 lose
win = 1/6 ≠ 1/16
2084 is the same as 1876 which cycled 40 years through 1900.
I was looking for other leap years starting on Saturday and overlooked that one; the way I figured it was just that the leap years starting on Friday (including 2072) had their previous 40-year gap the longest time ago, among those leap years in the 21st century with 40-year gaps.
The exact value of the probability for the cards is:
4610507544750288132457667562311567997623087869 /
284025438982318025793544200005777916187500000000
to 30 decimal places:
0.0162327274671946367481295565133
I solved it by using the OEIS, apparently this problem is related to the Dinner-Diner matching problem.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
Speaking of the Riemann zeta function, I have had for some time now an interest in understanding the Riemann hypothesis. Just out of curiosity, as a little "hobby project". I was wondering if someone could help me with it.
In order to understand the hypothesis, I first need to understand the Riemann zeta function. In order to understand said function, I need to understand analytic continuations. And the topic already becomes really complicated (not to talk about how complicated the zeta function itself is.)
Speaking of the Riemann zeta function, I have had for some time now an interest in understanding the Riemann hypothesis. Just out of curiosity, as a little "hobby project". I was wondering if someone could help me with it.
In order to understand the hypothesis, I first need to understand the Riemann zeta function. In order to understand said function, I need to understand analytic continuations. And the topic already becomes really complicated (not to talk about how complicated the zeta function itself is.)
While that is indeed a good starting point for understanding qualitatively what the concept of an analytic continuation is, it's not sufficient. What you really need is to take a course in complex analysis.
I don't know your mathematical background, but you only need up until Multivariable Calculus and the basics of Complex Numbers (polar form, roots of unity, etc) before you can tackle Complex Analysis. I've been eyeing taking the Complex Analysis course at my university, so I've watched a lecture series on Complex Analysis on Youtube. Specifically, the one starting from this video: https://www.youtube.com/watch?v=exTsBIQoxcI
You should probably start with this one though, it's more indepth and has what you're interested in (analytic continuations): https://www.youtube.com/watch?v=BruPj2mUGMo&list=PLun8-Z_lTkC5wjZ-8TH99y3htILDwlji5
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
The Riemann Hypothesis was always a bit weird for me, as unlike other famously unsolved conjectures of its kind there doesn't seem to be a heuristic reason why it should be true. I understand what the question is asking but it just doesn't seem at all obvious that the zeroes of the function have any reason to all line up as they apparently do.
Compare that to Goldbach's conjecture, for example. It's easy to see that the higher you take your number n, the more possible pairs of numbers (n/2) you could add together to achieve that number; and that n/2 grows much, much faster than the "probability" they will both be prime decreases (ln(n)^2 a consequence of the prime number theorem). Hence you expect the probability that there will be at least one suitable pair to approach certainty very rapidly, and once you've checked up to a thousand you conclude that it's very unlikely there's a counterexample.
Now of course that's not a proof because probability is not certainty and the above assumes that the primes are randomly distributed, which they most certainly are not. But you can see how it's plausible. With the Riemann Hypothesis, it's more "look at the first few zeroes, they all lie on this line" with, for me at least, no deeper intuition as to why that should be so.
The Riemann Hypothesis was always a bit weird for me, as unlike other famously unsolved conjectures of its kind there doesn't seem to be a heuristic reason why it should be true. I understand what the question is asking but it just doesn't seem at all obvious that the zeroes of the function have any reason to all line up as they apparently do.
You don't seem to be the only one thinking that. Apparently, John Littlewood, an expert in mathematical analysis in the early 20th century, said that he believed it was false for practically that reason (there was no real reason for it to be true), and Eric Landau, an expert in complex analysis, once posed why it should be true to another mathematician.
Speaking of the Riemann zeta function, I have had for some time now an interest in understanding the Riemann hypothesis. Just out of curiosity, as a little "hobby project". I was wondering if someone could help me with it.
In order to understand the hypothesis, I first need to understand the Riemann zeta function. In order to understand said function, I need to understand analytic continuations. And the topic already becomes really complicated (not to talk about how complicated the zeta function itself is.)
I always like to think of new math concepts as generalizations of old ones. In the case of analytic continuations, I imagine it as related to the geometric series.
I expect you are aware that
1 + x + x^2 + x^3 + ... = 1/(1-x)
for |x|<1, right? Well, consider graphing both sides of the equation. On the left hand side, you get a function that is well-behaved only for |x|<1. Outside this range, it blows up. This is easily seen using complex analysis because there is a pole at x = 1. Using real analysis, we just say that the domain of any series cannot extend past a vertical asymptote. It's left as an exercise to the reader to show that the radius of convergence is a "true radius" in the sense that if the series cannot extend past R to the right, nor can it extend past the same distance R to the left.
Anyway, we look at this graph and lament that its left end "looks" like it's begging for a continuation. In particular, although the graph blows up at x=1 and therefore the series cannot extend past that point (well, actually, it can, but never mind that), nothing seems to be stopping it from continuing leftward, past x = -1. The right hand side of our equation provides exactly such a continuation. The two functions are perfectly identical in all but one aspect: their domain.
Often, it's taught that the left hand side is the Taylor series of the right hand side and the radius of convergence is derived as an exercise. Here, I'm working in the opposite direction and I argue that the left hand side is practically begging to be written as the right hand side. The right hand side is merely a generalization of the left.
If you'd like a slightly better example that doesn't depend on asymptotes on the real domain, consider the function 1/(1+x^2). Famously, its Taylor series,
1 - x^2 + x^4 - x^6 + ...,
only converges for |x|<1. This is rather startling, since the function seems well-behaved throughout and there aren't any asymptotes. Again, learning some complex analysis brings it within your grasp.
thatguy wrote:
Now of course that's not a proof because probability is not certainty and the above assumes that the primes are randomly distributed, which they most certainly are not. But you can see how it's plausible. With the Riemann Hypothesis, it's more "look at the first few zeroes, they all lie on this line" with, for me at least, no deeper intuition as to why that should be so.
It's funny you should mention Goldbach's conjecture. I've heard it said that a single negative result for the Riemann hypothesis would "wreak havoc" on the distribution of prime numbers. While we all know that prime numbers are not distributed truly randomly, apparently the Riemann hypothesis is connected to the idea that the distribution of primes is characterized by certain qualities shared closely with random numbers. In that sense, your post is rather ironic because it boils down to the following argument:
"I believe Goldbach's conjecture to likely be true because it would almost certainly be so if the primes were randomly distributed.
One consequence of the Riemann hypothesis is that the primes are practically randomly distributed.
I'm skeptical of the Riemann hypothesis."
By invoking the apparent randomness of prime numbers, you unfairly favor one theory over the other.
To be perfectly clear, no one has explicitly shown that the Riemann hypothesis is equivalent to Goldbach's conjecture. Apparently, there is some suggestive evidence in its favor, however. It's just funny that the two are intrinsically linked to the idea of prime numbers being "random".
Well, to a physics graduate and amateur/recreational mathematician like myself, it's not obvious why the Riemann Hypothesis would imply that the primes are "randomly" distributed (for a suitable definition of "random"). The only link that I can understand that it has to primes at all is the Euler identity:
infinite_sum(1/n)^s = infinite_product(p^s/p^s-1)
where p are the prime numbers. It's not obvious how you go from there to saying that the zeta function has anything to do with the distribution of primes. Of course, other mathematicians have done this legwork but it's hardly trivial, is it?
Well, to a physics graduate and amateur/recreational mathematician like myself, it's not obvious why the Riemann Hypothesis would imply that the primes are "randomly" distributed (for a suitable definition of "random"). The only link that I can understand that it has to primes at all is the Euler identity:
infinite_sum(1/n)^s = infinite_product(p^s/p^s-1)
where p are the prime numbers. It's not obvious how you go from there to saying that the zeta function has anything to do with the distribution of primes.
As a fellow physics graduate, ya got me. I only know what I see on popular websites and online discussions like this one. I suggest you do the same thing I did and Google "Riemann hypothesis distribution of primes" and peruse what pops up. I think it's fascinating stuff but I don't have much patience for it since it's difficult for me to understand, not all that practical, and being studied by people orders of magnitude smarter than I am.
The prime number theorem proof outline on Wikipedia is somewhat understandable (this is coming from a person who hasn't yet started uni), and involves the zeros of the Riemann zeta function (subject of the Riemann hypothesis).
What is the integral of sin(x)*cos(x) dx ?
a) sin2(x) / 2 + C
b) -cos2(x) / 2 + C
c) -cos(2x) / 4 + C
This got me thinking that this is actually a great practical demonstration of why that +C in the result of integration is so important, especially given that many people lazily leave it out.
If you leave out the +C, one could incorrectly conclude that eg.
sin2(x) / 2 = -cos(2x) / 4
but of course this isn't true. However, it is true that
sin2(x) / 2 + C1 = -cos(2x) / 4 + C2
for properly chosen values of C1 and C2.
So, two questions:
1) When one is integrating something like sin(x)cos(x) dx, how and why does one come up with one of the above answers, and not the others? (It has been so long since I did any integration in high school that I don't even remember how you integrate sin(x)cos(x) dx.)
2) Small challenge: For which values of C1, C2 and C3 does it hold that
sin2(x) / 2 + C1 = -cos2(x) / 2 + C2 = -cos(2x) / 4 + C3
