Skilled player (1651)
Joined: 7/25/2007
Posts: 299
Location: UK
Hmmm, who explained to them where the doors lead, was it the same person he said "Show me your door" to? Obviously asking that causes the truth teller to point to his own door, and the liar to point to the other; identifying both who is being honest and which is the safe door. Therefore, if upon asking this you find that he points away, that means you're currently speaking to the liar. And if this is the source of your original rules for the riddle, then clearly they're not true. That means the 2 doors are not Liar/Truth, but either guarded by Liar/Liar, or Truth/Truth. As we've already established the current one is lying, then that would imply both are, and that no door leads to safety. PS, does this explain why in Labyrinth, Sarah ends up in the pit? Her logic was fine, but I guess if the original set up for the riddle was performed by a liar, then that's why she still got screwed.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
The problem is usually posed such that you can only ask a yes/no question, and only one. That makes it more difficult.
Player (146)
Joined: 7/16/2009
Posts: 686
To be frank, if we're taking the Yu-Gi-Oh! episode as the setting, it's "because he had a hunch". For those who haven't seen it (or looked up a summary): he thinks the brothers don't play fair, and can switch the doors after you've made your decision. By concealing his "decision" (a coin) he manages to trick them into revealing the door they think he chose as dangerous (and the other as safe), while actually choosing the other door. Very little to do with any actual sort of logic riddle, really.
Mitjitsu
He/Him
Banned User
Joined: 4/24/2006
Posts: 2997
Scepheo wrote:
To be frank, if we're taking the Yu-Gi-Oh! episode as the setting, it's "because he had a hunch". For those who haven't seen it (or looked up a summary): he thinks the brothers don't play fair, and can switch the doors after you've made your decision. By concealing his "decision" (a coin) he manages to trick them into revealing the door they think he chose as dangerous (and the other as safe), while actually choosing the other door. Very little to do with any actual sort of logic riddle, really.
The only way I can deduce it is. Since they both said that one will only speak the truth, and the other will only speak lies. Then they must both be lying. If you point to a door and say "Which door am I pointing at?", and they both point to the same door, then one or both of them lie and only tell the truth when it's convenient.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
I don't trivially see why this equality is true when |x| < 1: 1 + 2x + 3x2 + 4x3 + 5x4 + ... = 1/(1-x)2
Joined: 2/3/2013
Posts: 320
Location: Germany
Flip wrote:
Hmmm, who explained to them where the doors lead, was it the same person he said "Show me your door" to? Obviously asking that causes the truth teller to point to his own door, and the liar to point to the other; identifying both who is being honest and which is the safe door. Therefore, if upon asking this you find that he points away, that means you're currently speaking to the liar. And if this is the source of your original rules for the riddle, then clearly they're not true. That means the 2 doors are not Liar/Truth, but either guarded by Liar/Liar, or Truth/Truth. As we've already established the current one is lying, then that would imply both are, and that no door leads to safety.
You deduct that if the one who told Joey the rules is the liar (he points away from his door), then it is not necessarily so, that each of the two guards has a unique door. If so, then both would not have shown to the same door in the first place (both lie about their door and both doors are different) creating a paradox. However if both are indeed liars, then the door they point away from is the only assigned door. If we are allowed to scrap the idea that each guard has a unique door though, that could have meant that one door was unassigned all along, and thus both could have told the truth from the very beginning (doesn't tell us anything about where each door leads still). Edit: Is it a given that in the original set of rules the truthteller guards the safe door and the liar the unsafe one? EditEdit: Read Scepheo's post. Nevermind the question... Edit 2: Granted, if a liar told the rules then potentially no axiom actually holds and thus we can't deduce anything...
All syllogisms have three parts, therefore this is not a syllogism.
Player (160)
Joined: 11/25/2006
Posts: 22
Warp wrote:
I don't trivially see why this equality is true when |x| < 1: 1 + 2x + 3x2 + 4x3 + 5x4 + ... = 1/(1-x)2
S = 1 + 2x + 3x^2 + 4x^3 + ... xS = x + 2x^2 + 3x^3 + 4x^4 + ... (1-x)S = 1 + x + x^2 + x^3 + ... = 1/(1-x) S = 1/(1-x)^2
Skilled player (1651)
Joined: 7/25/2007
Posts: 299
Location: UK
Warp wrote:
I don't trivially see why this equality is true when |x| < 1: 1 + 2x + 3x2 + 4x3 + 5x4 + ... = 1/(1-x)2
Standard formula for geometic series. Sn=1+X+X2+X3+X4+...Xn S[Sub]∞[/sub]=1/(1-X) =(1-X)-1 for |X|<1 dS/dx=1 + 2x + 3x2 + 4x3 + 5x4 + ... =d/dx (1-x)-1 =1/(1-x)2
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Xyphys wrote:
xS = x + 2x^2 + 3x^3 + 4x^4 + ... (1-x)S = 1 + x + x^2 + x^3 + ... = 1/(1-x)
I don't understand that step at all. (Also, since you didn't specify any limit in your proof, wouldn't it make the equality hold for all x, not just for |x|<1?)
Flip wrote:
Sn=X+X2+X3+X4+...Xn S=1/(1-X) =(1-X)-1 for |X|<1
I don't understand that jump either.
Joined: 2/3/2013
Posts: 320
Location: Germany
Warp wrote:
Xyphys wrote:
xS = x + 2x^2 + 3x^3 + 4x^4 + ... (1-x)S = 1 + x + x^2 + x^3 + ... = 1/(1-x)
I don't understand that step at all. (Also, since you didn't specify any limit in your proof, wouldn't it make the equality hold for all x, not just for |x|<1?)
It's a bit informally written down. x * S = x + 2x^2 + 3x^3 + 4x^4 + ... is indeed valid for any x. (1 - x) * S = S - x * S ("= 1 + 2x + 3x^2 + 4x^3 + ... - (x + 2x^2 + 3x^3 + 4x^4 + ... )") = 1 + 2x - x + 3x^2 - 2x^2 ... = 1 + x + x^2 + ... (for this step to be valid you'd need to prove that you may reorder the summands like that (because that's not always possible: https://en.wikipedia.org/wiki/Riemann_series_theorem)) (1 - x) * S = 1 + x + x^2 + x^3 + ... = 1 / (1 - x) is a form of geometric series (https://en.wikipedia.org/wiki/Geometric_series#Formula with a = 1 in this case) and converges for |x| < 1 (i.e. in this step you need to have |x| be < 1). To get S, divide by (1 - x) /= 0: S = 1 / (1 - x)^2
All syllogisms have three parts, therefore this is not a syllogism.
Amaraticando
It/Its
Editor, Player (159)
Joined: 1/10/2012
Posts: 673
Location: Brazil
An easy way to verify this is by doing the finite sum first: S(n) = 1 + 2x + 3x^2 + ... + nx^(n-1) xS(n) = x + 2x^2 + 3x^3 + ... + nx^n S(n)-xS(n) = 1 + (2x-x) + (3x^2 - 2x^2) + ... + (nx^(n-1) - (n-1)x^(n-1)) - nx^n (1-x)S(n) = 1 + x + x^2 + ... + x^(n-1) - nx^n But 1 + x + x^2 + ... + x^(n-1) is a geometric series, whose result is pretty known: (1-x)S(n) = [(1 + x^n)/(1-x)] - nx^n S(n) = [(1 + x^n)/(1-x)^2] - (nx^n)/(1-x) , valid for all naturals n and all reals x, except 1. The infinite sum is lim(n->inf) of S(n). Since lim x^n = 0, x < 1 and there's no indeterminate form, we can substitute: S(inf) = [(1 + 0)/(1-x)^2] - 0/(1-x) = 1/(1-x)^2 EDIT: You right, marzojr. "Canceling" in this case is so automatic that I forgot about the indeterminacy.
marzojr
He/Him
Experienced player (761)
Joined: 9/29/2008
Posts: 964
Location: 🇫🇷 France
Amaraticando wrote:
The infinite sum is lim(n->inf) of S(n). Since lim x^n = 0, x < 1 and there's no indeterminate form, we can substitute:
There is, actually: nx^n would be of the 0 * inf variety. But this one is simple enough to prove the limit is 0 when n -> inf by L'Hôpital's rule (as it fulfils all criteria).
Marzo Junior
Player (160)
Joined: 11/25/2006
Posts: 22
Amaraticando wrote:
(1-x)S(n) = [(1 + x^n)/(1-x)] - nx^n S(n) = [(1 + x^n)/(1-x)^2] - (nx^n)/(1-x), valid for all naturals n and all reals x, except 1.
Slight error here. It should be: (1-x)S(n) = [(1 - x^n)/(1-x)] - nx^n and S(n) = [(1 - x^n)/(1-x)^2] - (nx^n)/(1-x)
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Now I'm even more confused. According to Wikipedia, the Riemann series theorem states that if you have a conditionally convergent infinite series, you can rearrange its terms to get a new series that converges to something else, or even diverges. This raises two questions: 1) So? 2) How does that help to prove the equation?
Joined: 2/3/2013
Posts: 320
Location: Germany
Warp wrote:
Now I'm even more confused. According to Wikipedia, the Riemann series theorem states that if you have a conditionally convergent infinite series, you can rearrange its terms to get a new series that converges to something else, or even diverges. This raises two questions: 1) So? 2) How does that help to prove the equation?
My mistake. I punched something into Google ("kleiner Umordnungssatz", "small theorem of rearrangement") and took the first result thinking it would be a different name for the same thing. The "kleiner Umordnungssatz" says that you can freely rearrange summands of an absolutely convergent series. I'm honestly not even sure anymore that that theorem applies here at all, so forget about what I wrote. I edited my original post accordingly.
All syllogisms have three parts, therefore this is not a syllogism.
ALAKTORN
He/Him
Former player
Joined: 10/19/2009
Posts: 2527
Location: Italy
Does anyone know how to reverse this formula to find x? y = ax+b (mod M) I was told x = a-1(y-b) (mod M) but it’s not working…
Joined: 2/3/2013
Posts: 320
Location: Germany
ALAKTORN wrote:
Does anyone know how to reverse this formula to find x? y = ax+b (mod M) I was told x = a-1(y-b) (mod M) but it’s not working…
Without any further constraints there is no reverse function for (a*x + b) mod M. E.g. let M = 10, a = 1, b = 0, then 10 mod 10 = 0 and 20 mod 10 = 0 and 30 mod 10 = 0 a.s.o., so given y = 0, there's no single (but multiple) x for which the equation holds contradicting the definition of a "function". Edit: If you restrict x suitably (and have gcd(a, M) = 1 (just refer to FractalFusion and the site he linked for this...)), it is possible. See Masterjun's post below.
All syllogisms have three parts, therefore this is not a syllogism.
Masterjun
He/Him
Site Developer, Skilled player (1987)
Joined: 10/12/2010
Posts: 1185
Location: Germany
ALAKTORN wrote:
Does anyone know how to reverse this formula to find x? y = ax+b (mod M)
Maybe this helps?
Warning: Might glitch to credits I will finish this ACE soon as possible (or will I?)
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
ALAKTORN wrote:
Does anyone know how to reverse this formula to find x? y = ax+b (mod M) I was told x = a-1(y-b) (mod M) but it’s not working…
Let me guess: You're trying to find the inverse of X(n+1) = 0x343FD * X(n) + 0x269EC3 (mod 2^31). The reverse formula is X(n) = 0x39B33155 * X(n+1) + 0x2170F641 (mod 2^31). In general, the post that Masterjun linked is a possible way to work out the inverse. Note that if you need to calculate multiplicative inverse (a-1 (mod M)), you can use this applet. By the way, a-1 (mod M) doesn't exist unless gcd(a,M)=1. If gcd(a,M)>1, then f(x) = ax+b (mod M) doesn't have an inverse function, since multiple x's give the same f(x).
ALAKTORN
He/Him
Former player
Joined: 10/19/2009
Posts: 2527
Location: Italy
Thank you guys. :)
Skilled player (1416)
Joined: 10/27/2004
Posts: 1978
Location: Making an escape
I recently learned that one you do trig on any rational multiple of pi, you end up with an algebraic number. Is the inverse of this true? That is, when one does inverse trig on a real algebraic number between 1 and -1 inclusive, will the result be a rational multiple of pi? Or, for a specific example, can asin(1/5) be represented as a fraction of pi?
A hundred years from now, they will gaze upon my work and marvel at my skills but never know my name. And that will be good enough for me.
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
If n is an odd integer greater than 1, then asin(1/n) is not a rational multiple of π. I will give a proof using your specific example of asin(1/5) (n=5). First of all, for a given -1≤t≤1, asin(t) is a rational multiple of π if and only if acos(t) is a rational multiple of π, since asin(t)+acos(t)=π/2. So we just need to prove that acos(1/5) is not a rational multiple of π. Let θ be an angle with 0<θ<π/2 such that cos(θ)=1/5. Then sin(θ)=(√24)/5. Use α to denote √24, so that sin(θ)=α/5. Now suppose that θ=pπ/q for integers p and q with q>0. Then: 1 = cos(2pπ)+sin(2pπ)i = cos(2qθ)+sin(2qθ)i = (cos(θ)+sin(θ)i)2q = (1/5+iα/5)2q. Let m be the smallest positive integer such that (1/5+iα/5)m is a fourth root of unity ({±1,±i}), which exists because of the above observation. Now the imaginary part of (1/5+iα/5)m is: sum{j odd, 1≤j≤m} (C(m,j)(1/5)m-j (α/5)j) = α(1/5)m sum{j odd, 1≤j≤m} (C(m,j) αj-1) = α(1/5)m (m + sum{j odd, 3≤j≤m} (C(m,j) 24(j-1)/2)) = α(1/5)m (m+24s), where s is an integer. So α(1/5)m (m+24s) equals the imaginary part of a fourth root of unity, which is 0 or ±1. There are three cases: Case 1: α(1/5)m (m+24s)=±1. This implies that 1/α, and therefore α (which is √24), is a rational number, contradiction. Case 2: α(1/5)m (m+24s)=0, m is odd. Then m+24s=0. But LHS is an odd integer, contradiction. Case 3: α(1/5)m (m+24s)=0, m=2r is even. This means that (1/5+iα/5)2r=±1, and so (1/5+iα/5)r is a fourth root of unity with 0<r<m, contradicting the choice of m.
Skilled player (1416)
Joined: 10/27/2004
Posts: 1978
Location: Making an escape
Thanks for the response. Sorry it's taken me so long to reply; I've just been trying to take it in and understand what you're saying. I have a passing interest in mathematics, but I'm such a huge ignoramous about it. So at the risk of sounding like an ignorant newbie, I want to see if I have this straight: what you're saying is that if cos(x) + i*sin(x) is a root of unity, then x = pi*a/b, with a and b as integers, and b > 0. Which kinda makes sense when I think about it. The trick then is to prove that such a number is such a root. If I am understanding this correctly - and if I am not, then I apologize - , then that means that to demonstrate my previous question but with atan(1/5) instead of asin, we'd have to prove that √26/26 + i*5*√26/26 is a root of unity. Unfortunately, I can't understand your explanation starting at the word "sum", so I'm a little lost as to how one would prove that.
A hundred years from now, they will gaze upon my work and marvel at my skills but never know my name. And that will be good enough for me.
Editor, Expert player (2073)
Joined: 6/15/2005
Posts: 3282
Hi Ferret Warlord, If there is anything that is not easy to understand, please tell me right away, since I am not certain of the appropriate level of explanation in all cases. In fact, Niven's Theorem states that the only rational θ in degrees (0°<=θ<=90°) for which sin(θ) is rational is sin(0°)=0, sin(30°)=1/2, and sin(90°)=1. Likewise this implies that the only rational θ in degrees (0°<=θ<=90°) for which cos(θ) is rational is cos(0°)=1, cos(60°)=1/2, and cos(90°)=0. Note that rational degrees is the same as rational multiple of pi in radians. Note also that this theorem says nothing about tangent. However, a post on xkcd.com indicated a rather simple way to prove that, say, acos(1/5) is not a rational multiple of pi, better than what I posted, although it assumes something from field theory. (In my previous post, I used the Binomial Theorem on (1/5+i√24/5)m and then used some number theory to prove it). First of all, θ is a rational multiple of pi if and only if cos(θ) + i*sin(θ) is a root of unity. So, let's say that we want to prove that acos(1/5) is not a rational multiple of pi. So we want to prove that 1/5+i*√24/5 is not a root of unity. Now 1/5+i*√24/5 is an algebraic number of degree 2, since if z=1/5+i*√24/5, then 5z-1=i*√24 and 25z2-10z+1=-24 and so 1/5+i*√24/5 is a root of 25z2-10z+25. However, the algebraic degree of a primitive nth root of unity is φ(n), where φ is the Euler phi function (in other words, the number of positive integers between 1 and n inclusive that are relatively prime to n). If n has prime factorization p1a1p2a2...pkak, then φ(n)=(p1-1)p1a1-1 (p2-1)p2a2-1 ... (pk-1)pkak-1. Using this, we can determine that the only values n for which φ(n)=2 are n=3,4,6. This gives the only possible nth roots of unity with n being one of these values are ±1, ±i, ±1/2±i*√3/2, none of which are equal to 1/5+i*√24/5. So 1/5+i*√24/5 is not a root of unity, and so acos(1/5) is not a rational multiple of pi. In fact, we can prove a general case. To prove that asin(p/q) or acos(p/q) or atan(p/q) is not a rational multiple of pi except for a handful of exceptions for p,q, we just have to show that √(q2-p2)/q+i*p/q or p/q+i*√(q2-p2)/q or q/√(p2+q2)+i*p/√(p2+q2), respectively, is not a root of unity. The above quantities each have algebraic degree at most 4. The only values n for which φ(n) is at most 4 are n=1,2,3,4,5,6,8,10,12. This gives as the only possibilities for nth root of unity ±1, ±i, ±√2/2±i*√2/2, ±1/2±i*√3/2, ±√3/2±i*1/2, ±(√5+1)/4±i*√(2√5-10)/4, ±(√5-1)/4±i*√(2√5+10)/4. I leave the rest for you to work out. The asin case results in Niven's Theorem. Edit: Corrected a mistake for the atan case.
Banned User
Joined: 3/10/2004
Posts: 7698
Location: Finland
Suppose there existed a program that answers this question: Given a natural number (in base 10) and a set of mathematical operators, does there exist a closed-form expression that uses those operators (and numbers in base 10) that is equal to that input number, and that uses less symbols than the input number? (I'm counting each digit as a symbol, as well as each individual mathematical operator.) I'm wondering what the computational complexity of that program would be.