Here's a problem I don't know the answer to, so best of luck to everyone.
Suppose we have a membrane in two dimensions that is both homogeneous and isotropic. What immediately comes to my mind is villi in the small intestines. We are supplied only a vertical cross-section of the membrane, like so:
From this, we can determine the arc-length along the cross-section. What is the surface area on, say, one square-centimeter of small intestine? (By which I mean one centimeter by one centimeter punched out of the small intestines. The one square-centimeter measurement is macroscopic while the surface area I'm asking for comes from adding up all the microscopic ridges and folds and should therefore be much larger.)
I am almost certain the conversion factor should be proportional to the square of the arc-length divided by the horizontal distance spanned. Perhaps the proportionality constant is just one. Can anyone succinctly prove what it should be?
Suppose we have a membrane in two dimensions that is both homogeneous and isotropic.
Could you explain what this means specifically? Does the cross-section arc length depend on which cross-section you choose?
My impression is of a function in two variables f(x,y) with the property that for some positive a,b, we have f(x+a,y+b)=f(x,y) for all x,y. In other words, periodic in two directions.
We can assume that the villi are spaced randomly and that our single cross section represents the mean cross section.
Because this is our mean, all cross sections will have on average, the same arc length.
Let's call the arc length / length = f, our constant of proportionality.
Let's consider the area of this cross section to be f*x*dy. x = length.
Therefore, the area is just integral of this value, or f*x*y. So f*A rather than f^2*A.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
We can assume that the villi are spaced randomly and that our single cross section represents the mean cross section.
Because this is our mean, all cross sections will have on average, the same arc length.
Let's call the arc length / length = f, our constant of proportionality.
Let's consider the area of this cross section to be f*x*dy. x = length.
Therefore, the area is just integral of this value, or f*x*y. So f*A rather than f^2*A.
I was about to throw down a healthy dose of skepticism, but a quick analysis below shows that your answer is plausible. I'm still troubled by the fact that you very quickly state that the area of the cross-section is f*x*dy. Can you go into more detail on how you got this? I don't see where you took into account that the villi exhibits the same ridges along the y direction. This all seems too easy...
Here's the analysis that shows you might be correct. As a very simple example, suppose we have a single cone of base radius r and lateral distance from base to vertex L (not the height of the cone). This fails the homogeneity condition but passes the isotropy condition as long as our cross-section goes through the cone's vertex. As such, it might not be suitable for building an analogy, but I'll explore it anyway. The arc-length is s = 2*L. It can be shown that the lateral surface area is
A = 2*pi^2*r*L
The characteristic dimension of the cross-section is 2*r while the area of the cone's base is pi*r^2. Therefore, your function f becomes 2*L/(2*r) = L/r while the ratio of the areas is 2*pi^2*r*L/(pi*r^2) = 2*pi*L/r. As you predicted, the conversion between them scales linearly, with a constant factor of 2*pi, which is probably unique to the cone.
If we play the same game with a hemisphere, we get an arc-length of pi*r and a surface area of 2*pi*r^2. The ratio of the lengths is pi*r/(2*r) = pi/2 while the ratio of the areas is 2*pi*r^2/(pi*r^2) = 2. Once again, it scales proportionately, with a new factor of 4/pi.
If I'm reading OmnipotentEntity's post correctly, it is implied that the constant of proportionality is one. This seems far off for the cone, but is close to what we observe for the hemisphere.
I'm guessing it was to make up for how hard last week's challenge was. I mean, even the case N=2 was hard enough, nobody proved it rigorously (the assumption is that one of two layouts would yield the maximum) and N>2 was a complete load of nothing. Also, I don't think a lot of people like solving quartic equations.
Whereas this week's challenge can be solved doing nothing more than writing down a table.
To explain what I mean, I'll reword the problem:
Players A and B play a series of matches against each other, each match one wins and the other loses. They play until one of them wins four matches (a.k.a. "best-of-seven"); that player wins the series. Each match, you may bet X amount of money on A winning; you gain X if A wins and you lose X if B wins. Is there a series of bets that guarantees that, at series end, you end with a gain of 100 if A wins the series and you end with a loss of 100 if B wins the series?
(spoilers below)
Construct a table representing the status of the series (based on # A wins and # B wins). The amounts that you have at the end are:
A 0 1 2 3 4
B
0 100
1 100
2 100
3 100
4 -100 -100 -100 -100
Now each number in the table (other than for 4 wins by either player) is the midpoint of the number directly below and the number directly to the right. Fill in the table from bottom-right to top-left according to this rule. Then the amounts that you must have in each case are:
I was about to throw down a healthy dose of skepticism, but a quick analysis below shows that your answer is plausible. I'm still troubled by the fact that you very quickly state that the area of the cross-section is f*x*dy. Can you go into more detail on how you got this? I don't see where you took into account that the villi exhibits the same ridges along the y direction.
f*x being the length is plausible. So, I believe you're taking exception with the width being dy.
So here's my logic: if you take that cross section and pull it straight you get a line with a length of f*x. But the width does not change with this action. Also, this action smooths out the undulations in both the x and the y directions for that slice. Then we just add up all of the slices.
I could, of course, be overlooking something critical. It's early now, and late when I wrote that. And I need more coffee.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
I was about to throw down a healthy dose of skepticism, but a quick analysis below shows that your answer is plausible. I'm still troubled by the fact that you very quickly state that the area of the cross-section is f*x*dy. Can you go into more detail on how you got this? I don't see where you took into account that the villi exhibits the same ridges along the y direction.
f*x being the length is plausible. So, I believe you're taking exception with the width being dy.
So here's my logic: if you take that cross section and pull it straight you get a line with a length of f*x. But the width does not change with this action. Also, this action smooths out the undulations in both the x and the y directions for that slice. Then we just add up all of the slices.
I could, of course, be overlooking something critical. It's early now, and late when I wrote that. And I need more coffee.
I followed that logic and was pretty convinced for a little while, but now I'm skeptical again. If we start with that same slice and extrude it directly along the y direction, your logic perfectly checks out.
But, as a simple example, suppose that we extrude back along a diagonal line. In more mathematical terms, f(x,0) is our slice, and f(x,y) = f(x,0) + C*y, where C is some constant. Because it is upward-sloping, it clearly results in a greater surface area over the same bounds on y. (If you're at all bothered by the fact that the slice no longer "lays flat", just play the same game with the height zigzagging as y varies.)
Based on this, I argue that we need some sort of approximation to the function's "average derivative" along the y direction. From isotropy, the derivative along the x direction is suitable and we just need to carry out the integration. I find this path to the solution inelegant, however.
I'll carry out the derivation at some point, but for now, I'm dead tired (and the day is only starting).
I figured out the issue with my logic. I was conflating dy (the width of the slice) with ds (the bias of the slice when taking into account the slope in the y direction). When pulled flat, the width of the slice is ds not dy.
If we take this into account, we'll likely arrive at f^2*x*y, but I don't have time to demonstrate it fully right now.
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
FractalFusion, the way I understood it, you had to make the seven bets ahead of time, and if you label them from A to G (where positive numbers are for bets that the Cubs win), you get this system for the first five bets, looking at a series won in four or five games:
(This system is for the Cubs winning, but the equations for the Cubs losing are obtained by multiplying both sides by -1, like "-A-B-C-D=-100", so they are the same equations.)
Add the last four equations to get 2(A+B+C+D)+4E=400, and substitute in A+B+C+D=100 to get 200+4E=400, from which E=50; then back-substitute and add the last four equations in pairs and simplify to get A+B=50, A+D=50, C+D=50, and B+C=50, from which B=D, A=C, and C=B. Then substitute into the first equation to get A=B=C=D=25.
Two of the equations for a series won in six games look like this:
A+B+C-D-E+F=100
A+B-C-D+E+F=100
Back-substitution (from the four-or-five-game case) yields
F=100
50+F=100
and the second of these equations has solution F=50, which is inconsistent with the first one.
This all assumes that if you placed a bet for a particular game, and it isn't played because one team or the other won the series, you just get your money back.
FractalFusion, the way I understood it, you had to make the seven bets ahead of time, and if you label them from A to G...
Oh, that's how you saw it.
I don't remember if I ever saw it that way. I understood it as a betting strategy where you were allowed to make a bet just before each match/game (since sports betting generally works like that). In any case, the method I posted shows that there is at most one possible betting strategy (because the exact amount you must have at each point is determined by the numbers that you end with). If we assume you have to make all bets before the series begins, then there is a strategy if it is best-of-1 or best-of-3 (N=1 or 2), but not if it is best-of-5 or longer (N≥3).
I remember a previous Riddler puzzle not being clear on certain things (iirc it had something to do with camels and bananas). Looks like that problem is still around. Also, a few too many recent Riddler puzzles talk about American sports; this tends to add too much cultural baggage to the puzzles. At least I haven't seen the Riddler talk about American politics yet. Hopefully it stays that way.
By the way, this site has answers to many Riddler puzzles. In fact the writer found that the bets required are numbers in Pascal's triangle divided by powers of two, something I didn't try to figure out.
For this week's Riddler.
Riddler Express
The pawn can choose to go left, up, or right, each of which costs 1 move, and always increases its vertical height by 1. So it'll always take 6 moves total to reach the top. Since the promotion point is on the same file as its initial point, we therefore need equal numbers of diagonal moves, IE L and R moves, to balance out and get us back on the same column. Basic combinatorics using factorials then gives us the total amount of possible variations to such moves. Calculated as:
With 0 diagonals: EG UUUUUU, 6!/6!=1.
With 2 diagonal: EG LUUUUR, 6!/1!4!1!=5x6=30.
With 4 diagonals: EG LLUURR, 6!/2!2!2!=3x4x5x6/4=90
With 6 diagonals: EG LLLRRR, 6!/3!3!=20.
Total 1+30+90+20=141 paths.
Riddler Classic
First: Just a Knight's tour? It's been known that it can go around the entire board for a long time now.
Second: A Camel which moves 3+1, IE an even number of squares, will always land on its own colour, thus placing a boundary of at most 32 squares. Whether it can visit them all is another matter. Similarly for the Zebra/Giraffe, they can move an odd number of squares, so no immediate upper bound emerges, but I have no idea how to show whether their respective tours can be generated.
Riddler Classic
First: Just a Knight's tour? It's been known that it can go around the entire board for a long time now.
Second: A Camel which moves 3+1, IE an even number of squares, will always land on its own colour, thus placing a boundary of at most 32 squares. Whether it can visit them all is another matter. Similarly for the Zebra/Giraffe, they can move an odd number of squares, so no immediate upper bound emerges, but I have no idea how to show whether their respective tours can be generated.
It says "without letting the path intersect itself". I take it to mean that if we draw each move with a line segment (line segment joining the centers of each pair of consecutively visited squares), this path does not cross itself.
Would it kill the Riddler to put an extra sentence to explain things?
Similarly for the Zebra/Giraffe, they can move an odd number of squares, so no immediate upper bound emerges, but I have no idea how to show whether their respective tours can be generated.
A cute problem I came across recently - I believe I have a proof, which took me about an hour so some of the guys on here will easily get it in a coffee break. It concerns a remarkable but little-known property of the golden ratio, phi.
Draw up a table with two rows and indefinitely many columns. Populate the two rows like this:
Fill in the first row such that the nth entry in the first row is the integer part (aka the floor function) of n*phi. In the second row, put all the positive integers that do not appear in the first row, in ascending order.
Prove that the difference between the two numbers in the nth column is n.
I had a feeling the Riddler question requires a lot of computation to solve completely.
This is actually the kind of problem that sounds like it would require a lot of computation to solve (and, if you were to make some kind of generic version of the problem, it would probably be exponential-time / NP), but in practice, due to the limitations given in the problem, is actually very fast to calculate with some very simple optimizations.
The key is that you don't have to test all possible combinations (which would indeed be exponential-time). When building combinations, if you encounter an invalid path (in this case one that crosses a line) you can simply discard that search sub-tree completely. This cuts off the amount of branches you have to search by an enormous margin.
I haven't tested, but I suspect that you can make a program that searches for all valid paths on an 8x8 board in a fraction of a second. (It obviously becomes slower and slower if you keep increasing the board size, but I think that it would remain reasonably fast even for somewhat larger board sizes, maybe even something like 20x20 or 30x30. But this is just a gut feeling. As said, I haven't actually tested it.)
A cute problem I came across recently - I believe I have a proof, which took me about an hour so some of the guys on here will easily get it in a coffee break. It concerns a remarkable but little-known property of the golden ratio, phi.
We let an be the nth value of the first row, and bn be the nth value of the second row. [x] is the floor function, the smallest integer less than or equal to x.
In fact, these rows are a special case of a more general property as follows:
Given an irrational number α>1, there exists an irrational number β>1 (in particular, β=α/(α-1)) such that [n*α] and [n*β] partition the set of natural numbers {1,2,... }.
There are many proofs of this (as can be seen from the [url=
https://en.wikipedia.org/wiki/Beatty_sequence]Wikipedia page on Beatty sequences[/url]) but there is a geometric proof by taking a grid and drawing a line of slope α-1 through (0,0), as shown below:
Note that, since α is irrational, the line does not pass through an intersection point of the grid other than (0,0). The gray squares (the ones which contain any part of this line) form a cell path from the bottom-left up and to the right. The kth step of this path is a rightward step if k is of the form n+[n*(α-1)]=[n*α]. By reflecting the diagram about y=x, it follows that the kth step is an upward step if k is of the form n+[n/(α-1)]=[n*(α/(α-1))]=[n*β]. Since there are only upward and rightward steps, [n*α] and [n*β] partition the set {1,2,... }.
(There is a way to allow α to be a rational number, but one of the floor functions has to be replaced with a modified floor function, the smallest integer strictly less than x.)
For example, the image above uses a line of slope φ-1, and the kth step is a rightward step if k is any one of the values an (1,3,4,6,8,9,... ), and an upward step if k is any one of the bn (2,5,7,10,13,15,... ).
Letting α=φ gives (after some calculation) β=α/(α-1)=φ+1. (Note: Solving x+1=x/(x-1), x>1 gives φ as the only solution.) Therefore an=[n*φ], bn=[n*(φ+1)]=n+[n*φ], and bn-an=n.
Note that the rows can also be generated by recursively letting an be the smallest number not yet listed, then bn=an+n. (There is only one way to place all natural numbers exactly once in two ascending rows {an} and {bn} where bn-an=n.) This ties into, for example, the winning positions of Wythoff's game; the winning positions are (0,0), and (an,bn) and (bn,an) for all n.
The classic proof that you often hear that there are infinitely many primes is a simplified version of Euclid's argument. In other words, the "if there are finitely many primes, multiply all of them and add one, and you get a number that's not divisible by any of those primes, therefore there has to be at least one more prime" thingie.
I don't remember when or where I heard this "proof" for the first time, but even back then it bothered me when it just makes the claim that you get a number that's not divisible by any of the listed primes, without even an attempt at a cursory informal argument about why that's the case. It kind of takes it as a self-evident fact that that's what happens... even though I don't think that can just be glossed over like that. It's not that self-evident. It always bothers me when the "proof" is repeated by people, and that last part is just stated as some kind of self-evident trivial thing that needs no argument or explanation, and can just be taken for granted just like that. I would argue that the proof is incomplete if that last part isn't explained.
Euclid's original argument doesn't actually gloss over it, nor take it for granted, but gives a short explanation of why the claim is factual. But you seldom see this part anywhere.
Thinking of it, the argument (even the original one) actually does take something else for granted without even mentioning or referring to it, namely the fundamental theorem of arithmetic. But I suppose that such fundamental theorems can in most situations just be implicitly taken for granted without the need to explicitly mention them.
I don't think "the product of all primes up to n, plus 1, is not divisible by any of those primes" is a trivial, self-evident statement requiring no further explanation (even if it's an informal one). It also isn't just a well-established named theorem (like the Pythagorean theorem, or the fundamental theorem of arithmetic) which explanation can be omitted because of that.
It's not trivial, unless you know a good bit of arithmetic. If one wants to be rigorous, they will need to use the principle of mathematical induction, some basic divisibility theorems and then the fundamental theorem of arithmetic.
There're obviously some advanced tricks that would prove this statement as well, but I don't think they count. For instance:
if there're only finitely many primes, the sum of the inverse of all primes would not diverge. But it does diverge. Therefore, there're infinitel many primes.
Just the divisibility theorems, the fact that any positive integer greater than one has a prime factor, and the principle of proof by contradiction should be enough. Something like this:
Suppose there are finitely many primes. Then they can be enumerated as p_1, p_2, ... , p_k. Let N equal the product of p_1 to p_k.
Lemma 1: If a positive integer d is a divisor of positive integers a and b, then d divides their difference.
Proof: Since d is a divisor of a and b, we can write a = xd and b = yd where x and y are positive integers. Then |a - b| = |x - y|d and this is a multiple of d.
Lemma 2: N+1 and N have no common factors greater than 1.
Proof: Let d be a common divisor of N+1 and N. Then by the above lemma d is a divisor of 1, and the only positive integer divisor of 1 is 1.
It follows that N+1 is not divisible by any of p_1 to p_k since they all must be greater than 1. But N+1 has at least one prime factor, which leads to a contradiction.
The statement that Warp has issues with is covered by the two lemmas.
the fact that any positive integer greater than one has a prime factor
That got me thinking how to prove that.
Let's assume there exist positive integers (larger than 1) that are not divisible by any prime number. By necessity, there must exist the smallest such number, N.
If N is only divisible by itself (and 1), then it's prime by definition (and thus divisible by a prime). Therefore for the assumption to be true it has to be divisible by some other number M, which is smaller than N.
Since we established that N is the smallest non-prime-divisible number, then M must be a prime-divisible number. But if M is divisible by a prime, so is N, which leads to a contradiction in our original assumption.
That last part follows from the fact that all factors of M are also factors of N. And that's true because... hmm...
Damn, that's a bit tricky. It's intuitively very simple, but to state it methodically... There's probably a very simple proof of that, but...
I guess it's about understanding your audience.
You already accept that you can assume the reader knows things like the Pythagoras Theorem.
I don't think it's a big step to assume the reader can prove, for themselves, some intermediate lemma, even if they don't already know the lemma to be true. Of course, it depends on the lemma and the reader.
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.
So instead mathematicians tend to use a "proof sketch" - a short summary, where the reader can fill in the details as necessary. The proof sketch is useful because, to the appropriate reader, it gives exactly the right amount of information, and because it operates at the higher level, it's easier to understand. The cost of this is that it shuts out readers who aren't as familiar with the required background. (As someone who was studying for a PhD for some time, let me tell you that I found this just as frustrating as you.)
The right level for a proof is on a sliding scale depending on the reader. For example, I mostly remember the infinite prime proof as "contradiction. assume finite list of primes, construct another prime not in the list.". If I need to, I can fill in the details as required, by redoing the work.
Some well-written papers write both a sketch and a fuller proof (although even the fuller proof will assume some background). Some readers will only need the sketch, while others will slog through the fuller proof.
Amaraticando wrote:
if there're only finitely many primes, the sum of the inverse of all primes would not diverge. But it does diverge. Therefore, there're infinitel many primes.
The proof that the sum of the inverses of all primes diverges (probably?) depends on the proof of the infinity of primes, so you can't use it to prove there are infinitely many primes. That'd be a circular argument.
From this, we can determine the arc-length along the cross-section. What is the surface area on, say, one square-centimeter of small intestine? (By which I mean one centimeter by one centimeter punched out of the small intestines. The one square-centimeter measurement is macroscopic while the surface area I'm asking for comes from adding up all the microscopic ridges and folds and should therefore be much larger.)
I am almost certain the conversion factor should be proportional to the square of the arc-length divided by the horizontal distance spanned. Perhaps the proportionality constant is just one. Can anyone succinctly prove what it should be?
Note that, since α is irrational, the line does not pass through an intersection point of the grid other than (0,0). The gray squares (the ones which contain any part of this line) form a cell path from the bottom-left up and to the right. The kth step of this path is a rightward step if k is of the form n+[n*(α-1)]=[n*α]. By reflecting the diagram about y=x, it follows that the kth step is an upward step if k is of the form n+[n/(α-1)]=[n*(α/(α-1))]=[n*β]. Since there are only upward and rightward steps, [n*α] and [n*β] partition the set {1,2,... }.
(There is a way to allow α to be a rational number, but one of the floor functions has to be replaced with a modified floor function, the smallest integer strictly less than x.)
For example, the image above uses a line of slope φ-1, and the kth step is a rightward step if k is any one of the values an (1,3,4,6,8,9,... ), and an upward step if k is any one of the bn (2,5,7,10,13,15,... ).
Letting α=φ gives (after some calculation) β=α/(α-1)=φ+1. (Note: Solving x+1=x/(x-1), x>1 gives φ as the only solution.) Therefore an=[n*φ], bn=[n*(φ+1)]=n+[n*φ], and bn-an=n.
Note that the rows can also be generated by recursively letting an be the smallest number not yet listed, then bn=an+n. (There is only one way to place all natural numbers exactly once in two ascending rows {an} and {bn} where bn-an=n.) This ties into, for example, the winning positions of Wythoff's game; the winning positions are (0,0), and (an,bn) and (bn,an) for all n.
