Posts for FractalFusion

Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Someone asked about how the Nicovideo monthly ranking works, so I'll do my best to explain. ---- To qualify for this ranking, the video must: - be uploaded during the month (Japan time), - be relevant to TAS, and - not be a compilation video or repost. If multiple videos uploaded in the same month are "part of the same TAS", at most one of the videos can qualify for the ranking. ---- Each video is ranked by number of points on the 6th of the next month at midnight (Japan time) as follows: Points = Views + Comments + (20 x Mylists) (note: The comment count and comments only appear if you go to the bottom of the page and set Region/地域 to Japan/日本 and Language/言語 to Japanese/日本語) ---- The ranking lists the top 30 ranked TAS videos as well as 10-12 other TAS videos (called "Pickups") of the organizer's choice. A small snippet of the video is shown, along with information such as title, author, points, rerecord count (if available), Nicovideo tags, and such. The monthly ranking video appears approximately by the 10th of the next month. It is generally expected that the community gives a TAS video the "TAS" tag to make it easier to find. There is also a Nicovideo yearly ranking which runs on a similar idea but is bigger.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Warp wrote:
But now enters the color photography using color filters problem: We have a monochromatic camera, and we take three photos with it, with a red, a green and a blue filter, and we combine them and we get a color photograph. And violet colors show up just fine! How?
I assume that by "violet colors" you are referring to violet light (400-440nm) and not digital (or otherwise) renderings of purple colors. Actually, it depends on the colors that the filters let through (since the red/green/blue filters only form an approximation when combined together). Perhaps violet colors show up just fine because the "blue" filter is actually closer to violet than it first appears (maybe it filters 400-440nm light, rather than the 470-500nm that is typical of blue). Or maybe the blue filter allows a wider range than it appears at first glance.
Warp wrote:
It is my understanding that this is because the frequency of violet is twice that of (low) red, and there's a resonance effect going on
p4wn3r wrote:
When it receives violet, the blue cone is stimulated because its frequency is not far below violet, and the red one as well, since it's stimulated by the second harmonic
I've never heard of a resonance effect or harmonic for electromagnetic waves before, but I don't know about it. I only know about resonance and harmonics in sound waves (e.g. vibrating string). The typical human sees color using three cones, often called "red", "green", and "blue". The typical sensitivities of the cones are shown in the image below, taken from the Color vision page on Wikipedia: In this model, violet light mostly stimulates the blue cone, compared to the red and green cones. Note that the peak of the blue cone is in the violet range. I have seen some other models where the red cone stimulation actually increases in the violet range, but I don't know if they are accurate or not. Searching the internet reveals that there is a disagreement in this area.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
July 2018: Link to video Ranking in detail. Dr. Mario scores a 19-hit combo! Apparently, there was a crazy frame war, and yes, there were even more Dr. Mario videos not included in the ranking.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Riddler Classic this week is as follows: ------------------ I flip a coin. If it’s heads, I’ve won the game. If it’s tails, then I have to flip again, now needing to get two heads in a row to win. If, on my second toss, I get another tails instead of a heads, then I now need three heads in a row to win. If, instead, I get a heads on my second toss (having flipped a tails on the first toss) then I still need to get a second heads to have two heads in a row and win, but if my next toss is a tails (having thus tossed tails-heads-tails), I now need to flip three heads in a row to win, and so on. The more tails you’ve tossed, the more heads in a row you’ll need to win this game. I may flip a potentially infinite number of times, always needing to flip a series of N heads in a row to win, where N is T + 1 and T is the number of cumulative tails tossed. I win when I flip the required number of heads in a row. What are my chances of winning this game? (A computer program could calculate the probability to any degree of precision, but is there a more elegant mathematical expression for the probability of winning?) ------------------ As for an infinite series that gives the exact answer but not in closed or numerical form: It's easy to write down for the probability of losing this game. To lose the game, you have to fail to flip heads by flipping a tails, then fail to flip two heads in a row by flipping a tails, then fail to flip three heads in a row by flipping a tails, etc. This gives (1/2)(3/4)(7/8)(15/16)..., and the probability of winning is one minus this. As for whether this series can be evaluated easily: It doesn't converge too quickly, but it does converge to a number > 0. There is a way to show this as well as improve on this. First, (1/2)(3/4)(7/8)(15/16)... is the series (1-x)(1-x^2)(1-x^3)... evaluated at x=1/2. Then (1-x)(1-x^2)(1-x^3)... = 1 - x - x^2 + x^5 + x^7 - x^12 - x^15 + x^22 + x^26 - x^35 - x^40 + x^51 + x^57 - ... , based on this theorem, the Pentagonal Number Theorem. This not only converges much faster than the above infinite product (provided |x|<1) but also has an effective bound on the error from the rest of the terms. Evaluating at x=1/2 up to the term x^40 in WolframAlpha gives approximately 0.28878809508660, accurate to 14 decimal places, since the error is bounded by (1/2)^50. This is the losing probability, so the winning probability is about 0.71121190491340. I don't have a way to evaluate this exactly in closed form (without infinite sum or product); I thought at first the problem implied there was such a form but I'm not so sure now.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Apparently, the centrifuge problem was posted in a blog a month ago, before the Riddler came up with it. - That page expresses the solution in a neat way: you can safely run K samples in N buckets if and only if both K and N-K are expressible as a sum of prime divisors (possibly with repeats) of N. - You may have noticed that one of the images gives a centrifuge with 20 buckets. So much for centrifuges being a multiple of 6. At least it's an even number. - The proof uses this result that if K Nth roots of unity (possibly with repeats) add up to 0, then K is expressible as a sum of prime divisors of N. - It turns out I was wrong about all safe alignments being a union of evenly-spaced rings. For example, if N=30 and we number buckets around the circle, then we can place samples in the buckets 5, 6, 12, 18, 24, 25 and it all balances out. However, note that we can get this alignment by taking a ring of 5 and a ring of 3, and removing a ring of 2. Indeed, the paper above says that we can "add" and "subtract" these rings to get any sum of roots of unity that adds to 0, so I wasn't that far off.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Warp wrote:
I'm not sure if there should additionally be the requirement that no three floor touch points should be collinear.
If the floor touch points are collinear but the centers of the spheres are not, then there is only one tangent plane. In the case where the floor touch points are collinear, that means one of the spheres (call it sphere A) is tangent to the cone inscribing the other two spheres. For there to be another tangent plane, that means sphere A must be tangent to the cone at a second point; if it is not (which is the case when the centers of the spheres are not collinear), then there is no second tangent plane.
p4wn3r wrote:
This week's Riddler classic puzzle kinda disappointed me, it's a simple Hamiltonian path problem, which can also be solved with dynamic programming.
Actually, you are expected to use pen and paper to solve it; that's why the Riddler put it as "a puzzle perfect for doodling during a boring class or meeting". Think of it like a knight's tour problem on a small board. You can program for a solution, but what's the point? There are many solutions; there's a solution I found which is a closed tour and is 180-degree symmetric: 12 02 20 09 03 22 16 05 25 15 19 08 13 18 07 11 01 21 10 04 23 17 06 24 14 Riddler Express is pretty open-ended (and therefore too difficult as an Express problem) this time around. I'll post it here, but I made a few edits to the problem statement in bold and square brackets in case it isn't clear what a centrifuge is or what it does. ------- A centrifuge [has a number of slots or "buckets" that are arranged in a circle, some of which have sample bottles placed in them. It] needs to be perfectly balanced along every axis before being run [; that is, the samples MUST be aligned so that their center of mass is in the exact center]; otherwise, the torque will damage the internal rotor. If a centrifuge has N equally spaced buckets, some of which you’d like to fill with K samples, and all samples are of equal weight, for what values of K can [the samples be aligned so that] all the samples [can] be spun in the centrifuge safely? Hint: You can run seven samples in a 12-bucket centrifuge. But you cannot run 10 samples in a 21-bucket centrifuge. ------- You can model this with points on the unit circle (or roots of unity in the complex plane) whose average is (0,0). Now it is clear that with N buckets, you can fill it with M>1 samples whenever M divides N; just place the samples so that they form a "ring" of M equally spaced samples. So the problem is probably(*) to find a union of such rings in the N buckets so that their sum is K. With 12 buckets you can put 7 samples safely (3+2+2). However, with 21 buckets you can't do that with 10 samples even though 10=7+3, since, once you take a ring of 7 samples, you can no longer fit a ring of 3. I think this is because 21 is a product of two primes, whereas 12 isn't. There are a few limited cases I can figure out, such that if N=2,3,4 or a multiple of 6, then you can put any number of samples from 2 to N-2 (this is why centrifuge buckets come in multiples of 6). If N is a prime power, or a product of two primes, then K has to be a multiple of a prime factor of N. Other than that, it seems difficult to express in general what the solution is. In conclusion, Riddler Express and Riddler Classic were switched around this week by accident. :) (*) I think, but cannot prove, that all safe alignments are a union of such rings.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Warp wrote:
The newest Numberphile video made me think of this hypothesis: Three non-overlapping spheres (not necessarily of the same radius) are on a floor (ie. a plane). As long as the points where the spheres touch the floor are not collinear, there will exist another plane that also touches all three spheres (in such a way that all three spheres will be on the same side of this second plane). Can this be proven?
Take a plane that goes through the centers of the spheres. If we reflect across this plane, then the spheres remain the same (by symmetry). So the reflection of the floor through the reflection plane gives another plane (the "ceiling") that touches all three spheres. This "ceiling" is distinct from the floor as long as the reflection plane is not the same as the floor (which it is obviously not) and is not perpendicular to the floor (which only occurs when the contact points on the floor are collinear but the centers of the spheres are not).
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
Language: cpp

for (int i=1; i<99>= 0)
I have never seen this type of code before in a for statement. Specifically the i<99>= 0 part. I was unable to get it to compile. The Riddler doesn't always specify things clearly, so I did the version where you minimize the average, as opposed to minimizing the worst case (maximum), as p4wn3r did. The code is based on p4wn3r's code and is as follows:
Language: cpp

#include <stdio.h> #include <algorithm> using namespace std; int v[4][100]; int main() { for (int i=0; i<=99; i++) { v[0][i] = i; } v[1][0] = v[2][0] = v[3][0] = 0; for (int c1=2; c1<=99; c1++) { for (int i=1; i<=99; i++) { if(i<c1) v[1][i] = v[0][i]; else v[1][i] = min(v[0][i],v[1][i-c1]+1); } for (int c2=c1+1; c2<=99; c2++) { for (int i=1; i<=99; i++) { if(i<c2) v[2][i] = v[1][i]; else v[2][i] = min(v[1][i],v[2][i-c2]+1); } for (int c3=c2+1; c3<=99; c3++) { for (int i=1; i<=99; i++) { if(i<c3) v[3][i] = v[2][i]; else v[3][i] = min(v[2][i],v[3][i-c3]+1); } int score=0, max=0; for(int i=1; i<=99; i++) { score=score+v[3][i]; if(v[3][i]>max) max=v[3][i]; } if(score<=389) { printf("1 %d %d %d max:%d sum:%d\n",c1,c2,c3,max,score); } } } } return 0; }
(To solve for minimizing the worst case, replace if(score<=389) with if(max<=6).) The result is:
1 5 18 25  max:6  sum:389
1 5 18 29  max:6  sum:389
So both (1,5,18,25) and (1,5,18,29) give the minimum average of 3.89 coins. Note that both of these also minimize the worst case of 6 coins.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Looks pretty good, p4wn3r. You got a numerical value that is very close to what I got. I figured out the exact value of the speed that your ship has to go compared to the sub (relative velocity). It is sqrt((1/x2) + 1), where x is the only solution to -ln(x)/x=pi/2. WolframAlpha gives x≈0.474541 and so that gives an answer of sqrt((1/x2) + 1 ≈ 2.332533. How I did this: Model the problem such that your ship starts at (-1,0), the sub starts at (0,0), and the port is at (1,0). Assume the sub has speed 1 and your ship has speed b. Note that b is the answer to this problem. The ship's path, as p4wn3r guessed, is indeed a line from (-1,0) meeting the sub's circle expanding away from (0,0), followed by a logarithmic spiral to the port at (1,0). Now the transition point where the line and the expanding circle meet can't just be anywhere, but must be such that your ship's radial speed at that point must be 1 outward, since the circle is expanding outward at a speed of 1. I claim that this point must lie on the y-axis. Indeed, the following image shows why: At the transition point C, your ship's radial speed is 1 and, with the ship's velocity vector having a magnitude of b, we form right triangle EDC. However, if we call distance BC as r, then the distance of AC is br. Since points A,C,E are collinear as well as B,C,D, the two triangles ABC and EDC are similar, so ABC is a right triangle with legs of 1 and r and hypotenuse br. Note that as your ship travels along AC, the sub's circle grows along BC with the same y-coordinate, so point C is indeed the first point where they meet. By using the Pythagorean Theorem and rearranging, we get our first identity 1/r = sqrt(b2-1). (*) Now after your ship meets the edge of the sub's circle, your ship must always maintain a radial speed of 1 while having a speed of b. Thus the tangential speed is sqrt(b2-1), which is 1/r from the identity (*), which depends only on b. (Note that constant radial and tangential velocities at every point is a characteristic of a logarithmic spiral.) Since the tangential speed is distance times angular speed, we get 1/r = x*θ'(x), where θ'(x) is the angular speed and x is the distance travelled by the sub (alternatively, the radius of the sub's circle). So θ'(x) = 1/r * 1/x, so then by integration, θ2 - θ1 = 1/r * (ln(x2) - ln(x1)). From the above image, we know that your ship must travel this spiral through the angle CBF, which has an angle of θ2 - θ1 = pi/2. Now the initial distance of the spiral is x1=r and the final distance is x2=1, so this simply gives pi/2 = 1/r * (-ln(r)). Then we simply solve for the variables r and b. WolframAlpha gives r≈0.474541, and plugging into (*) and solving gives b≈2.332533, which is our answer. The following image (created from desmos.com) shows the path your ship must take at speed b≈2.332533 that allows you to reach port safely. The blue part is the straight line and the red part is the logarithmic spiral. Note that the transition between blue and red occurs at the point (0,r) ≈ (0,0.474541).
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
I'm working on the Riddler Classic problem this week, worded as follows: ---- An enemy submarine determined to sink your ship is sitting, torpedoes armed, exactly halfway between you and your home port. The submarine submerges to some fixed depth, and your ship now has no further information about its position. The enemy sub has to be directly underneath your ship to sink it — but the sub can track your moves with precision and respond efficiently. If your ship is fast enough, though, you will be able to set a wide course around the sub and reach port safely. How much faster than the sub does your ship have to be to guarantee you can avoid the sub and get home? ---- Because your ship has no information about the sub's position except its starting point, the only way to guarantee that your ship reaches home port safely is to take a patch to home that avoids an increasing circle (centered on the sub's initial position) representing where the sub could be. So your ship has to be at least twice as fast (it has to reach home port before the increasing circle does), and your ship can easily reach home port if it is pi times as fast (by going along a 180-degree circular path to home port). So the true answer is somewhere in between. I'm currently trying to figure out what the path looks like (it depends on how much faster your ship is) but the problem seems somewhat difficult. Perhaps it can be solved like the fox and duck problem that we figured out before.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Warp wrote:
The answer given to this is that 1 is the result of the empty product. I suppose this makes sense when you consider that every natural number can be expressed as: n = 2p1⋅3p2⋅5p3⋅7p4⋅11p5⋅13p6⋅... as a combination of non-negative integer values of p1, p2, p3, etc. Nothing stops all of the powers from being zero (which is, thus, the unique prime factorization of 1).
Yes, that's right. The convention that an empty product equals 1 is explained on Wikipedia here. All the statements you gave are equally correct (if not completely precise). It's just that the first two use the convention of empty product equal to 1, and the others choose not to use that convention.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Ranking in detail. Reminder that there are smxxxxxxxx tags so you can paste it directly (as nicovideo.jp/watch/smxxxxxxxx) in your browser's URL bar.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
I was just commenting on certain aspects of Amaraticando's posts of late. I already know that there are a lot of soccer/football fans here and that the World Cup is a big deal.
mz wrote:
This whole thing started (IIRC) with a viral post showing a picture of Portugal leaving a single player inside the field after scoring a goal, otherwise Spain could have resumed the game without waiting for all of them to end the celebration and come back. This rule is obviously fake, but it appeared everywhere... Then Panama and England tried to apply it.
Oh, I see. It's more recent than I thought as well. (relevant link) The rules for a kick-off state though that all players except the player taking the kick-off have to be in their own half of the field of play. It also says that the referee has to give a signal to restart play. I'd find it hard to believe that a competent referee would give a signal to restart play based on an interpretation of the rulebook that is beyond common sense, but perhaps such stories could really have been true at some point somewhere.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Congrats to France for winning the World Cup. Croatia played well in the tournament for the most part but was unable to pull it off in the final. I'm a bit puzzled by the reactions in this thread though. This site is supposed to be tasvideos.org, not some crazy soccer board.
Amaraticando wrote:
This was a bit depressing to watch though... What were they thinking, LOL? https://www.youtube.com/watch?v=YDHzsO2iE9w https://www.reddit.com/r/soccer/comments/8y7nr8/englands_attempt_to_score_after_croatias_winning/
I didn't even know this was a thing. How do these players not know the rules?
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
p4wn3r wrote:
Find all positive integers a and b, with a > b, such that ab=ba.
Taking logarithms of both sides and rearranging, we get ln(a)/a=ln(b)/b (seen this before?). Taking the derivative of f(x)=ln(x)/x, we see that f(x) increases on the interval (0,e), decreases on (e,∞), and has maximum at x=e. Since f(x) is positive exactly when x>1, it follows that 1<b<e<a. Since b is an integer, this gives b=2. There is only one possible a corresponding to b, and a=4 (since 42=24). So the only solution is a=4 and b=2.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
So, which teams are going to be in the final? So many big names have fallen out. :| Judging from how things are going, I could make predictions, but then they'd all be wrong.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
So many own goals in this World Cup. Apparently 11 now. https://youtu.be/tafCE6GJrhQ?t=790
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
I'll post my solution to Riddler Classic here. The latest Riddler post also has a solution. To recall, the question is:
The Riddler wrote:
You have a gate that requires a passcode to open. There are 10 buttons: the digits 0 to 9. You have forgotten the passcode, but you remember it has four digits. You have no choice but to try them all. Since there are \(10^4\) = 10,000 four-digit passcodes, you might think this would take you 40,000 button presses to guarantee an opened gate. However, this gate’s keypad never resets: The gate opens as soon as the last four buttons you’ve pressed are the correct code, so you can be more efficient. For example, you can try two different codes by pressing just five buttons: The combination “12345” tries both “1234” and “2345.” Of course, pressed for time, you want to press as few buttons as possible while still trying different codes and eventually opening the gate. So the question is: What’s the smallest number of buttons you need to press to make sure you open the gate — i.e., that you’ve tried every possible four-digit combination?
You would expect that the minimum is 10003; we just need every 4-digit number to be a unique subsequence of a 10003-length sequence of digits. Indeed, it is possible to do so. It turns out that this problem has been well-studied before. Such a sequence is known a De Bruijn sequence. For example, the sequence 0000110100101111(000) is a De Bruijn sequence for n=4 and k=2; it contains all 16 4-digit binary sequences. Such a sequence always exists for given n and k; for n=1 it is trivial and for n>1 you take an Eulerian cycle on an (n-1)-dimensional De Bruijn graph (an Eulerian cycle exists on a strongly connected directed graph iff every vertex has equal indegree and outdegree). So for general n and k, the minimum number of button presses required is kn+(n-1). For the Riddler Classic problem, n=4 and k=10, and this gives 10003. Now unfortunately such a sequence isn't easy to memorize (such as the one given by the latest Riddler post); I thought I had such a sequence but it turns out I made an error. So about whether there is such an easily memorizable sequence, I will leave this one unanswered.
Mitjitsu wrote:
In the game of golf what is the fastest speed a ball can travel over the hole with still ending up in the hole? Assume the ball has been putted, with no elevation applied and is travelling directly over the middle of the hole
This seems like a physics question; did you mean to post it on the physics questions thread? In any case I think we'd need more details.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Here's an interesting Riddler Classic problem this week:
The Riddler wrote:
You have a gate that requires a passcode to open. There are 10 buttons: the digits 0 to 9. You have forgotten the passcode, but you remember it has four digits. You have no choice but to try them all. Since there are \(10^4\) = 10,000 four-digit passcodes, you might think this would take you 40,000 button presses to guarantee an opened gate. However, this gate’s keypad never resets: The gate opens as soon as the last four buttons you’ve pressed are the correct code, so you can be more efficient. For example, you can try two different codes by pressing just five buttons: The combination “12345” tries both “1234” and “2345.” Of course, pressed for time, you want to press as few buttons as possible while still trying different codes and eventually opening the gate. So the question is: What’s the smallest number of buttons you need to press to make sure you open the gate — i.e., that you’ve tried every possible four-digit combination?
Note: Passcodes can have leading 0s. This one may be challenging. It may be easier to try smaller cases, say, passcodes of length n over a set of k symbols; this problem is then n=4 and k=10. There are actually a few questions that can be answered, such as: What is the smallest number you need to press, is it possible to prove this (easily), and is there a simple algorithm to generate the sequence that you should try?
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
How did you even manage to glitch the game this badly. That's pretty cool. So that solves the long boss problem from the first version of the TAS. I admit though that not a whole of the game is left (I miss Honoo no Ya and Mizu no Ryuu). I wonder if maybe a less-glitched version is in the works.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
As far as I know, lsnes is the only emulator that supports mid-frame resets. I can't think of another one.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
HappyLee wrote:
That's true. Normally I wouldn't mind, but the same logic applies to TAS work. We have put a lot of hard work into our run, but our work wasn't respected by many people in the first place, and still hasn't been now. What's even more disappointing is that few people cares like I do, and many people are still blaming me over this and demanding me to shut up.
I say this from having experienced it myself, and seeing that this is something that is very easy to fall into on TASVideos. No one is entitled to anything. No one is entitled to good ratings or comments, nor freedom from bad ratings or comments. No one is entitled to praise, nor freedom from criticism. None of this changes just because of how much hard work one puts into a TAS or how much one cares about it. If one does not accept this, then it would be better to keep a distance from the site. The users of this site collectively are known to come down extremely hard on people who step out of line (however that occurs); that has happened a countless number of times in the past. I recommend not to get on the wrong side of anyone on TASVideos, no matter how they act.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Link to video Ranking in detail. Now with smxxxxxxxx tags so you can paste it directly (as nicovideo.jp/watch/smxxxxxxxx) in your browser's URL bar. There's a huge gap between 3rd (17382pt) and 2nd (127246pt), similar to a couple months ago.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
BrunoVisnadi wrote:
Consider a circular town of radius 1 mile. You want to build a 1 mile length road inside this town. What is the smallest d for which you can build a road so that every point inside the town is at most d miles away from the street?
Revisiting BrunoVisnadi's problem, we assume that the road is connected (otherwise you could use a measure-zero set). A circular road centered in the middle of the town with radius 1/(2pi) would give d=1-1/(2pi)≈0.841. Since the road doesn't need to enclose an area, we can do better than that, by breaking the circle as below: Here, d is the distance we want every point in the town to be within the road, r=1-d is the radius of the inner circle, P is a point on the edge of the town (here oriented at the top of the circle), and PA and PB are tangent lines to the inner circle. Then the road is formed by the arc AB (away from P) joined to the line segments from A and B toward P up to a distance of d away from P. The length of PA and PB are each sqrt(1-r2), and so the length of the road is: r(2π-2θ) + 2(sqrt(1-r2)-(1-r)) = 2r(π-θ+1) + 2sqrt(1-r2) - 2. Since cos(θ)=r and r=1-d, this becomes: 2(1-d)(π-cos-1(1-d)) + 2sqrt(2d-d2) - 2d. Using WolframAlpha, when the above is set to 1, you get d≈0.812. I checked some of the star-like configurations that Aran Jaeger suggested, but I couldn't do any better than this road with them, even with other values for d or length of road. Now if you use d=0.5, you get 2π/3 - 1 + sqrt(3) ≈ 2.826. So in the case of general d, this method works for any length up to about 45% of the town's outer boundary. Beyond that, the question becomes complicated since now you need the road to cover the center of the town. All I know that, in the limiting case where d→0, parallel lines spaced 2d apart ensure that each point in the town is within d of some line. In this system, a road of length x is in proportion to an area of 2dx, the ratio of road to area being 1/(2d). So, given a circular town of radius 1, the length of the road required for some d close to 0 approaches 1/(2d) * 2π = π/d.
Editor, Experienced Forum User, Published Author, Skilled player (1943)
Joined: 6/15/2005
Posts: 3250
Yes, both BrunoVisnadi and Aran Jaeger are correct. Indeed, this is case n=4 of the extremely well-studied Steiner tree problem. I didn't actually know how well-studied it was until I found it on Wikipedia. Don't be confused by the word "tree" here; this is a geometric problem and not (just) a graph theory problem. What is interesting is that every minimal Steiner tree (connected road that joins all given points and has minimum length) has the following properties: - The tree is a set of non-crossing line segments connected at their endpoints. (This is why they called it a "tree".) - Every angle formed by two joined line segments is at least 120°. If three line segments join at a single point, the angle between each pair of line segments is 120°. - At most three line segments can join at a single point. - Every join point that is not one of the given points is interior (within the convex hull of the given points) and has exactly three line segments joined at that point. Using these properties, it is very easy to solve n=3 and n=4. This site discusses general triangles as well as rectangles. The solution for n=4 (this Riddler problem) is shown below: The pentagon case (n=5) is discussed on this site. The solution for n=5 is shown below: However, it turns out that for n≥6, the minimal Steiner tree is just the polygon on the points minus an edge. (Just because a Steiner tree satisfies all the properties above doesn't mean that it has minimum length!) More information is in this paper. The case n=6 has some local minima, but hexagon minus an edge is the minimum: As for BrunoVisnadi's problem, assuming the road must be connected, I have so far a value of d≈0.812, where d=1-cos(x) and x is the root of cos(x)(pi-x+1)+sin(x)-1.5 in [0,pi/2]. The road I have is a "broken circle", having the shape of a hairband (I don't know how to describe it better). I'll explain how I got this later.