Since Warp still doesn't seem to understand why I'm actually angry at him (and wouldn't accept any other reason except that I'm an asshole), I've taken it to PM. Apologies to all, including Warp, for not doing so sooner.
I still maintain that I consider the attitude Warp displayed towards this thread over last few pages unacceptable; even though it may not have been the attitude he intended. And although it has always been an incredibly dick move to post the following link in an internet argument, I'll do so anyway.
http://www.catb.org/esr/faqs/smart-questions.html
Though if you disagree with me, feel free to tell me via PM. With that, back to math.
Scepheo wrote:
Basically, my proof consists of two parts:
1) Proof that we can also make the numbers up to f(n) for any given f(k) removed.
2) Proof that we could also remove f(n) instead and still make the sums.
Even after rereading your proof, I must admit that I don't understand the invariant you're claiming and the inductive step you're doing. To replace F(n), you need to get a sum for b-F(n) that doesn't contain F(n-1) nor F(n-2), but your assumption only allows you to remove one.
In other words:
Scepheo wrote:
I find all you people's proofs hard to follow, honestly.
right back at you. ;)
I've been meaning to post my proof in full, without the handwaving, but it's saved on the other computer, which is offline for today.
In particular, with 32 (0x20) super missiles we can use the power bomb count to jump anywhere between 0x0000 and 0x3200 in steps of 0x100. Lots of player-manipulable variables can be found in that range.
oh man. If i was an actual dog, you'd see tail wagging.
amaurea wrote:
By the way, the game state is stored in 0x998, and writing 0x26 to this address will play the ending.
You mean, on the next frame, the game loop checks the value there, and jumps to the ending routine if it contains 0x26? If so, would it be possible to jump to the ending routine directly (possibly giving us a different attack vector), or is the ending still part of the regular game loop?
Yes, I have proved these sequences you are complaining about are never generated by the greedy algorithm: F(2n-1) + F(2n - 3) + ... + F(1) = F(2n), which can be proved recursively. I did actually note this exception.
ah, you were talking about the longest subsequence of that form, not just about full sequences. Sorry I missed that. But to be fair, your description was a bit terse. ;)
Here's your star, then!
@Scepheo: so your proof says that you can remove any number F(n) after you've already removed a number F(k) with k<n? We know that's not possible, so there must be a flaw in there.
I think this is the part where your proof goes poof:
A) we will never have used both of them, as F(n - 1) + F(n - 2) = F(n) and b - F(n) < F(n)
B) we can safely remove the other one, as per our initial assumption.
A) Yes, after removing F(k), k < n, you will still have a sum, and that sum has only used either of F(n-1) or F(n-2)
B) ...but now you're retroactively changing k to either n-1 or n-2! By doing so, you get a different sum for b, invalidating your assumption that the other number wasn't used!
If you remove F(n-1), your sum may contain F(n-2), and if you remove F(n-2), your sum may contain F(n-1). At no point are both used (so A still stands), but there's no proof that you can remove both at the same time and still represent any b you need.
Warp wrote:
You might not have intended it like that, but you came out sounding like an a-hole.
I'm glad you noticed.
You know what else makes one sound like an a-hole? Asking a question, then ignoring the answers that others have spent time to provide for you. Above you were two proofs, one proving that no more than 30.6% of all fibonacci numbers can be removed; another proving that at most one can be removed. Yet you posit an argument suggesting to remove 1/3 of all numbers. Why? I doubt it'd lead to valuable insight. I also doubt it'd help you understand the issue. I doubt that it can, in any way, be considered a good contribution to the thread.
Now I know that these things aren't trivial, for none in this thread. Mistakes are made, misunderstandings happen, details get lost, sometimes things need to be repeated to be understood, and some people ask questions on a completely different difficulty scale than others. That's fine.
What's not fine is that you keep asking questions without trying to answer them on your own. Answering one of your questions can take a good hour of browsing wikipedia for known results, reviewing the previous posts in this thread, dabbling on a piece of paper, reformulating the problem, scribbling some more etc.
I think it's incredibly rude to ask others to invest that amount of time on your problem unless you've spent a good amount of time trying to figure it out yourself. Even more rude to ask more questions before you've made a good effort trying to understand the answers that were already given to you.
And not only is it more considerate towards your fellow forum members, it's also easier to learn and understand the things that seem to interest you by trying to solve these things for yourself. Knowing how many numbers you can remove from the fibonacci sequence is a useless trivia question; knowing how to prove it is a good skill.
And don't tell me it's too hard. This is not a problem about lattice configurations in 17-dimensional hilbert space while approaching relativistic speeds. All you need is wikipedia, highschool math and the will to sit down and work on it. I know you're smarter than this, you were just being lazy.
So go ahead, try the next thing you're curious about for yourself. If you get interesting results, share them. If you think the proof is interesting, pose it as a riddle to the thread, then share your solution later. If you get stuck, post how far you got and ask for help.
But please don't just post a random idea you had five seconds ago and expect everyone else to do the work for you.
[citation needed]
We've proven that such a sequence exists, and we've given an algorithm to find one such sequence, but we've never proven that such a sequence is unique. In fact, I have a counter-example. ;)
But you may start with the sequence generated by the greedy algorithm if you wish to rely on some of its properties.
thatguy wrote:
n can never reach one because we have already prohibited precisely the sums that would not terminate before they reached n=1, two paragraphs up.
No, you haven't, and I do believe that you need to handle this case. Consider the sum F(1) + F(3) + F(5) + F(100) - and the F(n) you wish to remove is F(5). Can you prove that such a sequence is never generated by the greedy algorithm? Or can you find another way to represent the number after removing F(5)?
Are there any other special cases you may have forgotten?
thatguy wrote:
Can I have a gold star please?
not yet :D The general idea seems to work, just add rigor until a proof appears.
Btw, I tackled the problem the other way around (since I didn't yet know the solution): I removed F(n) (with n > 2) and then tried to generate sequences for all natural numbers.
Numbers 1 to F(n)-1 are easy, use the greedy algorithm, no numbers are missing
F(n) is easy, F(n-2) + F(n-1)
F(n+1) is easy
Anything above F(n+1) is easy if anything below is possible; use the greedy algorithm until you pass F(n+1), then use the modified sequence from this proof for the remainder.
The interval F(n)+1 to F(n+1)-1 is the tricky part. By solving it I did not only notice that any one number can be removed, but also that you cannot remove two.
Fun fact: my variant doesn't rely on the non-consecutive property at all; the existence of a sequence is enough.
That's very sweet of you. Posting a counter-argument two posts below a proof that proves your argument false. What kind of answer do you expect to that?
As I said, I have proven the statement you quoted, and the last few posts in this thread contain all the information required to prove it yourself. Why don't you try working through the problem yourself? It's amazingly more enlightning than throwing random guesswork at a thread and waiting for someone else to provide answers.
And no, there's no hidden condition in my statements. You can remove exactly one fibonacci number from the sequence, and the remaining elements can still be combined to sum up to any natural number, where any fibonacci number is used at most once (though F(1) and F(2) can both be used, allowing you to use the number 1 twice). Remove two, and you can't.
That's the upper bound, correct.
Now you need to prove that any single number can be removed. Though that part of the proof is a bit tedious and not nearly as satisfying.
I can give you a better upper limit: 1. I can also give you a lower limit: 1. You can remove any fibonacci number you like, but only one. Since Warp already removed F(1) = 1, all the other numbers are required.
Relevant property: F(1) + ... + F(n) = F(n+2) - 1
I have a proof of both claims, but with the equation above it should be easy to try for yourself.
Wouldn't that be the set of all natural numbers? Or did I misunderstand something?
I think when he said "unique sums" he didn't just mean "sums of distinct integers", but also "there's only one possible sum per integer". If 5 can be represented as 1+4 and 2+3, then the sums are not unique.
So given the constraint that your sequence does not contain any numbers that aren't required, 2^(n-1) is the only sequence possible.
* Since negative numbers aren't allowed, you need 1 = 2^0 to get a sum for 1
* if your sequence contains all numbers 2^0 .. 2^n, then all numbers 1 .. 2^(n-1)-1 already have a sum. Thus, the smallest value you can add without creating multiple sums is 2^(n+1)
Thus, by induction, the densest sequence possible is 2^(n-1).
Got 1-7, 11 and 12
I'm a web developer. Is it a bad sign that I consider level 10 to be safe?
I mean, I cannot easily find a solution for 8 and 9 either, but just looking at it I think "bad idea". 10 looks fine to me.
Scepheo wrote:
Nope, still not necessary. Though now I'm curious as to your solution for level 7.
I solved both without the unnecessary things, probably the same way you did. The second just requires a javascript-feature that no mortal should ever have to know.
Not sure how you define "sparse" in this context, but I don't think you'll get better than the binary representation, i.e. the sum of distinct numbers of the sequence 2^n.
But not Bloodlines, the one that actually makes [kinda] bad references to Germany?
It's not censorship, it's copyright. It's not blocked by our government, it's blocked by youtube.
Unfortunately, this SME-music-content is not available in Germany because GEMA has not granted the respective music publishing rights.
Sorry about that.
There is no "fair use" clause in germany, so any unlicensed display of copyrighted works is by definition a copyright violation. Yes, this includes videos of games, since they always contain copyrighted artwork and music. Strictly speaking, we'd need the copyright holder's permission. The good news is that nobody cares, but it's still a legal minefield.
What happened here is the GEMA. The GEMA is a central authority for licensing copyrighted works. The idea is that, for example, a radio station does not have to hunt down contracts with every single artist they want to play music from. They just make a contract with GEMA, play their songs, and at the end of the day, they give a list of songs they played and a bunch of money to the GEMA and they distribute it to the artists. A good thing, in theory.
Now the GEMA sued google for breach of copyright and they demanded payments. Other licensing organisations in other countries did the same, they made a contract with google, and google paid up. Problem is, the GEMA is demanding an order of magnitude higher licensing fees than the others did; effectively they want more money than youtube makes. So google said "nope, screw you", got a copy of the GEMAs music library, fed it into their ContentID system, and is now blocking every video with music that has been released on CD in germany. Which includes some video game soundtracks. It's often ok, since the music is overlaid by sound fx and doesn't get recognized, but (for example) "I am the wind" during the credits is a good way to get blocked.
</offtopic>
+2 internet cookies for total!
My SNES asm is a bit rusty (as in "I dabbled with m68000 assembler in my childhood and thus know the difference between a micro chip and a potato chip"), but along with your comments, I think I understand most of it.
So it effectively jumps into a routine that looks similar to a memcopy which usually copies 10 bytes.
Bytes are read from (address at $00) + Y + 2 and written to $7EC1C0 + X + 2, X and Y increase by 2 each loop until Y >= 20. Breakage occurs when Y is negative.
Since A is 8 bit, it will copy 8 bits, the skip 8 bits, then repeat. Is that right?
Have you identified where the routine is usually used, i.e. where that code came from? It's probably irrelevant, I'm just curious.
Can you please copy the ASM for the other invalid beam combinations, too? Maybe something interesting turns up.
The whole code for beam firing should be interesting, too, because that's the part where the values for X, Y and $00 can come from. Backtracing the call stack until the most recent manipulation of those values would be useful.
X and Y are signed 16bit-registers, right? So at most one could write 32768+20 Bytes (Y range), and the addresses that could be written to are between $7EC1C0 - 0x8000 to and $7EC1C0 + 0x7FFF.
Now does an adressing overflow overflow into the next bank or will it keep the bank, but start at the bottom again?
In the first case, the routine could write to any address between $7E41C0 and $7F41BF, in the second case it'd be $7E41C0 to $7EFFFF and $7E0000 to $7E41BF, so essentially the whole 7E bank, which is most of the (non-expanded) RAM. Great.
Let's look at http://drewseph.zophar.net/Kejardon/RAMMap.txt :
Starting at 7E:CD52 things get interesting. There's a lot of gamestate, items, visited rooms etc, which may explain why the reset glitch does what it does - with a suitable start location for the copy, all the info gets zero'ed out, or at least badly mangled.
total wrote:
Regarding arbitraty code execution, what Tub said is correct since what happens is a invalid jump to ROM, so there's no way we can manipulate what code runs.
arbitrary code execution is a two-step process:
a) write the code you want to execute somewhere in memory. This usually starts with a minimal payload which then reads more code from gamepad input.
b) find a way to jump to that code
It could be used to do a), depending on the available values in $00. If $00 ever points at a suitable hardware register, preferably the controller data, that might be useful.
Should $00 always point to a RAM location (which it probably does), it's less useful, because it's just a copy. But with sufficient control over $00, X and Y we might be able to copy single instructions into just the right location.
It's not yet useful for b) either. Ideally, we could use a memcopy to write the pointer into a location that contains an address (like the $0C68++ in the beam code), but if (as you say) X = 0 is given, that seems unlikely.
Link I shouldn't forget: http://wiki.superfamicom.org/snes/show/65816+Reference
Does one really need to worry so much about emulator accuracy?
Yes. A lag frame here or there isn't a problem, but the murder beam and its effects are more volatile than that. If parts of the glitch aren't possible on the console or give different results, then that's a problem.
amaurea wrote:
Edit: Also, this glitch seems like a likely way to execute arbitrary code in super metroid.
I cannot find the writeup, but IIRC it was kejardon (who else?) who dissected the glitch, and from what I remember, arbitrary code execution was.. unlikely. The beam goes wild, overwrites memory locations it shouldn't and everything, but IIRC there was no real way to direct the values that get written. For arbitrary code execution, you'd need to write your initial payload somewhere (often into an easily manipulateable inventory). Writing the required values by chance AND finding a way to randomly jump there is unlikely.
tl;dr: the glitched beams are still poorly understood. More research would be helpful.
I pushed a little further in this and am now stuck on level 11/12 (neither of which I have any clue on). Anyone else chugging at this?
11: there is a defense against level 2's solution. Use level 2's solution anyway. The trick is to get it past the defense.
12: not a clue, though my observations above about level 7 may apply.
It's the simplest form of a greedy algorithm. You can generate a sequence of unique fibonacci numbers for your number N by picking the largest number F(n) <= N, then repeating for the remainder N-F(n), until nothing is left.
So for 100, you'd pick 89, remainder 11. Pick 8, remainder 3. Pick 3, nothing remains. Your unique sequence is 89, 8, 3.
To prove that this algorithm works, he needs to prove three things:
a) for every N > 0, there's always an F(n) <= N to pick. Since F(1) = 1, this is ok.
b) After you've subtracted your F(n) from N, the largest fibonacci number smaller than the remainder N-F(n) is not F(n) again, but a smaller fibonacci number. Otherwise they wouldn't be unique. He's proven that with all those intimidating subscripts; take a closer look.
c) The algorithm terminates. In every step, you subtract a positive number from your N, thus N will reach 0 eventually.
Not only has he proven that a sequence exists for every natural number N, he's given you an algorithm to find such a sequence. Constructive proofs ftw.
aaaand got ninja'd. ^^
rhebus wrote:
Interestingly, this algorithm will either only use even-indexed or odd-indexed fibonacci numbers.
As you noticed, that's not true.
Counterexample: 10. Your algorithm yields 8+2 with indexes 6, 3.
Other valid sequences for 10 are 8+1+1 (index 6,2,1) or 5+3+2 (index 5,4,3) or 5+3+1+1 (index 5,4,2,1) - neither of these sequences' indexes have the same parity.
rhebus wrote:
What is the minimum number of weights you need to measure items of every integer weight from 1 to 40?
We'll need a weight of 1 (let's call it W1) to measure 1.
1 = W1
We can measure 2, 3 and 4 if we add W3.
2 + W1 = W3
3 = W3
4 = W3 + W1
The next one we'll need seems to be W9.
5 + W3 + W1 = W9
6 + W3 = W9
7 + W3 = W9 + W1
8 +W1 = W9
9 = W9
10 = W9 + W1
11 + W1 = W9 + W3
12 = W9 + W3
13 = W9 + W3 + W1
Last one is W27, I think you can figure out the way. 4 weights.
It means you're using the wrong formula.
The definition of density is simple:
density = mass / volume
If you have any finite amount of mass and compress it into a space of zero volume,
lim (volume -> +0) mass / volume = +inf
says that your density is now infinite.
Applying the GR formulas to black holes suggest that at the very center, you get infinite density, thus a singularity.
But it is well known that the GR formulas don't apply at very small scales, and if a volume of zero doesn't qualify as "small scale" then I don't know what does.
It is not yet fully understood how QM applys in this area (mainly because there's no QM theory of gravity yet, and gravity is kind of important in black holes), but IIRC I read some articles that used QM to say: "We don't know what it looks like, but we can prove that it's not what GR says it is."
Very interesting game, thanks for sharing!
I've broken them up to level 6. I haven't beaten 7 yet, but I'll note my observations.
It's interesting to note that the function name allows []' as characters, but neither . nor (). So if you want to call document.getElementById you could write it as document['getElementById'], but I haven't found a use for that notion yet. Several... interesting applications that could really screw up your web site, but nothing to call alert(1).
Another interesting observation: it's possible to formulate an expression that yields 1 within the function name with the allowed characters. Not sure how to combine that though, neither binding nor closures seems to work.
Aren't photons the force-carrying particles of the electromagnetic force anyway, and thus a force themselves?
I've never understood hawkins when he talked about "virtual" photons (that are supposed to carry the force) and "real" photons (that somehow don't?).
Also, these proofs rely on the assumption that temperature, height and wind direction and continuous. At least for height I'd just point you to the nearest cliff.
For winds, the center of a small vortex is technically windstill, but standing in there you'd claim otherwise. The hairy-ball theorem also wouldn't count updraft as wind - I would.
Nice death exit glitch, but otherwise it's a pretty uneventful game. Barely any enemies are met, the movement isn't as varied as, say, super metroid, and the final boss fight looks like standing there with autofire.
I recognize the nostalgia for those who played it back in the day, but the interesting-to-uninteresting-ratio is kinda zelda'ish.
meh.
@Scepheo: so your proof says that you can remove any number F(n) after you've already removed a number F(k) with k<n? We know that's not possible, so there must be a flaw in there.
I think this is the part where your proof goes poof:
