Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Hi agwawaf.
The glitch works as follows:
Addresses 7E:1628, 7E:1658, 7E:1688, 7E:16B8, ...
are memory for objects like items, moving platforms, and doors. Each slot is 48 bytes. When an object is produced, the game places it in the lowest empty spot in memory. When an object is removed, the game removes it from memory without changing any other slots.
The boomerang glitch happens when an object is produced at the exact same slot and at the exact time that the game removes an object held by the boomerang cutter.
The method in your movie (which I tried earlier) doesn't work because the life recovery item was produced while the platforms were already in memory. As far as I know, the only way to start the glitch in this area is with the heart tank (life up).
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
The Brookman wrote:
I'm on a Dell with intel core 2 duo cpu p8400 2.26 ghz with 4.00GB ram.
Bizhawk is running my SNES game at ~25 fps. and i can't increase or reduce the frame rate significantly even at 6400% increase it runs at ~25 fps.
Would disabling "Use Ring Buffer IO" improve the fps for you? (When SNES ROM is loaded, SNES -> Options -> Uncheck "Use Ring Buffer IO".)
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Hetfield90 wrote:
What lua should I be using to see X/Y position values in snes9x (or BizHawk for that matter if there is one)? The one I'm trying to use now is giving me an error that says "\megamanx.lua:29: attempt to index local 'fle' (a nil value)".
Apparently, BizHawk's Lua has changed so much from Snes9x's Lua that it's not something I can fix right away.
In any case, the original megamanx.lua requires the file "lookup.xyz" in the same folder for it to work (lookup.xyz is a reverse lookup table for RNG values). It should at least work in Snes9x. Here are the files if you need it for whatever reason.
You can have a look at the RAM Map posted on this site. The memory for player X-position is 2-byte 7E:0BAD (pixels) and 1-byte 7E:0BAC (subpixels). The memory for player Y-position is 2-byte 7E:0BB0 (pixels) and 1-byte 7E:0BAF (subpixels).
Edit:
Hetfield90 wrote:
Does that essentially mean that (1600,252) is the upper left corner of the area which the 2nd set of platforms spawns, and then you just fly horizontally from there until you drop down to get past the corner of the building (and the e-tank spawns as some point during that horizontal movement)? If so that would make this pretty simple and easy to optimize.
I don't think "upper left corner" is the best way to describe it. More like (1600,252) and below is the left edge of the spawn area for the 2nd set of platforms.
Even then, there seems to be some hidden condition that may allow the platforms to spawn even when a little bit above (1600,252). It may be camera-related.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Here's a route to keep the flying platform from the first area and get the E-tank.
http://tasvideos.org/userfiles/info/20391573293448651
To allow the E-tank to spawn, Y-position must be higher (lesser) than 252, at X-position 1600; this is a necessary condition; otherwise the second set of platforms will load and prevent the E-tank from spawning. However, there seem to be other conditions that I do not fully understand. However, going horizontally at Y-position 225 as in the movie above seems to work.
I tried other stuff in the movie but it didn't work out. It is not possible to keep the platform throughout using the capsule (and it causes a lot of lag as well). You can go back to the second area's platforms and grab one, but it will disappear unless maybe you can get high enough (don't know how). The dropping platforms at the end cannot be grabbed; doing the boomerang glitch will just make them disappear.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Haha, what's with the random Idolmaster in your videos.
Anyway, for the any%, I think it is faster to use the boomerang glitch on the second set of platforms (as shown in http://tasvideos.org/userfiles/info/20389114088716596). The platform is a bit more annoying to deal with though. It is easy to end up standing on top of it, and then there is no way to fall off of it (without being bumped off by a ceiling or going off the top of the map, which loses the platform). So the only way to travel a long distance involves doing wall kicks on the side of the platform. Also, the platform disappears near the capsule location unless you are high enough.
I know the E-tank tends to disappear (if you boomerang grab the first platform) but I haven't tested it enough. In fact, I didn't know it was possible to keep the platform and not have the E-tank disappear before you showed that it was possible.
Edit:
I figured out the E-tank disappearing thing.
If you keep the platform that you boomerang grabbed by going high enough, then the first set of platforms will remain in active memory. If you then activate the second set of platforms, memory will be overloaded and you can't load the E-tank. To avoid this, you must be higher (have lesser Y-position value) than Y-position 252, at X-position 1600.Edit 2: Scratch that. Apparently the last sentence isn't true.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Hetfield90 wrote:
Also, interestingly enough you can even grab things that aren't even items with it, such as boss doors. I wonder if you can even grab capsules with it, lol.
Interesting glitch. Apparently, with the glitch, you can grab anything that spawns on the misc. objects list (starting at $7E:1628 and each object is 48 bytes); all item drops, heart tanks, and sub tanks are added to this list, as well as movable platforms and doors. Unfortunately, capsules are not added to this list.
I managed to grab a platform. The results are interesting. (Note: This movie uses Snes9x 1.43 v17 and Mega Man X V1.1). Basically, if a boomerang grabs a platform, you can use it to fly around.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
ars4326's translation looks good.
The rest of it:
----
異界に行くために銀色の機械を壊す必要がある
In order to go to the alien world, the silver-colored machinery must be destroyed.
GP Gyalivanpoint 8個集めると8回ダメージを半分にできる鎧を身に着けることができる
GP: Collecting 8 of them allows you to wear armor that cuts damage in half 8 times.
CP Cristalpoint weapon itemに分類されるものを使用する際に必要 特定の敵を倒すと回復アイテムドロップ
CP: Need this to use special weapons and items. You can defeat special enemies to drop CP restoration items.
・取得したweapon ハイパーレイ 赤いゲートを開けるために必要 1回5cp 扉を開けるために3回使う必要がある
Hyper Ray is needed to open the red gate. One use costs 5 CP, and it must be used 3 times to open the gate.
・取得したitem スタークリスタル 異界にいく隠しマップのエレベータを出現させるために必要 1回10cp
Star Crystal is needed to make the hidden elevator to the alien world appear. One use costs 10 CP.
なお、出現したエレベーターで同じバグを使用すると1画面下のMAP(ハイパーレイを取ったMAPの通路)にそのまま移動する
Furthermore, if you use the same bug on this elevator (instead of the one in the TAS), you can move around on the "map" below screen 1.
----
By the way, there is a guide on GameFAQs in English. It calls the alien world "Area 1-1" and the silver machinery enemy (or whatever it is) "computer". That's just that guide's name, I think.
also can you zip upward ? or zip downward elsewhere ( like spark mandrill shaft before the bubble boss or launch octopus heart ? )
I've tested it before (and probably parrot14green), but as far as I know, it is not possible to zip/glitch upward. There are other places to zip downward, but if you bypass the horizontal scroll trigger, then you can't progress (such as before the Spark Mandrill miniboss).
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
ALAKTORN wrote:
I think it was FractalFusion who was fluent in Japanese.
I'm not actually fluent. I can work hard to translate; that's all.
If you have something you want to translate from Japanese to English, I can help out.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Hm. Since the last time I posted here which was over a year ago, I watched a lot more anime:
- Tonari no Seki-kun
- Danganronpa (anime)
- Vividred Operation
... ok, that wasn't much. I also watched about 40 episodes of Aikatsu! at random; do note that it is a kids show (like Precure) and I don't think it's worth watching unless you want to learn Japanese by listening.
I've finally decided to follow at least some anime on a weekly basis (i.e. as it airs), which I never really did before.
Though this could change, I'm currently following Kantai Collection (Kancolle) the anime, Idolmaster Cinderella Girls the anime, and Ansatsu Kyoushitsu (known in some places as Assassination Classroom or Ass Class). The first two already have existing fanbases from popular game media (easy justification from my point of view) and for the third one I followed the manga and liked it.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Hetfield90 wrote:
Is the thing in Spark Mandrill you're talking about something like using the sled to glitch though the first wall and forgo the first 2 ladders with the same trick from Sigma 3 in your glitched walkathon?
Yes, it is like that. If you glitch into a wall that is thin enough, you can jump out the other side. I don't remember how exactly it works but I vaguely remember pulling it off. I did it on one of the walls to go from the Sub-Tank route back to the main route.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Good job, Hetfield90, and thanks for picking up where I left off.
Sorry that I didn't reply to your message; I forgot about it because I don't sign in to this site much anymore, and I forgot whatever I did to manipulate Vile in the intro stage (probably just trial and error).
There is a trick to glitch through the walls near the beginning of Spark Mandrill's stage using charged Shotgun Ice. I don't know if it is faster.
ALAKTORN wrote:
In the intro stage against the bee minibosses, why don’t you jump as they enter the screen to start shooting (and therefore hit them) sooner?
If I remember correctly, it's because the bee minibosses do not take hits until they stop going down and start attacking you.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Well done, everyone!
And thanks for all the time you've spent preparing for this occasion, dwangoAC. I didn't think previously that my Pokemon notes would have been of any real use.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
- BizHawk 1.7.0 and later are known not to work on some video cards (mainly older computers); it certainly doesn't work for me on the computer I am using now.
- For BizHawk version earlier than 1.7.0, the SNES portion could possibly be made faster by disabling the "Use Ring Buffer IO". To do this, load a SNES ROM, then go SNES -> Options and uncheck "Use Ring Buffer IO". I say "could possibly" because I don't know what your problem specs are, but disabling this option makes it much faster if your computer is single-core. It may still be slow though.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
HHS wrote:
For an arbitrary convex, simple quadrilateral ABCD in 3D space, define an S axis that goes from 0 to 1 along AB, and a T axis that goes from 0 to 1 along AD. Having defined a value at each corner, and wanting to find the corresponding value at some point (S,T) using bilinear interpolation, how does one determine the coefficient before ST?
Edit: Perhaps what I am trying to do is not even possible?
If I understand the question correctly, we're trying to fit a function to some values given at the corners of convex simple quadrilateral ABCD, such that the function is bilinear along AB (S-axis) and AD (T-axis). In particular, ABCD is coplanar and no three points are collinear.
In ST-coordinates, A=(0,0), B=(1,0), and D=(0,1). The important thing is to find the ST-coordinates of C. Let v(AB), etc., denote the vector from A to B in its original coordinates. We can find the ST-coordinates of C by solving the matrix equation [v(AB) v(AD)][s,t]T=[v(AC)] for s and t (equivalently, v(AB)s+v(AD)t=v(AC)). There is a unique solution; if there were no solution, then ABCD would not be coplanar; if there were infinitely many solutions, then ABD would be collinear. Let C=(s0,t0) in ST-coordinates. Note that s0 and t0 are nonzero; otherwise ABC or ACD would be collinear.
Let a,b,c,d be the values at A,B,C,D, respectively. We want to fit a bilinear function f(s,t)=w+xs+yt+zst to these values, where (s,t) is the point in ST-coordinates. Then
f(0,0)=w=a
f(1,0)=w+x=b → x=b-a
f(0,1)=w+y=d → y=d-a
f(s0,t0)=w+xs0+yt0+zs0t0=c
→
z=(c-a-(b-a)s0-(d-a)t0)/(s0t0)
This z would be the coefficent of st in f(s,t).
Note that it is not important which vector space ABCD is embedded in or which vector space the values assigned to the corners of ABCD come from; this process applies in any case. In fact, this process may apply even if ABCD is not a convex and/or simple quadrilateral; the only condition is that ABCD is coplanar, and that ABC, ABD, and ACD are not collinear.
Edit: Fixed solution for z; it was missing an "a".
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Amaraticando wrote:
This was a question in a mathematical olympiad that I've done. Determine all the functions f:ℝ→ℝ such that f(xf(y) + f(x)) = 2f(x) + xy , for all x, y in ℝ.
This is a very difficult question (expected for a mathematical olympiad). I'm still working to see if I can solve it fully; the farthest I have gotten is to show that if f is such a function, then f(x)=x+1 for all integers x.
Edit:
OK, I finally figured out how to do the question. The crux of the question is to figure out that f(-2)=-1, and then put y=-2 into the above equation. Here is my solution:
Based on the equation f(xf(y)+f(x)) = 2f(x)+xy, we know that f(x) is an onto (surjective) function; given a real number c, simply choose x≠0 and y=(c-2f(x))/x and the RHS becomes c. So, choose a,b such that f(a)=1 and f(b)=0. Then f(bf(a)+f(b))=2f(b)+ba, which gives 0=ba. Therefore either a=0 or b=0.
If b=0, then f(0)=0. Then f(xf(0)+f(x))=2f(x)+x*0, which gives f(f(x))=2(f(x)). Since f is onto, that means f(z)=2z for all real z. But then f(1f(1)+f(1))=2f(1)+1*1, which gives 8=5, contradiction.
So a=0, and thus f(0)=1. Now f(-1f(-1)+f(-1))=2f(-1)+(-1)*(-1) gives f(0)=2f(-1)+1, or f(-1)=0. Then f(xf(-1)+f(x))=2f(x)+x*(-1), which gives f(f(x))=2f(x)-x, or x=2f(x)-f(f(x)). Solving the equation f(x)=-1 by substitution gives the only possibility x=2*(-1)-f(-1), or x=-2; since f is onto, that means f(-2)=-1.
Now f(xf(-2)+f(x))=2f(x)+x*(-2), which gives f(f(x)-x)=2*(f(x)-x). Consider the non-empty set {f(x)-x|x in ℝ} and let d be an element of the set. Then f(d)=2d. Taking x=2f(x)-f(f(x)) and using it to solve the equation f(x)=d by substitution gives the only possibility x=2d-f(d), or x=0; since f is onto, that means f(0)=d. But since f(0)=1, that means d=1. Since this holds for every element of {f(x)-x|x in ℝ}, that means {f(x)-x|x in ℝ}={1}, and so f(x)-x=1 for every real x, and therefore as a function, f(x)=x+1.
Interestingly, the solution is pretty much the same even if we allow f to be a function from complex numbers to complex numbers.
By the way, Amaraticando, you said that this was a question on a math olympiad that you did. Did you do and/or solve this question during the olympiad?
Edit 2: Actually, if you replace "choose x≠0 and y=(c-2f(x))/x" with "choose x=1 and y=c-2f(1)", the same logic applies whenever f is a function on an integral domain.
Edit 2.5: Oops, a bit of an error on the last edit. If f is a function on an integral domain where 3=0 (e.g. mod 3), then the apparent solution of f(z)=2z in the case b=0 (f(0)=0) is in fact a solution, since f(xf(y)+f(x)) = 2f(x)+xy gives 4xy+4x=4x+xy and both sides are always equal since 4=1.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
The region of intersection is "obviously" a warped unit square. Thus the area is 1. For certain values of 1, anyway.
But I digress. If this question has some kind of fancy solution, I don't know about it. So I'll just do it the direct way. Warning: wall of computation incoming.
Rotate the diagram about the origin so that the common center of the two circles not centered at the origin is (√17,0) instead of (4,1). This doesn't change the area and makes the following calculations more tolerable.
We then look for the x-values of the intersections of a circle x2+y2=p2 with a circle (x-√17)2+y2=q2 for p in {2,3} and q in {3,4}. Solving the equations gives -2(√17)x+17=q2-p2, or x=(17+p2-q2)/(2√17)=(17+p2-q2)α, where α denotes 1/(2√17) for obvious clarity. Concern ourselves with only the intersections in the first quadrant (positive y).
-For p=2,q=3 (bottom intersection), x=12α.
-For p=2,q=4 (left intersection), x=5α.
-For p=3,q=3 (right intersection), x=17α.
-For p=3,q=4 (top intersection), x=10α.
Now, we derive a formula for computing the area under a unit circle and above the x-axis from x=a to x=b:
int[a,b] sqrt(1-x2)dx=int[*,**] sqrt(1-sin2(θ))cos(θ)dθ (x=sin(θ))
= int[*,**]cos2(θ)dθ=int[*,**] (1+cos(2θ))/2 dθ
= (1/2) θ [θ=*,**] + (1/4) sin(2θ) [θ=*,**]
= (1/2) θ [θ=*,**] + (1/2) sin(θ)cos(θ) [θ=*,**]
= (1/2) (θ [θ=sin-1(a),sin-1(b)] + x sqrt(1-x2) [θ=a,b])
= (1/2) ( sin-1(b)-sin-1(a) + b sqrt(1-b2) - a sqrt(1-a2) )
Therefore the area under a circle of radius r centered at (p,0) and above the x-axis from x=a to x=b is:
Area(r,p,a,b)=(r2/2) ( sin-1(B)-sin-1(A) + B sqrt(1-B2) - A sqrt(1-A2) ),
where A=(a-p)/r and B=(b-p)/r.
Then the area we want is the sum of:
(noting that √17=34α)
* Area(4,√17,5α,10α) (upper left boundary)
= 8 ( sin-1(29α/4) - sin-1(6α) + (29α/4) sqrt(1-(29α/4)2) - 6α sqrt(1-(6α)2) )
* Area(3,0,10α,17α) (upper right boundary)
= (9/2) ( sin-1(17α/3) - sin-1(10α/3) + (17α/3) sqrt(1-(17α/3)2) - (10α/3) sqrt(1-(10α/3)2) )
* -Area(2,0,5α,12α) (lower left boundary)
= -2 ( sin-1(6α) - sin-1(5α/2) + 6α sqrt(1-(6α)2) - (5α/2) sqrt(1-(5α/2)2) )
* -Area(3,√17,12α,17α) (lower right boundary)
= (-9/2) ( sin-1(22α/3) - sin-1(17α/3) + (22α/3) sqrt(1-(22α/3)2) - (17α/3) sqrt(1-(17α/3)2) )
The sum is:
8 sin-1(29α/4) - 10 sin-1(6α) + 9 sin-1(17α/3) - (9/2) sin-1(10α/3) + 2 sin-1(5α/2) - (9/2) sin-1(22α/3)
+
α [ 8 (29/4) sqrt(247/1088) - 10 (6) sqrt(8/17) + 9 (17/3) sqrt(19/36) - (9/2) (10/3) sqrt(128/153) + 2 (5/2) sqrt(247/272) - (9/2) (22/3) sqrt(32/153) ]
=
8 sin-1(29α/4) - 10 sin-1(6α) + 9 sin-1(17α/3) - (9/2) sin-1(10α/3) + 2 sin-1(5α/2) - (9/2) sin-1(22α/3)
+
α [34 sqrt(247/272) - 102 sqrt(8/17) + 17 sqrt(19/4)]
(try evaluating in a calculator)
≈1.07578-0.06317=1.01261≈1.013
Well, that was a mess, wasn't it? Might as well just say that the area is 1.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Archanfel wrote:
Amaraticando wrote:
New problem: just find the exact value of x.
x2=12-A2
and
(1+x)2+12=(1+{(1-A)2+12})2
Two equations and two unknowns. It should be quite easy to calculate.
x≈0.8832
Based on Archanfel's labelling above, we have
x2+A2=1
A/x=(1-A)/1
So A=x/(1+x). Substituting into x2+A2=1 and multiplying by (1+x)2:
x2+(1+x)2x2=(1+x)2
→ x4+2x3+x2-2x-1=0
This is a quartic equation, of which the quartic formula is an utter mess. But let's try adding 2(x2+2x+1) to both sides:
x4+2x3+3x2+2x+1=2(x2+2x+1)
→ (x2+x+1)2=(sqrt(2)(x+1))2
Magic! Both sides are a perfect square! (In the real polynomial ring, of course. 2 isn't a perfect integer square, but we aren't restricting to integers here.)
So then x2+x+1=±sqrt(2)(x+1). Let's only take the positive one (the negative one gives complex numbers). So then
x2+x+1=sqrt(2)(x+1)
→ x2+dx+d=0, where d=1-sqrt(2)
→ x=(1/2)(-d±sqrt(d2-4d))=(1/2)(sqrt(2)-1±sqrt(3-2sqrt(2)-4+4sqrt(2))
→ x=(1/2)(sqrt(2)±sqrt(2sqrt(2)-1))
Since x is positive, we take the positive: x=(1/2)(sqrt(2)-1+sqrt(2sqrt(2)-1)), which is about equal to 0.8832.
Note that A equals the absolute value of the negative root, which is about 0.4690.
Note also that x and A are constructible numbers. I leave it to others to figure out a straightedge and compass construction for x from a unit-length line segment.
For those wondering how I knew to add 2(x2+2x+1) to both sides of x4+2x3+x2-2x-1=0, well, I cheated. I used Wolfram Alpha's Root Finder to find what x was, then reconstructed its minimal polynomial (which is the polynomial above), thus back-solving for the method needed to find x in the first place.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Masterjun wrote:
I always wondered how it is possible to find a reverse formula of a linear congruential generator.
For example we have the formula:
X(n+1) = ( ( 0x41C64E6D * X(n) ) + 0x3039 ) mod 0x100000000
which, starting with 0, gives you values: 0, 12345, 3554416254, 2802067423...
So I wonder how it is possible to calculate this reverse formula:
Y(n+1) = ( ( 0xEEB9EB65 * Y(n) ) + 0xFC77A683 ) mod 0x100000000
which gives the expected values: ...2802067423, 3554416254, 12345, 0...
The inverse of x → Ax+B (mod N) is y → A-1y - A-1B (mod N). Assuming gcd(A,N)=1, of course. The inverse takes Ax+B to A-1(Ax+B) - A-1B = x (mod N), for all x.
The multiplicative inverse of A mod N can be computed by the extended Euclidean algorithm. But for the case when N=2m, it's even easier. The process is simply to solve Ax=1 (mod 2m) by writing in binary and determining the bits of x from right to left (least significant to most significant) as follows:
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
For the last question (pentagon and square arrangement of unit circles problem):
Let the center be the origin. Take a point where the inner circles touch and rotate the diagram so it is on the positive x-axis. Then the inner and outer circle in quadrant I touching the x-axis form the following diagram (not perfectly to scale):
Then x=tan 54° and so the distance from the origin to the center of the outer circle is sqrt(x2+4x+5)=sqrt((tan 54°)2+4(tan 54°)+5)
Therefore, the radius of the big circle (enclosing the outer circles) is one unit more; that is, sqrt((tan 54°)2+4(tan 54°)+5)+1. You can substitute tan 54°=φ/sqrt(3-φ) if you like (φ is the golden ratio (1+sqrt(5))/2), but I won't do that here. The number comes out to be about 4.521, close to Flip's estimate.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Bobo the King is right (and I can see where he got that guess; in each case of odd or even, the count is nothing more than sequential sums of polynomials of degree 2, which are polynomials of degree 3), but let's actually go through with a proof. Mere counting is overrated; let's go find a recurrence first thing.
Let Tn be the big triangle of size n and an be the count of triangles (of any size and orientation) in it. Let n≥3. Let Ta, Tb, Tc be the subtriangles of Tn formed by removing the bottom row, top right diagonal, and top left diagonal, respectively; note that each one forms a Tn-1, the intersections of two of them form a Tn-2, and the intersection of all three forms a Tn-3. Obviously this calls for inclusion-exclusion.
Let Ca, Cb, Cc be the conditions that a subtriangle of Tn is contained in Ta, Tb, Tc, respectively. The notation N(condition) means "number of objects in sample space satisfying condition". Then, taking the sample space to be all subtriangles of Tn,
an = M + N(Ca) + N(Cb) + N(Cc) - N(CaCb) - N(CaCc) - N(CbCc) + N(CaCbCc)
= M + 3an-1 - 3an-2 + an-3,
or, in other words,
an - 3an-1 + 3an-2 - an-3 = M,
where M = N(not (Ca or Cb or Cc)). A subtriangle of Tn is contained in none of Ta, Tb, Tc if and only if it touches all sides of Tn. The only up-pointing triangle satisfying this is the whole Tn. The only down-pointing triangle satisfying this is when n is even, and it is the triangle joining the midpoints of each side of Tn. Thus, M=1 if n is odd, and M=2 if n is even. So M = 3/2 + (1/2)(-1)n.
The recurrence is thus:
an - 3an-1 + 3an-2 - an-3 = 3/2 + (1/2)(-1)n (n≥3), a0=0, a1=1, a2=5.
The characteristic equation of this recurrence is r3-3r2+3r-1=(r-1)3. Therefore there exists constants A,B,C,D,E such that
an=A+Bn+Cn2+Dn3+E(-1)n,
where Dn3+E(-1)n is a particular solution of the recurrence. Substituting Dn3+E(-1)n for an in the recurrence gives 6D + 8E(-1)n = 3/2 + 1/2 (-1)n for all n≥3, so 6D=3/2 (D=1/4) and 8E=1/2 (E=1/16). So
an=A+Bn+Cn2+(1/4)n3+(1/16)(-1)n, a0=0, a1=1, a2=5.
Substituting the initial conditions gives A+(1/16)=0 (A=-1/16), A+B+C+(1/4)-(1/16)=1 (B+C=7/8), and A+2B+4C+2+(1/16)= 5 (B+2C=3/2). The last two give C=5/8, B=1/4. So
an= (1/4)n3 + (5/8)n2 + (1/4)n - 1/16 + (1/16)(-1)n = (1/8) (2n3+5n2+2n-((1/2)-(1/2)(-1)n)),
and (1/2)-(1/2)(-1)n is 1 if n is odd, and 0 if n is even. This agrees with Bobo the King's result.
I think it should be possible to derive this by a straight counting argument like Bobo the King has tried, but I'll leave it for someone else.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Flip wrote:
-If surrounding the central circle with smaller ones, what radius would they need to be in order to have exactly 8 surrounding it instead?
Suppose that there are n smaller circles of radius x surrounding a central circle of radius 1. The centers of all the smaller circles then lie on a circle of radius 1+x, and the arc between the centers of two consecutive circles has angle 2π/n.
So there is an isosceles triangle with sides 1+x, 1+x, 2x, and the angle opposite 2x is 2π/n. By the cosine law,
4x2=(1+x)2+(1+x)2-2(1+x)2cos(2π/n)=(1+x)2(2-2cos(2π/n))
This gives x=(1+x)sqrt(1/2 - (1/2)cos(2π/n)). However, cos(2π/n)=1-2sin(π/n)2. So the above equation simplifies to x=(1+x)sin(π/n), or x=sin(π/n)/(1-sin(π/n)). This agrees with r57shell's answer.
For n=8, sin(π/8)=sqrt(2-sqrt(2))/2, so we get x=[sqrt(2-sqrt(2))]/[2-sqrt(2-sqrt(2))]=[2sqrt(2-sqrt(2))+2-sqrt(2)]/[2+sqrt(2)], which is about equal to 0.62.
thatguy wrote:
And, AFAIK, the case for spheres is still an open problem today
According to Wikipedia, the sphere packing problem has been solved for over 15 years already.
Then x=tan 54° and so the distance from the origin to the center of the outer circle is sqrt(x2+4x+5)=sqrt((tan 54°)2+4(tan 54°)+5)
Therefore, the radius of the big circle (enclosing the outer circles) is one unit more; that is, sqrt((tan 54°)2+4(tan 54°)+5)+1. You can substitute tan 54°=φ/sqrt(3-φ) if you like (φ is the golden ratio (1+sqrt(5))/2), but I won't do that here. The number comes out to be about 4.521, close to Flip's estimate.