Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
HHS is correct, but I'll try to show more detail. Unfortunatly the notation gets pretty awful and I don't know how to write in LaTeX on here. Apologies in advance.
Anyway, the left hand side can be written as the
sum over k [ sum over permuations [ sgn(sigma) * product over i [ a_i,sigma(i) + w^k * b_i,sigma(i) ] ] ]
The sum over k can be brought inside to behind the product. For a given sigma, let's now look at
sum over k [ product over i [ a_i,sigma(i) + w^k * b_i,sigma(i) ] ] =
(a_1,sigma(1) + w^0 b_1,sigma(1))*...*(a_n,sigma(n) + w^0 b_n,sigma(n) ) +
(a_1,sigma(1) + w^1 b_1,sigma(1))*...*(a_n,sigma(n) + w^1 b_n,sigma(n) ) + ...
Expanding the brackets we can identify 3 types of terms.
1) products of only a's
These will be of the form a_1,sigma(1)*a_2,sigma(2)*...*a_n,sigma(n) and there are exactly n copeis of them.
2) products of only b's
These will be of the form w^k b_1,sigma(1)*...*w^k b_n,sigma(n) = w^(nk)*b_1,sigma(1)*...*b_n,sigma(n)
Again, there are exactly n of them and w^(nk) = 1 by definition of w.
3) Cross terms
These will be of the form
c_1,sigma(1)*c_2,sigma(2)*...*c_n,sigma(n)*w^(km)
Where c could be either a or b and m is equal to the number of b's chosen. Summing over k doesn't affect the form of the c factors and so we can identify a group of terms all involving the same c's, but with differnet powers of w. This can be factorised to
c_1,sigma(1)*c_2,sigma(2)*...*c_n,sigma(n)*[w^0 + w^m + w^(2m) + ... + w^((k-1)*m)]
However we know that the w sum is 0. (For example, these are the solutions to x^n - 1 = 0, which has no term with power n-1)
Therefore cross terms all cancel and we are left with.
n*(a_1,sigma(1)*...*a_n,sigma(n) + b_1,sigma(1)*...*b_n,sigma(n))
Putting back in sgn(sigma) and the sum over permutations gets us the final result.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
I got the same answer using Pythagoras a few times
Let A be the centre of the upper large circle, B be the centre of the left medium-sized circule, C be the centre of the let small circle and D be the centre of the rectangle (where the two large circles meet).
The radius of the big circle is obviously 8/4 = 2
Let R be the radius of the medium-sized circle. Using Pythagoras on triangle ABD gives
(R + 2)^2 = 4 + (3 - R)^2, which gives R = 9/10
Now let r be the radius of the small circle and use Pythagoras on triangle ACD. I get
(r + 2)^2 = 4 + (6/5 - r)^2
which gives r = 9/40
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
I have a semi-complete answer to the resistor problem that seems to get the answer in a different form.
Label each node using a string of bits that represent its coordinates. e.g. 1101 would be (1,1,0,1) in 4 dimensions. Let I(n,n+1) be the current flowing from a node with n 1s in its bit string to a node with n+1 1s in its bit string. I claim that this current doesn't depend on which particular segment you consider by symmetry (I couldn't think of a simple way to show this algebraically, but it seems obvious to me).
Consider the path from 00...0 to 11...1 where each bit is flipped from 0 to 1 sequentially from left to right (i.e. 000 -> 100 -> 110 -> 111 in 3D). Normalising each current by the current through the battery and using Kirchoff's voltage law, we have R = I(0,1) + I(1,2) + I(2,3) + ... + I(N-1,N). Conisder now the node along the path with k 1s in its bit string and therefore N-K 0s. Moving along any of the N different paths that join at the node corresponds to flipping one of the bits. The paths corresponding to flipping a 1 have current I(k-1,k) and the paths corresponding to flipping a 0 have current I(k, k+1). By Kirchoff's first law we have k*I(k-1,k) = (N-k)*I(k,k+1), which holds for k = 1, ... , N-1. In addition, at the ends, we have 1/N = I(0,1) = I(N-1, N).
Solving these equations gives
I(0,1) = 1/N
I(1,2) = 1/(N-1) * 1/N
I(2,3) = 2/(N-2) * 1/(N-1) * 1/N
...
I(N-1,N) = (N-1)/1 * (N-2)/2 * ... * 1/(N-1) * 1/N = 1/N
So, I(k-1,k) = (k-1)! / [ N!/(N-k)! ] = 1/k * k! / [ N!/(N-k)! ] = 1/k * 1/(N choose k)
Hence R = sum_{k=1}^{N} of 1/(k * N choose k)
It's not obvious at all to me that this is the same as the answer you provided, but it seems to agree numerically. I guess it follows from some identity involving binomial coefficients, but I wouldn't know which one.
Chanoyu wrote:
I'm thinking your hypothesis is false, but I just have a thought, and that's far from a proof. A rational number can be written as x/y. By allowing negative a1 etc., you get the 1/y part. But what about a number x/y where you need the same number p1, p2, or p3 to make both x and y?
In that case the numerator and denominator wouldn't be relatively prime and you could simplify the fraction.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
Apologies in advance for my lack of LaTeX.
The sum is equal to
1/(n-2020) + 1/(n-2019) + ... + 1/n + 1/(n+1) + ... + 1/(2n) + 1/(2n+1) + ... + 1/(2n+2020)
= 1/n + 1/(n+1) + ... + 1/(2n) + other terms
The 'other terms' is a finite series of fixed length and each term goes to 0 as n goes to infinity. Hence the original sum is equal to the limit of S(n) = 1/n + 1/(n+1) + ... + 1/(2n)
This is bounded below by the integral of 1/x from n to 2n+1, which is log(2+1/n) and bounded above by the integral of 1/(x-1) from n to 2n+1, which is log(2n/(n-1)) = log(2 + 2/(n-1))
So log(2 + 1/n) < S(n) < log(2 + 2/(n-1))
Hence S(n) tends to log(2) by the squeeze theorem.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
I feel like you've basically proven your own claim. You've given a list of constraints and are asking 'is it possible to list all the rational numbers between 0 and 1 to within these constraints?' On first glance, since the constraints seem fairly restrictive, it's not intutive to me that it should be possible. The fact that it isn't possible is simply demonstrated by finding examples of rational numbers that aren't contained in the list. You found one yourself and another one would be 0.10000000001... (put a 1 when a 0 should occur and 0s elsewhere), which is clearly rational. You can easily find many more.
I don't think there's much more to it than that. The list is incomplete because it assumes an ordering that is too restrictive to contain all the rational numbers. Rather than looking for an intuititve reason for why it isn't possible, I'd rather ask 'why did you think that list would have contained all the rational numbers?'
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
DrD2k9 wrote:
EDIT: Another way to look at it, (possibly more simply), it's the effect of inertia and the balance of forces on your own body's mass in relation to the earth that affect how heavy you feel.
When moving upward, you have to accelerate your own center of mass using at a force greater than that of gravity to ascend the ladder.
When moving downward, you only have to match gravity's force to ascend the ladder and keep your own center of mass suspended in space. Thus it feels easier.
Why? Suppose I am standing in the elevator. Even if the elevator is moving down (relative to the surface of the Earth) at a constant speed, I will have a weight, mg, which, when standing, is balanced by the reaction force from the floor, i.e. it'll feel exactly the same as being stationary standing on the surface of the Earth. If I want to accelerate myself upwards, I will need to exert a force that is greater than mg. If I only 'match gravity's force', then my net force will be 0 and I won't accelerate. From the point of view of someone on the Earth's surface, if I 'match gravity', then my net force is 0, but since I was already moving down at the same rate as the elevator, I will continue to do so and remain stationary relative to the elevator's floor.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
I have a fairly ugly function that may or may not be what you're looking for. Apologies in advance for the poor notation.
You can add zeros to the end of digits by multiplying each digit by powers of 10. Let f(N, x) be the number x with N zeroes added to the right of each digit. You can construct f using a series:
f(N, x) = sum from r=1 to infinity of [ 10^(r(N+1) - 1)*g(r, x) ],
where g(r, x) gives you the r'th digit of x and ideally g(r, x) = 0 once r is greater than the total number of digits in x. Alternatively, you can just write it as a finite sum up to the number of digits in x. What is g? With a bit of playing around I got it in terms of the floor function:
g(r, x) = floor(x/10^(r-1)) - 10*floor( floor(x/10^(r-1)) / 10)
Overall...
f(N, x) = sum from r=1 to infinity of [ 10^(r(N+1) - 1)*[ floor(x/10^(r-1)) - 10*floor( floor(x/10^(r-1)) / 10) ] ]
Adding zeros to the left of a number is really the same problem: just add zeros to the right of the digits but start from the 2nd digit instead (and then stick the very first digit on the end, e.g. by multiplying everything by 10 and adding the first digit).
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
Haha, what a crazy 'run'. To be honest, I don't really get any enjoyment from watching the actual videos anymore for these kinds of runs. What is enjoyable, however, is reading the technical explanations for how things like this are achieved. Perhaps the best way to present these runs then would be in the form of an article/paper or explanatory video. I know that's what the submission text is for, but I think for a run like this that's all that really matters.
In any case I think it should definitely be accepted. It's certainly loyal to some basic goals of TASing, e.g. beating a game as fast as possible, and it's a great technical achievement that deserves to be showcased. I just don't really care about the gameplay video and think, as a viewer, the value is more (all) in the explanation of how it works.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
Here's a problem I saw recently. Not sure if it was posted before.
A plane has 100 seats, numbered from 1 to 100. The 100 passengers board the plane in numerical order, i.e. the passenger whose seat is number 1 boards first, then the passenger whose seat is number 2 boards the plane and so on. The first passenger chooses a seat at random and sits there. For all the remaining passengers, if their seat is not taken, they take their own seat, otherwise they choose a seat at random from the remaining vacant seats. What is the probability that the final passenger sits in his own seat?
('at random' here means such that each choice of seat is equally likely)
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
Indeed they are related. Here's one way to see it. Consider the point lying on the unit circle that makes an angle -B with the positive x axis (measured anticlockwise). Its coordinates will be (cos(-B), sin(-B)) = (cosB, -sinB). If you now rotate this point anticlockwise by A, it will move to a point that makes an angle A-B with the positive x axis, and the y coordinate of this final point should be sin(A-B) (by the definition of sin). This should be equal to the newY given by your formula, where the old point is (cosB, -sinB), so newY = cosB*sinA + (-sinB)*cosA, which is the same as sin(A-B).
I suppose the main point is that a 2D rotation by A-B is the same as the composition of two rotations, one by A and one by -B. You can look at sin(A+B) similarly and even the formulas for cosine by considering the x components instead.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
Warp wrote:
What is the result of the infinite sum:
3/4 + 3/16 + 3/64 + 3/256 + 3/1024 + ...
Does the following infinite sum converge or diverge?
1/10 + 1/20 + 1/30 + 1/40 + 1/50 + 1/60 + ...
The first is a geometric series with a = 3/4 and r = 1/4
The sum is a/(1-r) = 3/4 / (1 - 1/4) = 1
The second can be written as 1/10 ( 1 + 1/2 + 1/3 + 1/4 + ... )
The series in the brackets is the harmonic series, which is famously divergent.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
An easy one that I can actually do =)
Call the weights a,b,c,d,x,y,z. The information is just a system of linear equations in these variables. Since there is one more variable than equations (7 vs 6), at least one variable must be free to vary (in fact only one, since the equations are independent). So you can solve for everything in terms of a, e.g. b = 2a, c = 2b = 4a etc.
Putting a=1 at the end you get a=1, b=2, c=4, d=7, x=3, y=5, z=6.
The sum of these values is 1+2+3+4+5+6+7 = 28, so each side of the scale needs to sum to 14. There are several ways of doing this, e.g. 7+6+1 = 2+3+4+5, which corresponds to weighing A D Z against B C X Y.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
It's probably too late now, but this looks like a simple exercise using the chain rule. If u = 1/r then u' = -1/r^2 * r'. You can then use u' = du/dtheta * theta' and the 2nd equation to write theta' in terms of L and r. Finding r'' should be pretty similar and part b should follow from just substituting what you have into the original equation.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
I don't know much about null egg, but if you say you followed the guides exactly, one can only guess where you went wrong. Can you make a video of a failed attempt? Also your best bet for getting help is to visit the #yoshi channel on the speedrunslive IRC. I doubt many of them frequent this forum.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
I went ahead and tried a counting argument. I find the number of up-pointing triangles N_up and down-pointing triangles N_down separately. Let the big triangle have side length n.
N_up:
Let's count the number of triangles with size s. Clearly 1 <= s <= n. Suppose I am on row j of the big triangle where j = 1 at the bottom. For fixed s I can only increase j until the remaining height left above me is equal to s, i.e. until s > n - j + 1, so j_max = n - s + 1. On row j there are n - (j-1) - s + 1 = n - j - s + 2 triangles of size s, so N_up = sum from s=1 to s=n of [sum from j=1 to j=j_max of (n-j-s+2)] = 1/6 * n(n+1)(n+2)
N_down:
Here I flipped the picture upside down and labelled the 'tip', which is now at the bottom, as row 0, the base of that small 'tip triangle' as row 1 etc. What's the largest size s I can have? Well when I am on row s I could at best have a triangle of size s, and the room above me is n-s, so I must stop when s > n-s, or s > n/2. So s_max = (n-1)/2 for n odd and n/2 for n even.
I only start counting triangles of size s from row s onward, so I label my rows as s+j where 0 <= j <= j_max. Again I stop when the room above me is less than my triangle size, i.e.
n - (s+j) < s, giving j_max = n - 2s. Clearly on row s+j there are j+1 triangles. Hence N_down = sum from s=1 to s=s_max of [ sum from j=0 to j=j_max of (j+1) ] = 1/24 * (2n^3 + 3n^2 - 2n - 3) for n odd and 1/24 * (2n^3 + 3n^2 -2n) for n even.
Finally N = N_up + N_down = 1/8 * (2n^3 + 5n^2 + 2n -1) for n odd and 1/8 ( 2n^3 + 5n^2 + 2n) for n even, in agreement with the above.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
I think the difference comes from the fact that the host revealing a goat is no longer a necessity, so when a goat IS revealed that gives us extra information about the possibilities of the game, changing the probabilities. It's clear that if the host revealed the car then we would instantly know we had lost, but we didn't know that before he had opened a door. In the original game, no information is conveyed like this because a goat is always revealed.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
Optimisation aside, I think this game has a lot more to offer and, given how short this movie is, I think it'd be better to have a comprehensive movie for the game that explores all the different modes. Therefore, I'll vote no for this, irrespective of how optimal it actually is (or isn't).
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
I don't see 'ending input early at the cost of finishing the game later' as anything more than a strange type of speed/entertainment trade-off (look ma', no hands!) and I think they should be treated as such. However, to use them to claim that a run is faster seems very silly to me.
Ideally, I would present game-specific times that reach some sensible and consistent end-point (e.g. final boss hit/explosion), agreed upon by people who run the game. The input file times are usually pretty close to that anyway, but when the difference is big I don't take the times on the site seriously.
Anyway, I know that won't happen and I don't mind, but as far as improving runs goes I would accept a longer input file if the game was finished quicker.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
boct1584 wrote:
The glitch is awesome, but seeing every level completed with that glitch would get old pretty fast. Were such a run submitted, I would probably vote for it to be Vaulted.
There's a fair bit of depth to optimising that run, as you must do various things at the start of the levels to avoid losing the sprite or getting trapped in the level, but I doubt anybody apart from the runners would really appreciate that. At the very least there is also some variation in the craziness that happens during each level, but I agree that it's probably more of a novelty run.
As the gameplay is significantly different, I think it's fine to keep the old any% category anyway (current non-glitched any% TAS) by just banning use of the null sprite glitch. That run also has many improvements and some new surprises for those who don't follow the YI scene.
Experienced Forum User, Published Author, Active player
(497)
Joined: 11/19/2007
Posts: 128
Very nice run. It was surprisingly entertaining throughout and some of the solutions really were quite ingenious.
Thank you for making it, and have another yes vote!
