I'm guessing it was to make up for how hard last week's challenge was. I mean, even the case N=2 was hard enough, nobody proved it rigorously (the assumption is that one of two layouts would yield the maximum) and N>2 was a complete load of nothing. Also, I don't think a lot of people like solving quartic equations.
Whereas this week's challenge can be solved doing nothing more than writing down a table.
To explain what I mean, I'll reword the problem:
Players A and B play a series of matches against each other, each match one wins and the other loses. They play until one of them wins four matches (a.k.a. "best-of-seven"); that player wins the series. Each match, you may bet X amount of money on A winning; you gain X if A wins and you lose X if B wins. Is there a series of bets that guarantees that, at series end, you end with a gain of 100 if A wins the series and you end with a loss of 100 if B wins the series?
(spoilers below)
Construct a table representing the status of the series (based on # A wins and # B wins). The amounts that you have at the end are:
A 0 1 2 3 4
B
0 100
1 100
2 100
3 100
4 -100 -100 -100 -100
Now each number in the table (other than for 4 wins by either player) is the midpoint of the number directly below and the number directly to the right. Fill in the table from bottom-right to top-left according to this rule. Then the amounts that you must have in each case are:
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Bobo the King wrote:
Suppose we have a membrane in two dimensions that is both homogeneous and isotropic.
Could you explain what this means specifically? Does the cross-section arc length depend on which cross-section you choose?
My impression is of a function in two variables f(x,y) with the property that for some positive a,b, we have f(x+a,y+b)=f(x,y) for all x,y. In other words, periodic in two directions.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Nice, you got the answer pretty quickly!
Yes, the smallest number is 1016949152542372881355932203389830508474576271186440677966. Bobthefloater's explanation works (though the way 'b' and 'a' are defined there means that b=169...796 instead of b=169...7966). I wrote it in a slightly different way.
Any such number N must satisfy 6*10N-N=A*(10n-1), or 59N=A*(10n-1), where A is the last digit of N and is a number from 1 to 9, and n is the number of digits of N. Therefore 59 divides 10n-1. The smallest n for which this works is n=58 (10 is a primitive root mod 59). So N=A*(1058-1)/59=A*169491525423728813559322033898305084745762711864406779661. Since N has to be 58 digits long, the smallest A that gives this is A=6, and that gives N=1016949152542372881355932203389830508474576271186440677966.
There is also a pencil-and-paper explanation as well, which I think BrunoVisnadi and Masterjun recognized. Let N be the number we want to find. The first digit of 6N has to be at least 6 (otherwise N has less digits than 6N) and N starts with 1. This means the second digit of 6N is 1. We have:
61.....
1......
The next digit of N to find is simply the remainder of the previous division by 6, joined to the corresponding digit of 6N (which is always the same as the previous digit of N). For example:
61.....
1......
(1 divide 6 is 0 with remainder 1)
610....
10.....
(10 divide 6 is 1 with remainder 4)
6101...
101....
(41 divide 6 is 6 with remainder 5)
61016..
1016...
and so on. The process terminates when a division has a remainder of 0 and the digit of N is 6 (the same as the first digit of 6N). This gives N=1016949152542372881355932203389830508474576271186440677966. Starting with 7, 8, or 9 as the first digit of 6N will give other numbers with the same number of digits, and they are larger. In fact, they are just cyclic shifts of the above number.
For x2 to x9 the smallest positive integer with this property is:
2: 105263157894736842
3: 1034482758620689655172413793
4: 102564
5: 142857
6: 1016949152542372881355932203389830508474576271186440677966
7: 1014492753623188405797
8: 1012658227848
9: 10112359550561797752808988764044943820224719
Other than for x5, the numbers resemble the repeating part of the decimal expansion for 2/19, 3/29, ..., 9/89.
I considered numbers which give strict multiples when their first digit is moved to the end, but that isn't as interesting. Only x3 works and the numbers are 142857, 285714, 142857142857, 285714285714, etc.
Invariel wrote:
FractalFusion and Masterjun, I am always happy to see people having fun with 142857, because it is easily one of my favourite numbers. (Well, more specifically the decimal expansion of 1/7.)
It's one of my favourite numbers too. I was familiar with such decimal expansions since childhood. (e.g. 1/7, 1/17, 1/19, ...)
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Here's a problem I thought about recently.
If you take the last digit of 102564 and put it first, you get 410256, which is 4 times the original number.
Similarly, if you take the last digit of 142857 and put it first, you get 714285, which is 5 times the original number.
Problem: What is the smallest positive integer such that if you take its last digit and put it first, you get a number which is 6 times the original? (As usual, numbers don't start with leading zeros.)
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Flip wrote:
There's a town where 70% of the men are married to 90% of the women. What fraction of the total town is married?
I had a suspicion that there was some background context related to this question, though upon searching the Web, I certainly didn't expect all the news articles regarding it. The fallout was amusing though.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Masterjun wrote:
No, you guys forgot the Law of sines (or something similar).
Then (after cancelling out the lengths of the sides) you will end up with something like
sin(15°) / sin(25°) = sin(Φ) / sin(80°-Φ)
which looks easy... but isn't.
How to derive it quickly: sin(15°)/BD = sin(30°)/CD, sin(30°)/AD = sin(Φ)/BD, sin(80°-Φ)/CD = sin(25°)/AD. Multiplying all equations gives sin(15°)sin(30°)sin(80°-Φ)/(BD*AD*CD) = sin(30°)sin(Φ)sin(25°)/(CD*BD*AD), and cancelling and rearranging gives the above equation.
You can use the trigonometric form of Ceva's Theorem to get the above equation directly. Now that I think of it, the sine law gives a really fast proof of that theorem. Most other proofs I've seen use the sine area rule, which is a bit more involved.
By the way, we can solve the equation as follows:
sin(15°) / sin(25°) = sin(Φ) / sin(80°-Φ)
sin(25°)sin(Φ) = sin(15°)sin(80°-Φ) = sin(15°)(sin(80°)cos(Φ)-cos(80°)sin(Φ))
(sin(25°)+sin(15°)cos(80°))sin(Φ)=sin(15°)sin(80°)cos(Φ)
tan(Φ)=sin(15°)sin(80°)/(sin(25°)+sin(15°)cos(80°))
and Φ is obviously less than 90° so
Φ=arctan(sin(15°)sin(80°)/(sin(25°)+sin(15°)cos(80°)))
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Bobo the King wrote:
HHS wrote:
For an infinite number of statisticians, one would have to compute , which I don't know how to do.
Wolfram Alpha gives the answer to this integral as 1/sqrt(5). I have no idea how it determined that.
I wouldn't know how to show directly that equals 1/sqrt(5); however, I can explain briefly where 1/sqrt(5) comes from.
Let p0 (you), p1 (person seated one away), p2 (person seated two away), ..., be the probabilities of winning depending on position. Now suppose that the number of people go to infinity. So pn=(1/3)pn+1 + (1/3)pn-1 for all n≥1. Supposing that pn+1=apn, plugging in to the equation above gives pn=(1/(3-a))pn-1. Without going into too much detail, applying f(x)=1/(3-x) to a number over and over will cause it to converge to a solution of x=1/(3-x); this gives x=(3-sqrt(5))/2 (since x has to be less than 1). So p1 approaches ((3-sqrt(5))/2)p0. Plugging this into p0=1/3 + (2/3)p1 gives p0=1/sqrt(5).
Edit:
arflech wrote:
It's a geometric sum, and it's then easy to see that the probability goes to 1/sqrt(5) as N approaches infinity; what looks trickier is that it seems like all of the probabilities are rational for finite values of N, but it looks like a slog to prove it.
Well, if N is finite, the probabilities are obviously all rational since the problem boils down to solving a linear system over the rational numbers. Which is a neat way to prove that the above quantity is rational for all N≥1.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
https://www.youtube.com/watch?a=1&v=ZmPUbuFGHcs&feature=youtu.be&t=1975
Hetfield90 brought this to my attention. It is a faster way of doing Mosquitus, using a glitch that sends Mosquitus into the wall and then automatically kills Zero without having to wait for Mosquitus to get near him. It also glitches out Zero.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
MUGG wrote:
I remember this discipline from various Japanese tv shows that aired here in Germany ages ago... Sports Bakka, Takeshi's Castle, ...
Why does Sports Bakka's original Japanese title and this game both have "Nan-chan no honō no charenja" in its name? I suppose the game stems from the tv show? Who is Nan-chan?
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
BrunoVisnadi wrote:
FractalFusion wrote:
Given a positive integer n, there always exists a power of 2 for which the final n digits do not have 1,2,4,8, so mod 2^m or 5^m arguments don't work.
How do you know that?
It's based on a few facts. If g is a primitive root modulo p^2 where p is an odd prime, then g is a primitive root mod p^n for all n≥2. Since 2 is a primitive root mod 25, then 2 is a primitive root mod 5^m. So for every number b that is not a multiple of 5, there exists a k for which 2^k=b mod 5^m.
Scale this by multiplying by 2^m. So for every number c that is a multiple of 2^m but not 5, there exists a k for which 2^k=c mod 10^m.
So it is enough to construct an m-digit number consisting only of digits 0,3,5,6,7,9 that is a multiple of 2^m but not 5, as follows: The ones digit is of course 6. Now supposing that you have a k-digit number d (possibly with leading 0's) that is a multiple of 2^k, extend to a k+1-digit number by adding to the left an even digit if d is a multiple of 2^(k+1) or an odd digit if d is not. The resulting number is a multiple of 2^(k+1). Since there are both even digits (0,6) and odd digits (3,5,7,9) to choose from, it is possible to construct such a number using only these digits.
Note that that's why I mentioned "So for all we know there could be a power of 2 consisting solely of the digits 5 and 6".
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Warp wrote:
Is 65536 the only power of 2 that doesn't have, in its decimal representation, any digit that's a power of 2 (ie. 1, 2, 4 or 8)?
65536 is the only power of 2 up to 2^40000000000 that doesn't have digits 1,2,4,8. I wrote a program to find other candidates based on their last 51 digits (i.e. mod 10^51). The program returned
16^7525657339 (last 51 digits 69707999760379505 77776399363966007 57506995373735936), and
16^9881236075 (last 51 digits 66955906599977637 96566660539696359 56056903569637376),
but using logarithms shows that
16^7525657339≈3.244240*10^9061794384, and
16^9881236075≈1.770509*10^11898193811,
so they don't work. Note that a power of 2 that doesn't have digits 1,2,4,8 must be a power of 16.
Unfortunately, as to whether one can prove that 65536 is the only power of 2 that doesn't have digits 1,2,4,8, I don't think it is possible to do so. Given a positive integer n, there always exists a power of 2 for which the final n digits do not have 1,2,4,8, so mod 2^m or 5^m arguments don't work. There don't appear to be any other mod arguments either, and there don't appear to be arguments based on the first few digits or on special factorizations.
So for all we know there could be a power of 2 consisting solely of the digits 5 and 6; the chance of that is practically zero but there appears to be no way to prove that it is actually zero.
There are problems based on manipulating digits in base 10 or what a number looks like in base 10 that are very easy to pose and seem almost impossible to solve. For example, the 196 problem is one such problem. Very often the best that can be done is the use of heuristic arguments which treat sufficiently large numbers as numbers with random digits; if applied to this question, the probability that there is a power of 2 greater than 2^40000000000 that doesn't have digits 1,2,4,8 is, I think, (1/(1-0.6))*(0.6)^40000000000, or whatever number that is close to zero. This is of course invalid math logic, but there is nothing else to work with.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Based on the [url=http://tasvideos.org/5175S.html
]rejection message in this submission[/url], the password glitch has been disallowed for all speed categories. Also, PCSX/PSXJin for this game is not allowed because of poor emulation.
@paosidufygth: We cannot stop you from doing your 100% TAS if you so wish, but it cannot be accepted to this site.
@paosidufygth: Please read this post. Also note:
Mothrayas wrote:
If you feel you have a long run that already had a lot of work put into it, and will need a while to be completed, you may request a continuance in this thread.
Samsara wrote:
The point of a continuance is to give leeway to people who don't want to give up long-term projects they started with a soon-to-be deprecated emulator.
Since you did not provide any other information (such as an existing WIP which you have already put a lot of work into), your requests were not granted.
Also, because of poor emulation, I do not think that any request for a continuance on Rockman X3 will be granted.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Based on the [url=http://tasvideos.org/5175S.html
]rejection message in this submission[/url], the password glitch has been disallowed for all speed categories. I assume this means the SNES version as well.
Sorry about that GlitchMan but you'll have to rework your any% run again.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
Warp wrote:
In short: 36 is a square number (because it's 6*6) and a triangular number (because it's 8*(8+1)/2). The question is: Are there other numbers that are also square and triangular at the same time? In other words, there exist some integers n and m for which n2=m*(m+1)/2. And if they are, what is the pattern?
We can rewrite n2=m(m+1)/2 as follows:
n2=m(m+1)/2
2n2=m2+m
8n2+1=4m2+4m+1
8n2+1=(2m+1)2
(2m+1)2-2(2n)2=1
a2-2b2=1 where a=2m+1, b=2n
This is a Pell equation. It is well-known that the solutions are given by an+bn*sqrt(2)=(a1+b1*sqrt(2))n=(3+2*sqrt(2))n
which can also be represented by the recursive formula:
an+1=3an+4bn
bn+1=2an+3bn
The first few solutions for a,b are
1, 0 (m=0, n=0)
3, 2 (m=1, n=1)
17, 12 (m=8, n=6)
99, 70 (m=49, n=35)
577, 408 (m=288, n=204)
3363, 2378 (m=1681, n=1189)
19601, 13860 (m=9800, n=6930)
and so on.
Amaraticando wrote:
What is the smallest natural number n such that n has some power whose the last trillion decimal digits are all ones?
The answer is n=71.
We want to find the smallest n such that there exists an integer k where the last trillion digits of nk are all ones. Some facts:
@ nk=1 (mod 10)
@ nk=11 (mod 20)
@ nk=11 (mod 50)
@ nk=11=3 (mod 4)
@ nk=1111=7 (mod 16)
Then:
@ n cannot be 0,2,4,5,6,8 (mod 10).
@ n cannot be 3,7,9 (mod 10); otherwise k is even and nk is a perfect square. But nk=3 (mod 4), which cannot be a perfect square.
@ n cannot be 1 (mod 20) since nk=11 (mod 20)
@ n cannot be 1 (mod 50) since nk=11 (mod 50)
@ n cannot be 11 since the residues of 110, 111, 112, ... (mod 16) are 1, 11, 9, 3, 1, ... , but nk=7 (mod 16)
@ n cannot be 31 since the residues of 310, 311, 312, ... (mod 16) are 1, 15, 1, ... but nk=7 (mod 16)
So the least possible candidate is n=71. We show that this is the solution.
We prove by induction:
1) For each m≥4, there exists a k for which 71k ends in 11...1 (m 1's)
2) For each m≥5, there exists a k for which 71k ends in 300...01 (m-2 0's)
Base step:
1) 7113=1111 (mod 10000)
2) 71250=30001 (mod 100000)
Induction:
Suppose that statement 1 is true for m and statement 2 is true for m+1. Let i be a value for which 71i ends in x11...1 (m 1's) where x is a digit, and let j be a value for which 71j ends in y300...01 (m-1 0's), where y is a digit. Let z be 7*(11-x) mod 10. Then 71i+z*j ends in w11...1 (m 1's) where w= (x+3*z) mod 10 = (x+3*7*(11-x)) mod 10 = (x+11-x) mod 10 = 1. So statement 1 is true for m+1. Furthermore, 7110*j ends in 300...01 (m 0's), regardless of y. So statement 2 is true for m+2. This completes the induction.
Since statement 1 is true for m = one trillion, we have that n=71 is the solution to the problem.
Edit: Fixed some bad notation.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
jlun2 wrote:
How exactly does the password glitch work? How many things can allowed from it? Any limits? There was a glitched password TAS of a different game that skips directly to the credits (usually does not do that), but that got rejected for being unvaultable.
I'll try to remember what I learned from disassembling the password routine from the SNES version.
After entering the password, the game decodes it and checks for its validity. There are five parity checks (hearts, subtanks/upgrades, chips/ridearmors, bosses alive, and Vile/Bit/Byte/Zero/intro status). If the password fails one of them, there is an error and the glitch does not work.
In the PSX version, there is also a chip upgrade consistency check somewhere in the routine (I don't know exactly where). The check is not in the SNES version. To pass the check, you must have 0, 1 or 4 chip upgrades and all chip upgrades require the corresponding normal upgrade. Otherwise, there is an error and the glitch does not work. Note: Entering 4 chip upgrades is valid but the game will remove them from your possession.
If the password passes all checks so far, then the game starts writing all the data determined by the password, including Vile/Bit/Byte status.
Then the game does two additional checks. One is to check that, if the intro stage is enabled, then no items are obtained and everyone is alive and not previously beaten. The other check is that, if the Beam Saber is enabled, then all bosses and Zero are dead.
If the password fails either of these checks, there will be an error. The game will then attempt to erase all the data it put in, but then fail to erase a couple addresses, including Vile/Bit/Byte status.
You can then exit the password screen. The game then erases the data again just to be sure, but it still fails to erase the Vile/Bit/Byte status.
At this point, starting a new game allows you to keep this Vile/Bit/Byte status.
The statuses work as follows. Each of Vile, Bit and Byte have two associated flags: either defeated or not defeated, and either dead or alive. In normal gameplay, dead implies defeated, but the password can circumvent this. How this plays out in the game is:
- Vile's stage may be entered only if Vile is neither defeated nor dead.
- You meet Bit only if he is neither defeated nor dead.
- You meet Byte only if he is neither defeated nor dead.
- In Doppler 1 you go to the Press Disposer room only if Bit and Byte are both defeated and dead. Otherwise you go to the Godkarmachine room.
- In the Godkarmachine room, Bit appears only if he is alive. Byte appears only if he is alive or he is not defeated. If Bit is dead and Byte is defeated and dead, then no battle takes place and you finish the level immediately (this is not supposed to happen in normal gameplay).
- In Doppler 2, the stage makes the Beam Saber available only if Vile is dead.
The idea of this TAS then is to set Vile to be dead, Bit to be dead but not defeated, and Byte to be defeated and dead. This allows you to skip fighting any boss in Doppler 1 and get the Beam Saber in Doppler 2.
Note that this TAS does not use valid passwords or savegames. It only enters an invalid password as a glitch, then starts a new game. Admittedly it is a cheap move, but without it the PSX any% version would be longer and all fights would be X-Buster only.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
I'll try to explain a little about what makes the PSX version different.
- There is the glitch that allows you to skip directly to the Doppler stages when you are at the stage select. To do this, press the arrow key towards the empty space on the menu (where the Doppler stage would appear if it was unlocked) and press X on the same frame.
- Wall-jumping is a few frames faster than in the SNES version. This changes a lot of movement strategy. This also appears to enable the glitch where Zero frees X immediately at the same time as killing Mac, though I haven't tested whether it can be done on the SNES version.
- Jumping after walking gives a height boost no matter if the floor is sloped or not. This can be seen on the first wall of the intro stage that X must normally wall-jump off.
- The Beam Saber is a bit more glitched in this game where X/Zero can turn to face left and the Beam Saber will still be out to the right.
- Left+right wall-jump glitch like in the SNES version is not possible in the PSX version.
paosidufygth also uses the invalid password glitch (which also works on the SNES version). Laseki and I knew about this glitch for a while but it appears to have been discovered independently by GlitchMan and also independently by paosidufygth as well. Inputting a password that enables the intro stage but gives you any item or defeats/kills anybody, or a password that enables the Beam Saber but leaves any of the 8 main bosses or Zero alive, but is otherwise valid (PSX adds a restriction that the chip upgrades be consistent with a valid playthrough; SNES doesn't), will make a password error but update the status of Vile, Bit, and Byte anyway. Using this, it is possible to set Vile's status to dead (to get Beam Saber in Doppler 2) and skip Bit and Byte's fights as well as skip both Doppler 1 end bosses (as in, you enter the bottom room and warp out without fighting).
Both the skip to the Doppler stages and the invalid password glitch account for the ridiculously low time.
Spikestuff wrote:
Does the game hardlock for anyone else on psxjin (after the credits)?
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
There is a problem. I can't get any music. I'm trying to use PSXJin v2.0.2 svn0 and load "Rockman X3 (Japan).cue". I also have the files "Rockman X3 (Japan) (Track 01).bin", "Rockman X3 (Japan) (Track 02).bin", ... , "Rockman X3 (Japan) (Track 32).bin" in the same folder.
Is there something special that I have to do to get music? Or is PSXJin unable to play music?
For me, BizHawk 1.11.6 has no problem playing music in Rockman X3 (PSX).
Edit: Apparently MDK and Pepsiman also have this problem.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
I watched this yesterday. This game is very long and has a lot of content. It's great that you were able to manipulate a lot of the game as evidenced by the 228561 rerecords.
Editor, Experienced Forum User, Published Author, Skilled player
(1943)
Joined: 6/15/2005
Posts: 3249
paosidufygth, are you submitting this run to tasvideos.org?
I was finally able to sync the run (bios is SCPH 1000, ROM name to select is "Rockman X3 (Japan).cue"), but I noticed that PSXJin seems to have a problem with the sound, and there is no stage music. I don't know why that is. Then I think that BizHawk is much better than PSXJin.
By the way, a faster glitch password setup:
1111
1117
1122
1181
, which I don't know how to do.
It's a geometric sum, and it's then easy to see that the probability goes to 1/sqrt(5) as N approaches infinity; what looks trickier is that it seems like all of the probabilities are rational for finite values of N, but it looks like a slog to prove it.