Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Bobo the King wrote:
This bugs me. Hilbert's third problem was motivated by failed attempts by Gauss to produce a cut-and-glue formula for the volume of a pyramid and I seem to have done essentially that. It was later shown, using mathematics beyond my pay grade (Dehn invariants), that such a solution does not in general exist. Furthermore, once we have the volume of one pyramid-like solid, we can apply uniform scaling and/or Cavalieri's principle to show that the volume of any pyramid-like solid must also be 1/3 * base * height. I've proved this formula (Maybe? I think?) without using a limiting process or calculus, which Wikipedia seems to indicate is strictly necessary.
Well, Hilbert's third problem concerns whether, given any two polyhedra of equal volume, there is a general method to cut the first one into a finite number of pieces and rearrange into the second, and the answer was proven to be no. That you have found a cut-and-glue method for specific polyhedra does not change this answer.
Also, the usage of Cavalieri's principle is outside the scope of this problem; it is not considered a cut-and-glue method in the context of Hilbert's third problem.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
r57shell wrote:
Suppose you have a pizza. And there are two possibilities: you'll have party of N people or party of M people. (including yourself).
In what minimum number of slices (pieces) you need to cut this pizza, such that in both possibilities each member will able to get same amount of pizza without making additional cuts, and there will be no remaining slices (pieces) in both cases. Slices can be any size.
I don't have a complete answer.
It is easy to show that M+N-gcd(M,N) pieces is enough. There is a cutting of the pizza into M equal slices, and a cutting of the pizza into N equal slices; overlay them together so at least one of the cuts from one of them coincides with at least one of the cuts from the other. Then there is an overlap of gcd(M,N) cuts, so there are a total of M+N-gcd(M,N) pieces.
The hard part is showing that you can't use less than M+N-gcd(M,N) pieces. I don't have an answer for that.
OmnipotentEntity wrote:
There is a box that magically produces mangos. You may check it at most once a day, and every day it has a 5% chance of spawning a mango, unless there is already a mango in the box. However, if you open the box to check, regardless of whether or not you find a mango inside, you cannot open the box for 3 days, and the box will not spawn a mango for those 3 days.
How often should you check the box to maximize your expected rate of mango acquisition?
First, let n be the number of days (inclusive) from when the box starts producing mangos until you open it. Then the expected rate of mango acquisition is (1-(0.95)n)/(n+3).
Next, I prove the following statements (n is a positive integer):
(0.95)n < 20/(n+23) for n≥10
(0.95)n > 20/(n+23) for 1≤n≤9
For the first, (0.95)10 < 20/(10+23). Now assume (0.95)k < 20/(k+23). Then (0.95)k+1 = (19/20)(0.95)k < (19/20) 20/(k+23) = 19/(k+23) < 20/(k+24) = 20/((k+1)+23), thus proving the first by induction.
For the second, (0.95)9 > 20/(9+23). Now assume (0.95)k > 20/(k+23). Then (0.95)k-1 = (20/19)(0.95)k > (21/20) 20/(k+23) = 21/(k+23) > 20/(k+22) = 20/((k-1)+22), thus proving the second by reverse induction.
Why do I look at these two statements? Because:
(1-(0.95)n+1)/(n+4) < (1-(0.95)n)/(n+3) is equivalent to (0.95)n < 20/(n+23), and
(1-(0.95)n+1)/(n+4) > (1-(0.95)n)/(n+3) is equivalent to (0.95)n > 20/(n+23).
These can be verified by expanding the left inequality and solving for (0.95)n.
This means that (1-(0.95)n)/(n+3) is decreasing on [10,∞) and increasing on [1,10].
So the max of (1-(0.95)n)/(n+3) over all positive integers n is n=10. Putting in the value gives:
(1-(0.95)10)/(10+3) = 0.0308663...
So n=10 gives the highest expected rate at (1-(0.95)10)/(10+3) = 0.0308663... mangos per day.
The route we are forced to go goes:
jump < pipe < ruby < ruby < bounce < dash < squish < sticky < ruby < ruby < ruby < ruby < ruby
There really isn't flexibility when it comes to routing for this game.
This submission text wrote:
As I said, the route has been completely changed and this is it in its current form:
springy < bouncy < slurpy < squishy < spinny < ruby < ruby < sticky < ruby < ruby < ruby < ruby < ruby < ruby
Things really do change, I guess.
I found it amusing that, because of glitches, the blob resembles Sonic the Hedgehog at times (both in speed and in glitchiness).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Something I was curious about. Does this TAS stop as soon as the trip count first reaches 99?
It may be better to go one further to show that the trip count no longer increments after 99, similar to how [4769] Uzebox 2048 "maximum score" by p0008874 in 02:17.35 defines max score by overflowing to prove that the max score was reached, as opposed to stopping literally at the maximum possible number (65532).
Fun fact: The trip count no longer incrementing after 99 is an intentional troll move by Penn & Teller. I did not realize at the time I first saw the #2211: alden's SegaCD Desert Bus in 41:17:15:05.68 submission, but I realized immediately when I read something in an article similar to the following (if anyone has a more reliable source, feel free to post it):
https://www.newyorker.com/tech/annals-of-technology/desert-bus-the-very-worst-video-game-ever-created wrote:
Penn, Teller, and the game’s publisher, Absolute Entertainment, planned a lavish prize for any player that scored a hundred points, a feat that would require eight hundred continuous hours of play: a real-life trip from Tucson to Las Vegas on a desert bus carrying showgirls and a live band.
Read the first twenty words of this quote and you will immediately see why.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I didn't even realize this was the NES version until I saw the screenshot for the publication. (This is despite the site clearly stating the system name at least a hundred times, each time not having the "S" in front of "NES").
I guess this is proof of how revolutionary [1248] SNES Family Feud "playaround" by Heisanevilgenius in 06:46.71 was. Definitely worth watching again.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
In case you need to do any testing on the hardest difficulty (the CPU take a really long time sometimes), you can use my form-based Lua script to help with this. I used it to make a (not very useful) Stockfish vs Battle Chess TAS (in my userfiles somewhere). Note that Stockfish is non-deterministic so other attempts at using Stockfish to beat Battle Chess may differ.
Also QuickNES is reasonably accurate for this game. The CPU thinking time is virtually the same and the only difference is NesHawk is slightly faster on some screen transitions (at the beginning of the game, and also when using capture animations). So you can optimize it on QuickNES and then make the final movie on NesHawk. Although probably everyone uses QuickNES anyway.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
In the past, I would have just been like "just set up the 10x10 matrix and solve it". Which is what you mentioned in your spoiler already.
However, earlier this year I was looking up information about expected length of random walks, and learned something that was intuitively simple, yet profound:
A random walk can be modelled as a recurrence relation.
Think about it. The rule for moving in a random walk is the same for a whole range of values, so it is just like a recurrence relation. The initial values would be the end states of the random walk (in this case, having 0 coins = 0 and 9 or 10 coins = 1 ), which would be used to determine the coefficients in the solution.
So for this example, letting xk be the probability of winning (at least 9 coins) given you have k coins, the recurrence relation is:
xk+1 = (5/9)xk + (1/3)xk+2 + (1/9)xk+3 for 0≤k≤7, x0=0, x9=x10=1
Or in other words:
xk+3 + 3xk+2 - 9xk+1 + 5xk = 0 for 0≤k≤7, x0=0, x9=x10=1
The characteristic equation is r3+3r2-9r+5, which factors as (r+5)(r-1)2 (it helps to see that, not only is r=1 a root of any recurrence based on a random walk, but r=1 has at least multiplicity 2 if it is a martingale). So the solution to this recurrence is of the form:
xk = A+Bk+C(-5)k for 0≤k≤10
Using x0=0, we get A=-C. With x9=x10=1 and A=-C, we get 9B-1953126C=1 and 10B+9765624C=1. Subtract the two resulting equations to get B=-11718750C and so C=-1/107421876. So A=1/107621876 and B=11718750/107421876 and so:
xk = (1/107421876)( 1 + 11718750k - (-5)k ) for 0≤k≤10
and with k=5, this gives x5 = 1627691/2983941 = 0.545483...
This model is definitely easier to extrapolate to large n (as opposed to dealing with (n+1)x(n+1) matrices!)
Regarding martingales and the approximation x/y where x is the number of starting coins and y the number of goal coins, you're probably thinking of the simplest martingale: losing or gaining 1 coin with equal probability (1/2) at each step. In that case, x/y isn't just an approximation; it's the actual probability! (Because xk = (1/2)xk-1 + (1/2)xk+1, every three consecutive terms, and thus the whole sequence, has to be in arithmetic progression.) The model given in the problem probably isn't too far off from this model then.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I'm currently exploring how long it would take to beat the CPU on hardest difficulty without using glitches (i.e. legitimately). I figured that at some point we're going to have to stop being cheaters.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I actually forgot I ever played this hack (it was like 15 years ago) until I watched this TAS.
It was actually kind of cool that there was some custom soundtracks (even if most/all of them were from other Mega Man games).
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
ShesChardcore wrote:
I've refrained from working on some TASes (not this game specifically, SpaceColonizer did a great job and I very much would not have haha) due to the rules being the rules.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Wait, the book does not even define exponentiation for integers or prove anything related to integer exponents, and yet you are expected to prove b^r b^s = b^(r+s) for rational r and s?
I was about to try answering, but considering how much the book does not allow to you assume, it's clear I know nothing about this subject, so I'm not going to bother.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I was just thinking now if there are any particular set of goals that would make a Battle Chess TAS more interesting.
If, for example, I just made a TAS forcing CPU moves all the time, would that be more interesting? At least it would take like 1/10 the time of this TAS.
Also, is there any reasonable interpretation of "100%" that would make sense with this game?
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
In case viewers have no clue how (or rather, why) the illegal move works, I updated the submission text with a spoiler description. It includes an explanation of how this works as well as a table of moves and comments.
I see adelikat has not commented yet, but I suppose he already knew where I was going with this submission, at least by move 8. After all, adelikat was the first one to find the exploit which the illegal move is based on, and even made an April Fools submission out there which abuses this.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
adelikat wrote:
Your words worry me that you are upset, but I am not sure. I didn't mention authorship, but now that I have redone the movie, I see it is the same moves and take backs. I would not feel comfortable with this movie, as is, being a sole authorship of mine.
I'm fine with whatever you decide. Also I assume you are making the TAS on your own, so it is yours to claim.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
adelikat wrote:
FractalFusion wrote:
IIRC, this TAS is easily beaten by ~1m30s, somewhere on this forum.
Ah, this: https://tasvideos.org/Forum/Posts/108220
Very clever, looks like 2 take backs + 2 take backs avoids the computer thinking for one more move, I'll make an updated version
For a moment, I thought no one actually wanted to take the credit that I was practically giving away for free.
Cool, it's yours.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
I can't remember a lot of things from a game I did a TAS of 12 years ago. From what I can remember though:
* I aimed to get Fever Time as soon as possible, which meant priority to shooting the UFO and clearing the Bingo panel as soon as possible.
* Red-red and green-red Bingo panels give the fastest bonus round clears if you use a laser (blue).
* When not in Fever mode and having bomb (red), it is better to alternate bomb and normal fire as much as possible.
This game takes quite a bit of effort to TAS, if I remember correctly.
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
As a side note, I was introduced to that type of kite problem in a calculus course where it was expected to be solved in the same way as Dacicus did it (which I also did as well). After doing it that way, I found a simpler method very similar to how p4wn3r did it: Using trigonometry gives the angle between the sides of length 4 and 7 to be 90 degrees, and the rest of the problem easily follows from this.
(I also intentionally set up the problem to conceal this method. It's easier to see if you draw the vertical diagonal splitting the kite into two congruent triangles.)
p4wn3r wrote:
Also, the quadrilateral is cyclic, so we can apply Ptolemy's theorem: x*sqrt(65)=4*7+7*4 => x=56/sqrt(65)
Or just: The area of the kite is half the product of the diagonals: (1/2)*x*sqrt(65)=28 ------> x=56/sqrt(65).
(Yes, I know there are a dozen different ways to work out x.)
Editor, Experienced Forum User, Published Author, Skilled player
(1941)
Joined: 6/15/2005
Posts: 3247
Here's a calculus problem:
A kite is to be constructed with side lengths 4,4,7,7 as shown below (not to scale):
We wish to maximize the area of the kite we construct. What is the value of x (the length of the dotted line in the diagram above) that gives the maximum area, and what is the maximum area?
We wish to maximize the area of the kite we construct. What is the value of x (the length of the dotted line in the diagram above) that gives the maximum area, and what is the maximum area?