Posts for p4wn3r


Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I highly recommend Ubuntu. Although you will see people debating a lot which distro is better, you will see that distributions have to do one very basic thing and do it well. What they have to do is to allow you to install and update software easily without breaking everything, and it helps a lot when you're a beginner to use popular ones, because it's very likely they already did what you need done to start using software, and even if you're an advanced user, it's likely you don't care how distros work internally and need some obscure piece of software to work, and have to hack it in yourself, and again, there are more resources available to hack a popular distro. The only use case of using a niche distro is if you want to gain knowledge about how package management works. It's nice if you want to become a sysadmin, but definitely don't bother with it if you're starting.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Today's question has real world applications. Suppose you are a financial analyst working at an investment fund managing billions of dollars in assets, and you are not a corrupt individual (shoot, I just said it had real world applications, and now I make this unrealistic assumption). Someday, someone comes to you saying they have an insurance fund made up of shitcoins they created themselves. A possible example is if they tweeted the following: Now, assume, just in theory, of course I'm not trying to imply anything here, that when they show you the daily value of this fund, instead of calculating it from the assets there, they just use the following Python code, with a Gaussian of mean 7500 and standard deviation 3000, which is summed to the value each day: The question is: what is the probability that this code will increase the value of the fund each day it runs? Do you think this pattern is reasonable for a fund consisting of an asset whose price fluctuates like this? Please, don't try to connect this problem to current events. This is a purely academic question :D
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
For what it's worth, here's the intended solution. Substitute x = a² and y = b². We have a² + b² = 6 (a² + a)(b²+b) = 33/4 Rearrange the second equation as: ab(1+a)(1+b) = ab(1+a+b+ab) = 33/4 Now multiply both sides by 4: 2ab(2+2(a+b)+2ab) = 33 Notice that a² + b² = (a+b)² - 2ab = 6, so 2ab = (a+b)² - 6. Substitute it to find: ((a+b)²-6)((a+b)²+2(a+b)-4)=33 Now set u=a+b and expand: u⁴ + 2u³ -10u² - 12u - 9 = 0 Use rational root theorem or whatever means to see that u=3 is a root. Then factor it (u-3)(u³+5u²+5u+3) = 0 Notice that since u = a+b > 0, and the second factor is always positive for u>0, then u=3 is the only plausible root. Then you have a + b = 3 a²+b² = (a+b)² - 2ab = 6 => ab = 3/2 So, we find a and b by solving the quadratic z²-3z+3/2 to find a = (3+sqrt(3))/2 and b = (3-sqrt(3))/2 to find x = (3+sqrt(3))²/4 and y= (3-sqrt(3))²/4 So the idea was to recast everything in an equation for the sum, which I chose the values to be very simple to solve.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I created a new one today! Let x and y be two positive real numbers, such that x > y and: x + y = 6 (x+sqrt(x))(y+sqrt(y)) = 8.25 Find x and y.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
OmnipotentEntity wrote:
Show that: Sum(a=1..inf) Sum(b=1..inf) gcd(a,b)/(a^2 b^2) = (5/2) zeta(3)
The trick here is to find an Euler product that will decompose this thing into an infinite product of primes, and then apply the zeta formulas. Notice that the denominator is always the square of an integer. Because of this, we can rewrite the sum as: S = sum(n=1..inf) f(n)/n^2 What is f(n)? f(n) is the sum of gcd(a,b) for every possible way of writing n=a*b. Another way f expressing it is f(n) = sum(d|n) gcd(d, n/d). Notice that if we have n and m coprime, then f(n*m)=f(n)*f(m), so f is a multiplicative function. Because of this, we only need to evaluate it for prime powers, where things are much simpler. We have f(p^k) = sum(i=0..k) gcd(p^i,p^(k-i)) = sum(i=0..k) p^(min(i,k-i)) We break it into even and odd: f(p^(2l)) = p^l + 2(p^l-1)/(p-1) f(p^(2l+1)) = 2*(p^(l+1)-1)/(p-1) To set up the Euler product, we need to calculate T(p) = 1 + f(p)/p^2 + f(p^2)/p^4 + ... We sum an even plus an odd one divided by p^2 and sum to infinity. With some help from Wofram Alpha, the answer is: Now sum it and simplify (credit to Wolfram Alpha again): So, we want calculate the infinite product of T(p) over all primes p. To do that, we can use that prod(1-1/p^s) = 1/zeta(s) and prod(1+1/p^s) = zeta(s)/zeta(2s) So, our product becomes: Using zeta(2) = pi^2/6 and zeta(4) = pi^4/90, the factors of pi cancel out and the answer is 90/36 * zeta(3) = 5/2*zeta(3). By the way, this was a pretty challenging one. I saw the multiplicative property of the gcd in the sum, but had to do a lot of trial and error with some generating functions that led nowhere until I got the Euler product right, and even then it was a lot of algebra that I don't think I could do by hand.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
FractalFusion wrote:
Fiddler on the Proof has an interesting question this week that I had coincidentally been thinking about some time ago (at some point in the last year or so, I can't remember).
I already knew this one. Actually when I started university a physics professor came to visit me and my friends at our dorm, and he showed this question as a challenge. So I have a bit of nostalgia here and absolutely MUST solve it. There are two ways to go about it, one is more formal, other more intuitive a la Euler that's harder to formalize. Let's start with the intuitive one. Consider the continuum limit. In that limit we connect the point (0,1-t) to the point (t, 0). If we add a differential dt, we similarly must connect (0,1-t-dt) to the point (t+dt,0). We can find the intersection point of these two by solving a linear system. The first line is given by y = 1-t - x*(1-t)/t, and the second line is y = 1-t-dt - x*(1-t-dt)/(t+dt). Equate them and you get -x*(1-t)/t = -dt -x*(1-t-dt)/(t+dt) => x = t(t+dt). Notice that in the limit dt -> 0, we have simply x = t^2. In this limit the intersection point should correspond to a point in the curve. So, substituting y = 1 - t - t(1-t) = (1-t)^2. We know (t^2, (1-t)^2) for t from 0 to 1is a parametrization of the curve. It's easy to express it as y(x) = (1-sqrt(x))^2 Now let's go to the formal way, which you would write in a calculus test. Suppose y(x) is the curve. The tangent to the curve at x must cross the x and y axes at points (0, 1-t) and (t,0) for some t. This implies that the slope of the tangent is -(1-t)/t. Therefore, y'(x) = -(1-t)/t for some t. However, this condition is not sufficient. The point (x, y(x)) must also be somewhere along the line y = 1-t -x*(1-t)/t, or else the setup won't work. This second condition, though, fixes a value for y given x. So, if we isolate t, we have t = 1/(1-y'(x)), and substituting this in the other equation we get: y = xy' -y'/(1-y') Now, if you like to research things, you'd eventually recognize this as Clairaut's equation. If you don't know it, you can still guess you can solve it by noticing that the terms y and xy' combine nicely. Anyway, the basic idea is to simply differentiate it with respect to x: y' = y' + xy'' - y''/(1-y')^2 => y''(x - 1/(1-y')^2) = 0 Now, y'' = 0 gives functions of the form y = ax + b. The only way to satisfy the boundary conditions y(0)=1 and y(1)=0 is to set y = 1 - x. Although this function satisfies the conditions I set before, it does so in a trivial way, so let's look at the other solution. It is x(1-y')^2 = 1 => y' = 1 +- 1/sqrt(x). Notice that we want the derivative to be negative for 0<x<1, for this to happen, we need to pick the minus sign. So y' = 1 - 1/sqrt(x). Finally integrate this to find y = x - 2sqrt(x) + c. Setting y(0) = 1, we have c = 1, and we can rewrite y = (1-sqrt(x))^2, the same answer as before. For the bonus question, we just need to integrate y(x) from 0 to 1 and from 1/2 to 1. That's pretty easy, because y(x) is just a sum of x to the power of an exponent. If we do this, we have that the area from 0 to 1 is 1/6, and from 1/2 to 1 is sqrt(2)/3 - 11/24. If we sum the area of 4 curves around a square, we double count 8 times the area from 1/2 to 1. From this we can compute the free area in the unit square as 1 - 2/3 + 8*sqrt(2)/3 - 11/3, which is approximately 0.4379
Post subject: Origin of Pokémon glitches
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I haven't posted here for a while, but recently digging through the Internet I found some very interesting information, and I think I managed to find the origin of the Select+Cancel glitch in Red/Green J and the Missingno. glitch, and I also have some speculation on how Trainer-Fly was originally found. Since I have nowhere better to post this, I'm posting here. Also, notice that my japanese is terrible, and I had to rely on google translate and OCR software to read printed japanese characters and understand what's going on. In any case, it's a giant wall of text, but there was a lot of detective work: Select+Cancel: 27/02/1996 - Pokemon Red/Green was released in Japan. 05/04/1996 - Famimaga No. 7 is published. It covers the Pokemon games, and in a section where readers can submit tricks, it shows a technique to clone Pokémon in a trade by shutting down one of the cartridges at a specific time. 15/04/1996 - CoroCoro comics for the first time acknowledges the existence of Mew, the 151st pokemon, and announces a special distribution event where only 20 readers would be selected to receive it. 19/04/1996- Famimaga No. 8 publishes in its reader submitted tricks a Select glitch to allow to share experience between Pokemon in battle. More details later. 20/05/1996 - Kouichi Hiwasa describes on usenet a Select glitch to create Mew. In the email he says he did not believe the Mew rumors initially, but this glitch convinced him it was real. Later he credits his younger brother for the discovery, after experimenting with a Select glitch he learned from Famimaga. Speculation about what happened: The story of how Mew was put into the Pokemon games as told by the developers has changed several times. Sometimes it's said that it was a prank, and later they released it when a glitch allowed players to access it, and in other interviews it was said that they included it to create rumors to drive up sales. According to this timeline, it looks like it was the latter. The Select glitch published in Famimaga No.8 goes like this: say you want to give exp to the second pokemon. You place the Select cursor on the second item, and exit with B. Then you go to the pokemon menu, and the cursor shows up at the second. Then if you switch it with the first pokemon, the Pokemon in battle don't actually change, but after you win the battle the experience only goes to the one you switched over. Now, Select glitches were pretty common in JRPG's at the time. For some reason developers couldn't implement swapping things in UI right. Anyway, it looks like shortly after the games release someone wrote to Famimaga about this select bug in Red and Green, and they published it. Now, when you know this, there's the natural question. Does this work outside battle? There are six pokemon in the party, but 20 items, what happens if you swap pokemon that do not exist? Nowadays we know the answer, this corrupts memory, and if you choose specific hex values, you could theoretically get other types of Pokemon, including Mew. It's unclear to me why editors of Famimaga did not consider this. The most likely reason is that, since they had connections to Nintendo, they didn't want to publish things that would cause kids to lose their game, so they settled for publishing a safe variant. In any case, I think you can see how unreasonable is the story of Game Freak devs, that Mew was an accident discovered by a glitch. Although there really was a glitch that allowed players to see it, it was only published in a very mild form in Famimaga only AFTER they released it. Although Famimaga No. 7 does include a glitch, it's an improper trade cancellation glitch, not a select one. And even the select one published requires quite a bit of work to get Mew. Even if we accept that somehow Famimaga knew about the glitch and told the Nintendo devs way before publishing, we are talking about someone finding Mew with a very difficult to exploit glitch, telling Famimaga everything, they contacting Nintendo, and then distributing it to only 20 people after finding out about it. I think this is extremely unlikely, what most likely happened is that they put Mew in the game with the intention of distributing it to 20 people in CoroCoro almost two months later to create rumors. Then the glitch was found, and people heard about the rumors and could confirm that Mew existed in the game using the glitch. Then later the devs made up that story as a marketing strategy. Missingno. February 1999 - Nintendo Power No. 117 publishes in "Classified Information" section the Fight Safari Zone pokemon in the wild trick. This is a crucial source that most people miss. The Fight Safari Zone pokemon trick is described as running out of steps in the zone of the safari zone the pokemon you want appears, then surfing from the south of Fuschia to Seafoam Islands and surfing up and down in the east coast. It's incorrectly stated that if the player battles trainers along the way, the trick will not work. April 1999 - Nintendo Power No. 119 publishes in the PokéChat section, where they take questions for fans, two interesting answers. The first is an answer to a question regarding catching tough pokemon, that the player should try holding B the moment the ball explodes, which has no effect at all. Although this is not technically wrong advice (it's never explicitly stated that doing this will make catching easier), it's likely the source of the infamous myth that holding B will improve catching. The other interesting answer asks the player to try fishing on gym statues. This is indeed a trick that exists, since gym and pokemon league statues are considered water tiles, and you can fish and surf on them. May 1999- Nintendo Power No. 120 acknowledges the existence of Missingno. and describes it as a glitch that could harm the game. It describes the way to encounter it as talking to the Old Man in Viridian City and using Fly to get to Seafoam Islands while avoiding contact with all land pokemon. June 1999 - Nintendo Power No. 121 describes the Poké Doll trick in Pokémon Tower to skip the Silph Scope. Sometime before Jan 2000 - Nintendo has an FAQ about Red and Blue where they discuss missingno. It describes it as appearing when the player incorrectly performs the Fight Safari Zone trick. This trick, by the way, is also described incorrectly in another answer, saying that the trick will not work if the player faces enemies which are not the water pokemon on the way there. Jan 2002 - Jolt135 creates a strategy guide which has his discoveries about Missingno. He figures out that the encounters are controlled by the characters in the player's name. Speculation about what happened: For those who don't know, here's how this method for seeing Missingno. works. Tiles in gen 1 are actually composed of blocks of 2x2 subtiles. Due to a programming oversight, when the game calculates if you should have an encounter, it uses the bottom right subtile, but when it picks which pokemon you should actually see it uses the bottom left. This doesn't matter in 99% of the cases. The only instance where this causes problems is when you have a shore tile, where the left subtiles are land, and the right subtiles are water. To compute the encounter density in these tiles, the game will pick the data for surf encounters, but when you eventually get the encounter it will pull that data from the land encounters. Although there are a lot of shore tiles with left land, and right water in the game, the only regions that have surf encounters are in the water routes between Pallet Town, going through Cinnabar and Seafoam, until Fuschia. Because of this, this discrepancy only happens in three places. The left most shore tiles you can surf while leaving Pallet, the right coast of Cinnabar, and the right coast of Seafoam Islands. Pallet is completely useless because Sea Route 21 has land pokemon, so you will simply encounter them, which you could easily do by walking on the grass. That leaves only Cinnabar and Seafoam, where you can potentially access uninitialized data, and today almost everyone does it in Cinnabar because it's easier to reach. Now, one guide in Gamefaqs states without source that Missingno. was first found in an in-game trade with the guy in the Cinnabar lab. This guide is cited in some places, and it does make sense, because you can think someone trading a pokemon there, surfing in the Cinnabar coast and finding a Missingno. However, in face of all of this, I think this is highly unlikely. Notice that nearly all early material on this glitch comes from Nintendo, and they only mention Seafoam Islands, both on their Safari Zone trick, the Old Man+Missingno. disclosure in Nintendo Power, and in their FAQ on pokemon.com, where they state that Missingno. is an effect of players doing the Safari Zone trick incorrectly. Therefore, all evidence points to the glitch being disclosed by Nintendo, and it's not clear at all that they even knew the glitch could be performed in Cinnabar, because all their early references are in Seafoam. Even in their Missingno. disclosure in May 1999, where they correctly state that the player must avoid land pokemon, they specifically tell readers to use Fly and go to Seafoam, not Cinnabar, which would be easier. Because of this, I think it's much more probable that Nintendo knew that the old man could trigger the glitch before they knew it could be done in Cinnabar, so the story that Missingno. was found first without the old man and at Cinnabar is implausible. Nowadays, it's generally acknowledged that Nintendo disclosed the bug on the May 1999 issue of the Nintendo Power magazine, but I think the one with most information is the Feb 1999 issue, with the Fight Safari Zone trick, and together with the others, we can have a pretty good idea of what was going on there. First, why on earth does Nintendo say in Feb 1999 that the Fight Safari Zone trick doesn't work if you fight trainers on the way to Seafoam? It's not only a mistake, but a very difficult one to make if you found the bug by testing. Say you found the trick, then if you're going to publish that it doesn't work if you fight a trainer, you do the obvious, you fight a trainer and go there, you figure out that it still works, and you don't publish! The thing is: this mistake is very easy to make if you are a DEVELOPER. Judging from the other issues, Nintendo was disclosing tricks which are pretty difficult to find if you don't know the game's internals, but pretty easy if you know their logic. For example, the statue tiles being considered water so that you can fish, the pokedoll trick, and even one about holding the B button, which is wrong, but could potentially come from someone who understood the code wrong. Anyway, if you assume this wrong tip about the Safari Zone trick came from a programmer, the mistake is easy to justify. You know that the glitch happens because of uninitialized data in land pokemon, so you conceive of this trick, where you visit the Safari Zone and just go to Seafoam, while keeping it there. However, you don't know if other parts of the code can overwrite it, so you do the minimum amount of actions, you don't use Fly, you don't fight trainers, and try to get it working only with wild encounters. After you see that the trick works, congratulations, the bug in your code can now be put on a magazine as a neat trick. What the programmer(s) who conceived of this trick did not know at the time is that it's extremely difficult to overwrite the active land encounter table. The only things that can do it are the Old Man, in-game trades and cable club battles and trades, and exploiting the last is not trivial either. Normal trainer battles don't override the encounter table, and since it persists when you save the game, resetting to access random data there also doesn't work. However, even if this tip was wrong, it might have led players to the glitch. Suppose you are a pokemon enthusiast that regularly reads game magazines and you see the Fight Safari Zone trick as it was published. The trick seems to imply that the tiles at Seafoam are special, and with little effort you can conclude that you can encounter there pokemon from the last area you visited. But if they were programmed to do so, why does it include the condition to not fight trainers for the trick to work? If you do fight trainers, what's going to happen? From there, assuming that you are going to test this trick on a game where all trainers have already been fought, the easiest option is to simply go to the Old Man and go to these tiles and see what happens! From this, I think the most probable timeline of events went like this: 1. While Nintendo is working on Yellow or G/S, they figure out the problem with the shore tiles, along with other things. 2. Someone at Nintendo gets creative and sees that these bugs can be refurbished as neat tricks to publish in Nintendo Power. 3. Through careless testing, the Fight Safari Zone pokemon trick is published, including an incorrect condition to avoid trainer battles. 4. Players, probably using a game without any trainers to fight, try the Old Man before going to Seafoam. 5. Shocked, they see all the oddities of the glitch, including Missingno. 6. At some point, Nintendo Power is contacted with questions about Missingno., if it's a new Pokemon, and why it appears after you talk to the Old Man when doing the Safari Zone trick. 7. The magazine contacts the programmers about this, who now analyze the code correctly. 8. Nintendo Power publishes the programmers' conclusion. Missingno. is simply a bug, it might have unintended side effects. They now describe the trick correctly. It's land pokemon that you should avoid, not trainers. They publish the procedure to get it and print its photo to show readers it's only a bug. 9. This disclosure has unintended consequences. When you tell people not to do something, they usually do it. People start encountering Missingno. and catching it. 10. Nintendo sees that the glitch almost never erases the game, and can have good side-effects, and could be exploited by cheaters, then tries to bury the issue by never giving details about Missingno. again, saying it's just a glitch when the Safari Zone trick is done incorrectly and questions should not be asked. Trainer-Fly Sometime around 1998 - Team PA starts Pokemon analysis (everything except the BBS board is archived here). They accumulate a lot of knowledge about the game, they reverse engineer how item, pokemon, moves, stats and encounter tables work, and include a page about how to make Mew using Select+Cancel. Unlike Hiwasa, which I cited before, they know what they're doing. While Hiwasa got Mew's ID of 21 by using a water type without knowing about the ID, they get the value of 21 by using map coordinates. 07/08/1999 - Someone reports encountering a Level 7 wild Mew in teamPA BBS board. The source for this is Kakeru, and he admits in his blog he can't give an objective source, because this BBS archive is private. Nevertheless, I think this is trustworthy, and is key material that I will discuss this and Kakeru's tweets later. 31/05/2002 - "Nintendo" submits a code to JesseWorld detailing how to get Mew using the well known Gambler+Youngster method. It's dismissed as fake. 09/03/2003 - Daniel26 submits the same Gambler+Youngster technique to catch Mew on GameTalk. It doesn't pick up any attention and receives low ratings. 19/04/2003 - TheScythe posts in GameFAQs boards the same Gambler+Youngster technique. He anticipates skepticism and says he saw it in two other websites, tried it because he was bored, and it does work. 20/04/2003 - Jolt135, a respected user who wrote the strategy guide posts "What I wonder: Where do they pull 7 and 21 from if this indeed exploits timing glitches? Oh, well. It doesn't matter. All that matters is... IT WORKS!!!!!" This validation proves to be critical, and everyone starts trying the method and seeing that it works. 20/04/2003 - Jolt135 posts a link to the GameFAQs thread to Azure Heights, telling people about it. 29/04/2003 - White Cat posts an Eureka in Azure Heights, figuring out that the pokemon battled is controlled by the special of the last pokemon seen. 29/01/2004 - fifthヽ(´ー`)ノ ◆Fi3PJTZKLQ posts in 2ch a link to his webpage. This explains the glitch in some detail, like how the pokemon changes when you fight different trainers. This post greatly popularizes the trick, which becomes known as the "fifth method" in Japan. Analysis: The most interesting piece of info is the post on the teamPA BBS board in August 1999. The poster is playing the japanese Yellow version, and answers Mew stats for L64 and L68. When asked where he got it he never says the location explicitly, but it's strongly implied to be Rock Tunnel. That's because he mentions using Flash with Pikachu, being annihilated in a tunnel and going back in, and encountering Mew in the 2nd floor, in the place where girls show up one after the other. Rock Tunnel is the only dark cave in Gen I, the only place where you need Flash, and it does have in the final section three girl trainers. It's entirely possible that you die there in front of a trainer, get teleported out, and enter Rock Tunnel from Lavender to activate an encounter. Kakeru comments in his tweet that he should have noticed the start menu not working after doing this, but actually in the Trainer-Fly variant where you die from an encounter in front of a trainer, the start menu still works afterwards. The poster mentions using a L20 Pikachu and paralyzing Mew and using 3 balls to catch it. These numbers also make sense. Now there's the question: why does the poster not mention dying in front of a trainer specifically? My guess is that this technique of dying to a Trainer in a cave was already known, and this is implied by the context. To start, let's see how we could get Mew this way. If we die in Rock Tunnel for the first time, we need to reenter it from the north part of route 10, which is not the area with the girls. So, to do this, we need to already be past Rock Tunnel. So, this definitely did not happen by accident on the first Rock Tunnel visit. It must have happened in a revisit. Well, if you are revisiting Rock Tunnel with the intention of dying to a trainer there, the entrance closer to Lavender is much better, because the two girls there are optional, so you can skip them in a first visit, and they are pretty close to the entrance, so you can try dying to them. Now, if we just do Trainer-Fly by dying in front of a trainer and going back immediately, the result is uninteresting, because we're simply going to fight the trainer. To have interesting results we need to battle a trainer or a wild pokemon first. It turns out that none of the trainers close to the south Rock Tunnel entrance give Mew. With respect to wild encounters in the yellow version, it's much more interesting. The grass behind the Cut trees in route 8 in Yellow have L20 Pidgey and L22 Pidgey as the most common Pokémon. Together they make about 40% of the encounters. L20 Pidgey has 3/16 chance of having the special to trigger Mew, and L22 Pidgey has 2/16 chance. Just to confirm all of this, I loaded the save file from FractalFusion's cancelled Yellow TAS and setup all I needed to make this work, leveling Pikachu up a bit, catching 10 pokemon, getting Flash, etc. I could get a wild encounter in front of the girl in Rock Tunnel in my fifth attempt. It's pretty easy, you can simply save in the diagonal of the trainer, walk to the spot and if you don't get an encounter, reset immediately and try again. Then I just had Pikachu use Thunder Wave on the Zubat until it got killed. After that I got the cut slave and went to route 8 to find encounters. I only went back to Rock Tunnel when I encountered a Pidgey, and in my tenth attempt I got Mew! It's certainly reasonable to obtain Mew this way if you put some effort. One important thing also is that the post in 1999 has in its title that it's a wild LEVEL 7 Mew. And unlike other trainer-fly reports, teamPA does take it seriously and asks questions. It looks like the most probable thing is that it was already known to teamPA members that you could encounter level 7 wild pokemon by dying in front of a trainer, facing a battle and going back, but they did not know what controlled it. Since it was already known how they could make Mew using select glitches, the novelty of the report is that Mew could be encountered with the wild level 7 method. It was plausible to them that this could occur, because they didn't understand it, so they immediately asked what the person did, so that they could replicate it. The poster did not know either, so he wrote about Pikachu's paralysis status, etc. Speculation about what happened: 1. It was already known to enthusiasts in Japan in 1999 or before that you could die in front of a trainer to cancel a battle, and resuming it after facing a Pokemon would spawn level 7 encounters, but why this happened wasn't known. 2. By trial and error, they started testing around Rock Tunnel, where it's pretty easy to die in front of a trainer. 3. The trick was considered minor at the time, so it never became popular. 4. Eventually by trying to figure out what controlled the encounters, someone found Mew without knowing how it works, which drew attention to the glitch. 5. In the time between 1999 and 2002, people figured out optimizations. Like Flying in front of the gambler, which is much more reliable to cancel the battle instead of dying, and realizing that fighting a trainer always gave the same Pokemon. 6. It was not before the Youngster was found, which gave Mew 100% of the time, that the trick had any hope of getting mainstream. At the time there were lots of hoaxes claiming to give Mew, which only made people waste their time. 7. In some way, someone might have seen the trick in Japanese forums, or it was spread without the Internet until someone heard about it and posted in its final Gambler+Youngster form, which was not annoying to execute, and you could try it out if you were bored. 8. Eventually someone who was familiar with the game internals looked at it and thought it was reasonable, verified it worked, and the word spread. I had a look at why fifth is credited for the method in Japan. It looks like the source of this is fifth himself. In his webpage, he claims that he bought the game the day it came out, researched it, came up with that trick after playing for a few years, and was only posting at the time because he did not know how the web worked. To be honest, I highly doubt any of this is true. While he does seem to know that the pokemon that shows up depends on the trainer you use, he doesn't seem to know that there's nothing special about the Gambler, any long-range trainer, of which there are many in the game, work. And a person who found the glitch by researching would know this. Also, his post is nine months after the glitch was common knowledge in the west. To me, it looks like he simply found it on the web, made a convincing tutorial in Japanese and claimed it as his own. From this, I believe the best place to keep looking for the origins of the Trainer-Fly Mew glitch is to search japanese glitch forums and websites for a level 7 wild pokemon trick or something like that, but as I said before, my Japanese is terrible, and I'm not qualified to do it.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Well, I've been in this site for a long while. In the old days there was even a page explaining how emulators could never be accurate, and it made no sense to compare TAS to real runs because of that, and how cosmic rays, temperature changes, or whatever, made it impossible to simulate real hardware. That was until people actually tried to reproduce some runs on real hardware and saw the situation was not so dire. Even something as simple as the Game Boy has some sort of multithreading, because it has processors other than the main CPU to do memory transfers and so on, and it still works. The reason is that, for programming that makes sense, it doesn't matter. And if the programming doesn't make sense, don't even try to get it working, because it's likely that in original hardware it won't work either. Take Pokemon RBY for example, it uses an RNG that calls a timing register several times per frame, and yet, real time runners can and do manipulate it with some tricks to get the input at the right time in lots of runs. I cannot really comment about the run you linked, because I'm not familiar, but I've seen several desyncs, even in emulators, which control the entire execution. What's the evidence that you guys have that it was caused by multithreading? Asking sincerely, because I could take a look and learn from it. My first impression is that if you run Unity, which is a massive engine with lots of dependencies, many small configuration changes in the OS can affect the replay, which is the reason I'm running the game sandboxed.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Lots of interesting replies in this topic. Well, I think the problems introduced by multithreading are being overestimated. Definitely the end result of a program can depend on the order everything is processed, but it's in general extremely bad programming practice to do this. In fact, true concurrent code should never produce different results when you change execution order. While it's simple to come up with cases where this matters a lot, the fact is that code written by humans for humans to use does not look like that. For example, using xscope I can clearly see that there's a burst of requests to X in a short amount of time, then it stops, and after around 30 ms another burst happens. This is probably because it runs at 30 fps, and even if X doesn't know what a frame is, the UI library in the application is enforcing it. This is pretty typical when you have much more computational power than you actually need. Most of the time, the application sits around doing nothing, waits for user input, then it does a lot at the same time. In general, if the output of your program depends on the order, there's a bug. In theory you could use this as a source of randomness, but it's a very bad one. It's very biased and the bias can drastically change with some small changes to the code or even changes in the platform running it. If you're using Linux processes, you really have to go out of your way to mess things up, because most interprocess communication in Linux makes everything order independent. You'd need to either use shared memory between processes and program terrible synchronization code to make this mistake. It's unlikely that an app would do this unless they explicitly want to detect virtualization. The only way I can see this affecting real apps is when a game uses time and random devices to choose an action. From my experience with emulators, though, it's pretty easy to get determinism by "discretizing" the world. You essentially choose a time window and fake all of these devices to return the same value during it. Then when the time window is over, you stop everything and update the device values. That usually works pretty well. Regarding image building, I did not do everything through Dockerfiles, because the installer usually has a GUI. It's definitely possible to do, though. You can run xvfb in the image to run GUI apps, and use xdotool to automate the input. It's annoying, but possible. It should be OK as long as you don't include the game binaries yourself, and tell the user that by running the tool they accept some license which they should read in another environment, but it's a good idea to check with a lawyer.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Alright, here it is. Please don't mock me for my subpar Youtuber skills. Link to video
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
So, I studied the X11 protocol and realized I can virtualize it even more. X11 works like this: there's really no definition of a frame. What X11 does is: it keeps the state of the image of your desktop system, and any client with the proper permissions can view it with a GetImage call. So, when something is 60 fps in X11, what's actually happening is that your device is a client of the X server, and it's dumping its content 60 times per second. X can also call its clients by sending events, and it's precisely how it sends input. The client doesn't poll X, it simply sends an event that the client registered for, and in the client-side there's usually Xlib with a queue so that it can process them in order. Therefore, in my previous setup, when I wired the starcraft app to the main X server in my machine I did not completely virtualize it. That's because when it registered with X it started receiving a plethora of events from the host which I had no control. Fortunately there's a way around this. There's a tool called Xvfb. It's just a dumb X server with no display and no input devices, but works as a backend for GUI apps. I started starcraft using xvfb as a backend and it does work. How do I know this? Well, even though xvfb is dumb, it does keep the image, and you can run a VNC server, like x11vnc, on top of it, just like with a regular X server. With this, the events from your machine never reach it, unless you explicitly configure mouse and keyboard events to go through VNC. Here's a screenshot: Running it through VNC there's some horrible lag, though. But anyway, from this setup we have (1) the xvfb process with the state of the virtual X server (2) the container wine processes with the state of the virtualization layer (3) setting up xscope between the container and xvfb we know exactly when input events are sent, and can pause it anytime After some googling, I found the criu utility which can checkpoint processes and containers, maybe it's already implemented in docker itself, I don't know. It definitely looks like we can control input, video, audio and savestates. It looks like the best way to see if there will be any desyncs is to actually implement this...
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Just a small update. I kept hacking around today and I can confirm that this idea totally works for stopping and resuming execution of starcraft. First of all, I got tired of fighting Blizzard and decided to run the old version 1.16.1. Even with containerization, it starts almost instantaneously. Just to show how much gaming companies have gone out of the way to put stuff you don't need... Also, I configured wine to run a virtual desktop of resolution 640x480 so that Starcraft runs on a small window in my machine. I researched how applications communicate with the X server. It's all done through the X11 protocol, which is a protocol that behaves like a TCP one (actually if you run X over a network it will use TCP to implement it). In any case, to intercept the communication, we can setup a proxy. We start a process that fakes an X server in a Unix socket, but in reality what it does is simply forward them to a real X server. To the X server it looks like the proxy is the client, so it answers it. With this, we have full control over the messages and can play with them. Then we could either code an X server proxy, but like most things in programming this has already been done. After a bit of digging, I found this page, and from all applications there it looks like xscope is the most powerful. It's an obscure app, though. I did not find a package for it and had to compile from source. After this was done, I started xscope with the following command:
xscope -i2
What this does is: it starts xscope listening on X unix socket number 2, and with the DISPLAY environment variable set to :0, xscope will forward everything from that socket to the real X server at socket 0. Then, we start the containerized starcraft with DISPLAY set to :2 so that wine sends the data to xscope:
docker run --rm --env PULSE_SERVER=unix:/tmp/pulseaudio.socket --env PULSE_COOKIE=/tmp/pulseaudio.cookie -v /tmp/pulseaudio.socket:/tmp/pulseaudio.socket  -v /tmp/pulseaudio.client.conf:/etc/pulse/client.conf --user 1000:1000 -e DISPLAY=:2 -v /tmp/.X11-unix:/tmp/.X11-unix:ro  --network none --entrypoint /home/wineuser/sc starcraft
And it works! xscope can sniff the traffic. Here's a typical output:
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 31768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
	 ............REQUEST: PutImage
	              format: ZPixmap
	            drawable: DWB 02400001
	                  gc: GXC 02000016
	               width: 0280
	              height: 0066
	               dst-x: 0
	               dst-y: 204
	            left-pad: 00
	               depth: 18
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 27992 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
	 ............REQUEST: PutImage
	              format: ZPixmap
	            drawable: DWB 02400001
	                  gc: GXC 02000016
	               width: 0280
	              height: 0066
	               dst-x: 0
	               dst-y: 306
	            left-pad: 00
	               depth: 18
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) --> 32768 bytes
31.62: Client 7 (pid 975254 StarCraft.exe) -->  624 bytes
	 ............REQUEST: PutImage
	              format: ZPixmap
	            drawable: DWB 02400001
	                  gc: GXC 02000016
	               width: 0280
	              height: 0048
	               dst-x: 0
	               dst-y: 408
	            left-pad: 00
	               depth: 18
The fun thing is: if you hit Ctrl-C in xscope it goes into interactive mode, and will only let the data through after some commands. If I do this, the starcraft window freezes completely, but the sound keeps on playing in a loop. Another test I did was wait until some audio was played and hit Ctrl-C. The audio finished playing, and the sound loop kept going, but the audio that would play afterwards did not start. After I hit continue in xscope the window unfroze and the new audio immediately started. That leads me to believe that sound in starcraft runs in a separate thread, and the main thread, which gets blocked on UI calls, sends messages to it so that it updates the sound currently on. With this setup, I managed to pause and resume the app without breaking it. I see that xscope can set breakpoints on certain protocol requests. I'm studying the protocol to see if I can find something that signals if a frame was rendered, and if keyboard or mouse input was sent to the client. In any case, it looks like the "emulator" we need to code should be a generalization of xscope, which records frame renders, records input events, or filters them, replacing with fake ones to playback the movie.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
That's a pretty good question that I did not address. It requires some Linux and Docker knowledge. Basically, Linux has an API for you to debug processes. The easiest way to use it is through gdb. When you attach gdb to a process, it sends signals to them like PTRACE and others I don't remember, which tell Linux how much to execute in each of them. Although in the main OS you have lots of processes, in Docker containers you don't have a lot of them. This is the output of ps aux in the image I built:
root@969ea0cd49f0:/# ps aux
USER         PID %CPU %MEM    VSZ   RSS TTY      STAT START   TIME COMMAND
root           1  1.0  0.0   4252  3472 pts/0    Ss   19:20   0:00 /bin/bash
root           9  0.0  0.0   5900  2996 pts/0    R+   19:20   0:00 ps aux
See how there are only two of them, the /bin/bash command with the shell, and ps aux itself. If you know Linux you can already see that this is not a "real" OS, because PID 1 is not systemd or whatever init system you're using. So, implementing savestates is as simple as: send signals to all process to stop them (there are no permission issues, this PID 1 process for example is just an ordinary process in the host machine, but the containers sees it as 1 because of the namespace). Look at the kernel info to see what memory it's accessing and dump it. That's how you save. To load, you spawn all processes by hand, put the memory there and send a signal for them to resume. That's the whole point for using containers, you can literally stop all their processes, while in your host OS you can't do that, for obvious reasons.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
First of all, apologies if I'm posting this in the wrong forum, I did read most of the things that were written about this subject in the IBM PC threads, but from skimming at it, I found nothing similar to what I'm suggesting, so I do think this idea is new. If not, we can use this topic to summarize what has been done on this. Anyway, as everyone knows, TASing PC games is a nightmare. The reasons for this are that, unlike Console games, PC games take input from lots of sources, and might interact with the OS in completely different ways, which are usually affected by several hidden configurations, which makes it very hard to run processes in a deterministic way. The most immediate solution, virtualization, doesn't work too well, either, because virtualization usually makes things too slow, and it works by virtualizing the entire operating system, which means that it's pretty hard to separate what syscalls and library calls are regular OS processes, and what is actually the application you are trying to virtualize. Given this, an idea I had was to use Docker and Wine to run the application in a containerized environment, and after some trouble I managed to get the latest version of Starcraft running on it. For those who don't know, containers are a more lightweight alternative to running a Virtual Machine. Containers, at least in Linux, make use of a feature called kernel namespaces. Essentially, you can think of the OS as an entity that provides lots of "services" to an application, like creating processes, using networking, file systems, etc. Now, when you spawn something in a kernel namespace, whenever the application requests something from the Linux kernel, Linux can see the namespace it requested from, and based on that, it can "hide" lots of things, to give the application the illusion that it's running in an isolated environment. Of course, this isolation is never complete, because you need to communicate somehow with the application, if not why start it? In any case, containers give you the ability to declare precisely the dependencies that the application has and only interact with the main OS resources in the way that you specified it. When you do this, you get the predictability of a virtual machine without the performance hit, because the app is still running in an ordinary process. To be fair, there's still some performance hit, because in order to run any application you need to include a lot of OS things in a container image, and this does take some time to startup. My containerized starcraft usually takes 2 minutes to start, but after startup the performance is just the same. Let me explain what I did and why I think it has potential to improve TASing for PC games. In order to run things in docker, you need to create an image, which you specify with a Dockerfile. I installed wine in it with the following commands:
Language: Dockerfile

FROM ubuntu:focal ## for apt to be noninteractive ENV DEBIAN_FRONTEND noninteractive ENV DEBCONF_NONINTERACTIVE_SEEN true ## preseed tzdata, update package index, upgrade packages and install needed software RUN truncate -s0 /tmp/preseed.cfg; \ echo "tzdata tzdata/Areas select Europe" >> /tmp/preseed.cfg; \ echo "tzdata tzdata/Zones/Europe select Berlin" >> /tmp/preseed.cfg; \ debconf-set-selections /tmp/preseed.cfg && \ rm -f /etc/timezone /etc/localtime && \ apt-get update && \ apt-get install -y tzdata ## cleanup of files from setup RUN rm -rf /var/lib/apt/lists/* /tmp/* /var/tmp/* RUN apt update RUN apt install -y wget RUN dpkg --add-architecture i386 RUN mkdir -pm755 /etc/apt/keyrings RUN wget -O /etc/apt/keyrings/winehq-archive.key https://dl.winehq.org/wine-builds/winehq.key RUN wget -NP /etc/apt/sources.list.d/ https://dl.winehq.org/wine-builds/ubuntu/dists/focal/winehq-focal.sources RUN apt update RUN apt install -y winehq-staging=8.4~focal-1 wine-staging=8.4~focal-1 wine-staging-amd64=8.4~focal-1 wine-staging-i386=8.4~focal-1 RUN wget -O /home/winetricks https://raw.githubusercontent.com/Winetricks/winetricks/master/src/winetricks RUN chmod +x /home/winetricks RUN /home/winetricks sound=pulse COPY StarCraft-Setup.exe /home/
Several comments here. I used an old version of ubuntu, 20.04 or "focal" because it seemed that Blizzard's battle.net client was refusing to start in the newest one because of "digital certificate verification". I suppose Blizzard is actively trying to stop people running Starcraft on wine, because of this I used this old Ubuntu version with the exact same wine version reported with platinum status, 8.4. In any case, the magic of Docker containers is that we only need to get a working image once, and then after that we can simply boot it up in any linux distro that it will work. I'm not distributing the image I made here, because even though StarCraft is a free game, that would probably violate Blizzard's EULA. The setup works like this: first is some automation to setup a locale in wine without the terminal (everything needs to be noninteractive for the image to build). Then I install the specific version of wine I want, and then setup winetricks and configure it to use pulseaudio. I will go into more detail later. It's the easiest way to get the audio working. Finally, I copy the battle-net client I downloaded from the Blizzard website into the image and do the rest of the setup manually. The way I got starcraft to work was: I logged into the container forwarding graphical output to X (more on that later), and then I ran the setup client as root, logged into my blizzard account, accepted everything and it installed starcraft. It installed all files on /root/.wine/drive_c/Program\ Files\ \(x86\)/ Then I created a user with uid 1000 and gid 1000, which matches the one from my user in the main host machine (1000 is the default id for the initial ubuntu user, unless you did something crazy when you installed it). Then I changed the ownership of everything in the container /root folder to this new user. The purpose of this is to setup pulseaudio as mentioned here. Essentially we setup a shared socket for the containerized process to communicate with pulseaudio, so that we can hear its sound, but for some hacky reason you need to run it with a user that has the same ID as the user in the host machine where the pulseaudio server is actually running. With this done, I setup a script that runs starcraft without Blizzard's launcher as this new user:
Language: bash

#!/bin/bash wine /root/.wine/drive_c/Program\ Files\ \(x86\)/StarCraft/x86_64/StarCraft.exe -launch
And then I saved the image with docker commit to persist my changes and it works, as long as you remember to allow the container to access the X server so that it can create a window and receive input, and the pulseaudio socket and configuration to receive the sound. My full command was:
docker run -it --rm --env PULSE_SERVER=unix:/tmp/pulseaudio.socket --env PULSE_COOKIE=/tmp/pulseaudio.cookie -v /tmp/pulseaudio.socket:/tmp/pulseaudio.socket  \ 
-v /tmp/pulseaudio.client.conf:/etc/pulse/client.conf --user $(id -u):$(id -g) -e DISPLAY=$DISPLAY -v /tmp/.X11-unix:/tmp/.X11-unix:ro \
--network none --entrypoint /home/wineuser/sc starcraft
So, why do I think this idea has potential? Well, with this I managed to isolate everything and the only performance hit is on startup. We know exactly the image used to run the game, we can completely disable the network and possibly other os stuff that might cause desyncs, and it's even more fantastic once you understand how the communication with X and pulseaudio actually happens. For those who don't know, communication with them happens through Unix domain sockets, which are just like network sockets, but Unix specific because they handle stuff which makes no sense to pass through the network. In my setup, I simply opened all the sockets in /tmp/.X11-unix to make it simple, but in theory it should also be possible to mess around with X to create a specific socket to trade UI and input data with the game, and use Docker to pretend it's the main one in the containerized OS, so that the game accesses it. The end result is: with some combination of Docker and wine magic, we can redirect all the stuff that matters to TASing, which is audio, video and input, to some unix domain sockets, and we could potentially code a library around them to intercept these calls. This not only is much simpler than what libTAS does, which is wrap around several different types of library calls, but also works much better! That's because not only the game is running in an isolated environment, but also because wine redirects EVERYTHING a multimedia app needs to the X server and pulseaudio, unlike standard Linux apps which can depend on lots of different stuff. So this setup should in theory work no matter what library the app is using to run the game, as long as wine is able to run it. Let me know what you guys think of this idea, and if you have more suggestions!
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Very nice! I think it does work. The solution I had in mind uses methods I learned in statistical physics. It goes like this: Suppose you have n white squares at the end. What's the probability of that happening? The formula is: (N!/n!(N-n)!) * (1-1/N)^(Nn) * (1 - (1-1/N)^N)^(N-n) Justification is: first we have to choose the N choose n ways to choose the n squares. Then, for the n squares, we multiply n times by the probability that each of them are never painted, which is (1-1/N)^N. Similarly, for the N-n black squares, we multiply N-n times by the probability that they are painted at least once, which is the complement of the previous one: 1-(1-1/N)^N. What we need to do now is to compute the expected value of n in this distribution. Essentially sum on n, and find the limit when N->inf. Now the tricks from statistical physics come into play. It turns out that things simplify a lot in the asymptotic limit: 1) The most obvious one is that (1-1/N)^N goes to e as N->inf 2) It often happens that in the large N limit, each individual term has a different exponential growth rate, and the term with the largest growth rate dominates all others 3) You are free to add and remove irrelevant asymptotic terms to simplify solving the problem, because they don't matter in the N->inf limit. 4) When N->inf the ratio r=n/N can be considered a continuous value, and you can use calculus. Because of these things, the trick here is to take the logarithm of each term, then you compute everything in the asymptotic limit, adding and removing terms which are smaller than O(N), then rewrite it in terms of the ratio r and then use calculus to determine where the maximum of the logarithm happens. Let's do this step by step. First, we use (1): (N!/n!(N-n)!) * e^(-n) * (1 - 1/e)^(N-n) Simplify a little: (N!/n!(N-n)!)*(1-1/e)^N * (e-1)^(-n) Now let's take the logarithm. We can use Stirling's approximation up to O(N), which gives log N! = N log N - N N log N - n log n - (N-n) log (N-n) + N log (1 - 1/e) - n log(e-1) We want to find the maximum of this expression with respect to n. The constant terms in n are not relevant, so we drop them: - n log n - (N-n)log(N-n) - n log(e-1) Now we substitute n = rN: -rN log(rN) - N(1-r)log((1-r)N) - rNlog(e-1) Here, we can simplify further. Notice that N is just a constant that multiplies everything and does not affect the maximum, so we can drop it. -r log(r) - (1-r)log(1-r) + log N - r log(e-1) The log N term is constant in n and can also be dropped. Anyway, we can differentiate with respect to r to obtain: - log(r) - 1 + log(1-r) + 1 - log(e-1) = 0 log(1/r - 1) = log (e - 1) 1/r - 1 = e -1 r = 1/e The reason you don't find this solution in most math books is that, in the way I wrote it, it's not 100% rigorous, but it can be made so, with the theory of asymptotic analysis and, in my opinion, easier than joint probability distributions. EDIT: Well, now looking at it, it seems I did not need to take the asymptotic limit at all! The sum on n in the initial formula can be computed exactly using binomial expansion: sum_n(n*(N!/n!(N-n)!) * (1-1/N)^(Nn) * (1 - (1-1/N)^N)^(N-n)) = N*sum_n((N-1)!/(n-1)!(N-n)!) * (1-1/N)^(Nn) * (1 - (1-1/N)^N)^(N-n)) = = N*(1-1/N)^N*sum_n((N-1)!/(n-1)!(N-n)!) * (1-1/N)^(N(n-1)) * (1 - (1-1/N)^N)^(N-n)) Reindex the sum: n -> n+1 N*(1-1/N)^N*sum_n((N-1)!/n!(N-1-n)!) * (1-1/N)^(Nn) * (1 - (1-1/N)^N)^(N-1-n)) = N*(1-1/N)^N -> N/e So the ratio tends to 1/e for large N.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
This one I created myself! You have a very large array of N white squares. Choose one of them randomly and paint it black. Repeat this process exactly N times. You can paint a square black more than once, but that has no effect in the final result. On average, what's the ratio of squares that will remain white?
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Hello. Yes, it can be solved using just calculus. I could not see your attempt. If you want, you can post it again and we work it out.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
I saw this one today. Given the equation in the reals: (x^2-3x-3)ex-m=0 Find, for any given m, the number of roots that the equation has.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Hmm, apparently not even I know what's going on, since I phrased the question wrong xD. Anyway, here's the context. I was coding a renderer for fractal flames, and when I got a sample picture, I realized that normal renderers were plotting the picture with the y axis flipped. I had no idea why, because I had remembered to flip the y axis when saving the image. Eventually I realized that it was all because my renderer was serializing the coefficients of the affine transformation differently than traditional ones, and that was causing the flip. For example, when regular software showed a positive coefficient somewhere, it would save a negative one in the file anyway. So I had to figure out how to change them so that I got a flipped transform. The answer, in this question's notation, is to actually negate d, e, and c. My reasoning was: the point (0,0) was sent to (a,d), now it goes to (a,-d), so d must flip. (1,0) was sent to (a+b,d+e), now (a+b,-d-e), so e must also flip. But the y axis was also flipped, so if before we had (0,1) sent to (a+c,d+f), we now need (0,-1) to go to (a+c,-d-f). For this to happen, we need to keep f the same, and flip c. But now I realize that the transformation U we need is actually defined by U(x,-y)=T(x,y)*. Does anyone know why it's this transformation we must consider instead of the other definition?
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Here's one that I came across recently. It's simple but tricky. Suppose you have a two-dimensional affine transformation T defined by six parameters as: x' = a + bx + cy y' = d + ex + fy From this transformation derive another transformation U such that U flips the y axis, that is, if we let (x,y)* = (x,-y), we should have for every point: U(x,y)=T(x,y)* How do the coefficients of U relate to those of T?
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Since this looks like a homework problem, I'll only give a hint. Notice how Rudin proves that the n-th square root makes sense. He proves that x^(1/n) exists for x>0 in the way sketched below: (a) He shows that the set A of real numbers y>0 such that y^n < x is bounded from above, and since the reals are complete, has a least upper bound. (b) if we denote y = sup A, then there are only three options: y^n < x, y^n = x, y^n > x (c) he then shows that if y^n < x, he can construct a larger y that still satisfies the inequality. similarly, if y^n > x, he can construct a smaller y still satisfying the inequality (d) from this, assuming that y^n < x or y^n >x you conclude that y is not the least upper bound of A. Therefore, it must be true that y^n = x From this, it makes sense to define x^(1/n) as the supremum of the set A = {y in R | 0 < y^n < x }. Notice that this is what we call an ineffective result. It merely shows by contradiction that a result exists, but provides no way to actually calculate it. This is pretty typical of the most fundamental results of real analysis. Now, to your first exercise, you need to show that (b^m)^(1/n) = (b^p)^(1/q) if m/n = p/q. Notice that we have two root operations instead of one. Following Rudin's definition, we should look at these two sets: A = { y in R | 0 < y^n < b^m }, B = { y in R | 0 < y^q < b^p } Can you say something meaningful about these sets that could be useful to relate their supremum?
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
So, if you remember my previous posts studying the Apollonian gasket, I managed to improve to the point where I can do 4K zooms of it. See the video: Link to video Explanation here.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
Just to clarify, I'm not saying that it's "bad" to use calculus to solve this problem. Any proof is as good as any other. However, one important part of studying math is to get used to different techniques, so you should always have the habit of, when you find a solution, see if it has some special properties, because often this highlights another way to tackle the problem. In this case, if you solve with calculus you could try to guess what makes the quadrilateral that solves the problem so special, and then you would find that it's cyclic, has right angles, etc.
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
There's a way to do it without calculus. Let alpha be the angle between the sides of lengths 4 and 7. The area of the kite is 28*sin(alpha), so it's maximized for alpha = 90 degrees. For this angle, one diagonal can be evaluated using pythagoras' theorem: sqrt(4*4+7*7) = sqrt(65). Also, the quadrilateral is cyclic, so we can apply Ptolemy's theorem: x*sqrt(65)=4*7+7*4 => x=56/sqrt(65)
Experienced Forum User, Player, Published Author (42)
Joined: 12/27/2008
Posts: 873
Location: Germany
It took me a long time to write my post about Iterated Function Systems and Apollonian gaskets, but I think it was worth it because I got a very elegant solution to the problem. Here is the medium post.