Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
This kind of proofs works if limit exists. They based on some properties of limits, like limit of sum of sequences, and reordering of summation. And here is interesting thing. This means, that in any other system where limit exists, and it doesn't equal to -1/8 for example, then some of basic properties should also be violated.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
p4wn3r wrote:
r57shell wrote:
p4wn3r wrote:
Now, if the game is fair, it should also be fair when the sequence of coin flips HHTT just showed up.
What means to be fair at some moment?
It means that, if the game, played infinitely, is fair, then the game, when it's played only until the sequence HHTT shows up, should also be fair.
Ah, alright. Now I get it. So basically, imagine casino which close its business as soon as HHTT arrived, and all gamblers also await HHTT. And, expected balance is still 0 in the end, so at last step should be just total wins. So for HHTT wins only first gambler, and all other loose. But for HHHH all of them win so sum of powers of two. Ok. Now all clear. Suffixes and prefixes is also clear now.
Didn't get proof though, nevermind.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
I don't want to get a lot of text about it, but I'll phrase precisely what I don't understand:
p4wn3r wrote:
Now, if the game is fair, it should also be fair when the sequence of coin flips HHTT just showed up.
What means to be fair at some moment?
p4wn3r wrote:
At that point, the casino got t dollars from gamblers and had to pay back 16 dollars to the gambler that won.
How do you calculate that at some moment they spent X money? It looks like "out of thin air".
p4wn3r wrote:
E[t-16]=0
Where this equation came from? What is t?
The more I ask, the more I understand.
Looks like, you not calculating expectation. You just calculate balance of casino. And you assume all of them betting HHTT. And at that moment, at point HHT arrived, ppl already leaved, who was betting. And next three will get HTT, TT, T and you may calculate do they leave already or not. Or, maybe I don't understand again.
But I see here relation with how you could propagate expectation in automaton that I was drawing. You can move forward and cut loops using infinite sum of geometric progression. You'll get same result. It's tricky though.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
p4wn3r wrote:
Now, if the game is fair, it should also be fair when the sequence of coin flips HHTT just showed up.
From this and after, I'm unsure.
Ok. I was able to use Masterjun approach (or idea at least) for HHHHTTTT, and for HHHHHTTTTT.
I had mistake in first automata: https://imgur.com/iz5RiTm
Some arrows are steps by H, and other arrows are steps by T. So, mistake was that I need arrow from 4-th H to itself, instead of arrow back to 0.
Then, derivation is here, for curious.
Indeed, in average you need 256 tosses for HHHHTTTT and 1024 for HHHHHTTTTT.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
Chanoyu wrote:
If I apply the same correction to my 'don't care about heads or tails' solution, I get 1023 average tries. My code does not disagree, in multiple tries it hovers about that number as well. It really may have been that simple.
I don't know what is simple. Answer number is simple, yes, but none of derivations of it is simple.
I don't know how you guys derive it using some recurrence relations with expectation or markov chains, but I was able apply method I was using before, to the case where you expect exactly heads. And for n heads we need 2n+1-2 tosses. Derivation: https://imgur.com/qA5d8V4
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
Looks like my question is either ignored, or too much complicated, or too hard, or just not noticable.
Chanoyu, looks like you ignoring that 10 heads may appear as subsequence. Your calculations holds when you do: 10 toss. Is all heads or tails? no! Make fresh new 10 tosses. But what if it was 1 tail and 10 heads 9 tails? Your calculation assume those two as two fails in the row.
Warp wrote:
This got me thinking: What's the expected average number of times you'll need to toss the coin in order to get 10 of the same side consecutively?
Surprisingly, exactly 1023 tosses. I was also surprised when I got this result. Perhaps I have mistake somewhere.Alright, I'll say a tiny info what I was doing: let say C(n) is number of combination we accept as succes during exact n tosses. Then G(x) is generator of this sequence, and a bit spoiler, it's like a tribonachi numbers but 9-nachi numbers. Generator easy derivated, then you just need to prepare it well and plug in certain number. Here is whole derivations without text: https://imgur.com/Cm81u7LProbably for n successive heads/tails formula is 2^n - 1. But I'm lazy to redo all derivations. Also I'm lazy replace number of tosses by new variable.
By the way, I don't know how you can apply this method to get number of tosses to get 10 heads. exactly heads! not something else.
Edit: Actually it's easy to prove that number for heads is exactly half of C(n), so for exactly heads you need exactly 2046 tosses in average.Edit2: Something is wrong with previous edit. My words about 2046 was out of thin air. Formulas tells it should be 1023/2 which is less, and it's strange. I'll investigateEdit3: Ah! now any amount of tails can be. So my first edit is wrong in this part. Sequence is completely new. Interesting.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
tower of x power was also discussed in lockdown math by 3Blue1Brown recently. With solution and proof. Much funnier to ask x^x^x... = 2 straight after ask about x^x^x... = 4, and you get in both questions answer sqrt(2) :D
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
p4wn3r wrote:
I guess I don't count, because I looked at the solution analysis when you posted it :P
There isn't described minimum number of points. If it is, then can you tell location? (for example Test 3 paragraph 5 statement 10, or in any other understandable way. I don't want quote under spoiler (idk why))
Edit: ah, I didn't say points you check are random. So, I don't mean random points. You also allowed to pick next one based on result of previous one.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
r57shell wrote:
Edit: I want to mention recent task from Google Codejam 2020 Round 1B second task under name Blindfolded Bullseye. I don't think everyone here is familar with programming, so for those who interested just look statement there. It's very interesting problem. :) For those who curious about solution, there is "analysis" button with solution. Reason why I mentioned it here, I tell a bit later.
I waited a bit because I don't want to spoil solution. Part of my question is related to solution.
I'll rephrase everything to make question what I find interesting / related.
You have square, and you know that there is disk non-strictly inside square.
And nothing moves. Everything is in fixed position.
You can tell is point non-strictly inside the disk or is it strict outside the disk.
How many points enough to check to find at least single point non-strictly within the disk knowing that radius of the disk is greater than one fourth of side of the square.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
p4wn3r wrote:
r57shell wrote:
Second misunderstanding is, actually more precise knowledge of previous one. I need only two examples: f(x) = 1 only at x = zero, and everywhere else is 0 is
also fit requirements.
That's not true. For non-zero x, f(x-x)=f(x)f(-x). For this f, this would imply 1=0, so this function does not work.
Alright, my mistake :( Then I think for f defined on non-negative R it should work.
FractalFusion, thanks, now I know what name of what I was describing. :)
Consider a non-constant function f: R -> R satisfying:
f(x+y) = f(x)f(y),
for all real x and y.
For those who watched 3Blue1Brown lockdown math, they would think they know answer. But I guess there is some misunderstanding.
Proof that is easy to follow that was done by 3Blue1Brown is following: if f(x+y) = f(x)(y) it should also work for y = 0 thus if(x + 0) = f(x)*f(0) = f(x) thus f(0) = 1. Wait! Hold on. Last sentence follows from f(x)*f(0) = f(0) by division by f(0). What if f(0) = zero? Well, then f(x) = f(x+0) = f(x)*f(0) = 0. This means that f(x) = 0 for any x. So, this is why mentioned corner case function f(x) = 0. Spoiler: that is the only constant f(x) satisfying conditions.Second case: f(0) not zero -> f(0) = 1. Move on: f(x+1) = f(x)*f(1), f(x+2) = f((x+1)+1) = f(x+1)*f(1) = f(x)*f(1)*f(1) In other words, for any integer k we have f(x+k) = f(x)*f(1)k Let's call f(1) = a, then f(x+k) = f(x)*akThen, we have f(1) = f(1/2+1/2) = f(1/2)*f(1/2) = f(1/2)2, thus f(1/2) = +-sqrt(a). Minus sqrt version looks odd, but it fits well so far. So we want to find counterexample. It's easy. f(1/2) = f(1/4+1/4) = f(1/4)*f(1/4) it should be square. So it must be positive.Next, f(1) = f(1/3+1/3+1/3) = f(1/3)*f(1/3)*f(1/3) = f(1/3)3, thus f(1/3)3 = a -> f(1/3) = a1/3. So, for any natural k f(1/k) = a1/kNext, f(2/k) = f(1/k+1/k) = f(1/k)*f(1/k) = f(1/k)2 = (a1/k)2 = a2/k, thus f(2/k) = a2/k. Similarly f(n/k) = an/k for any integer n and natural k.Now we covered all rationals. So only irrationals left. Also we know that f(x+n/k) = f(x)*an/k for any integer n and natural k. Irrational + rational is always irrational. So, we don't have any ristrictions on irrationals. But! within class of irrational x - we know that f(x+n/k) should be f(x)*an/k. So, this is similar to cosets from group theory (I'm not sure that it's precisely cosets).
I didn't prove that any set of values for f(x) for each cosets + f(1) is satisfying everything. But I think you can claim it.If we add condition for f(x) to be continious, then for any irrational x there is sequence of rationals n/k with limit x, so f(x) should be limit of an/k so it should be ax.First misunderstanding is filled: if it's continious then yes: f(x) has to be ax or f(x) = 0. Being continious is important!Second misunderstanding is, actually more precise knowledge of previous one. I need only two examples: f(x) = 1 only at x = zero, and everywhere else is 0 is
also fit requirements. This is actually how 0x often defined. And next example is following: f(x) = ax for all rational x and f(x) = 0 for anything else is also fit requirements <- this is why I think you can claim that statement about something similar to cosets is true.I want to say more about latest example. Let's prove it fits well.
First case: f(rational+rational') = f(rational)*f(rational') - obvious.
Second case: f((irrational+rational)+rational') = f(irrational+(rational+rational')) = f(irrational)*an/k for some rational n/k. so this is also ok. (just zero multiplied by something)
Third case: f((irrational+rational)+(irrational+rational')) = f((irrational+irrational')+(rational+rational')) = f(x)*f(y)*an/k for irrational x,y and rational n/k.
So, this actually disprove my claim about any f(x) for cosets. They actually need to follow same rule: f(x+y) = f(x)*f(y) where x and y is irrational. for example f(sqrt(2)*n/k) = f(sqrt(2))n/k for any rational n/k. This actually means that things similar to cosets should be closed over multiplication by rational and addition of rational. Probably then you can claim that for any values for this new
similar to 'cosets' f(x) will fit conditions.
Oh, latest is also wrong. f(sqrt(2)+sqrt(3)) = f(sqrt(2))*f(sqrt(3)). You can't define those three independently. Alright. Anyway, I think there exists basis of probably continious number of irrationals where you can arbitrarily define values and reconstruct function using them.Edit: I want to mention recent task from Google Codejam 2020 Round 1B second task under name Blindfolded Bullseye. I don't think everyone here is familar with programming, so for those who interested just look statement there. It's very interesting problem. :) For those who curious about solution, there is "analysis" button with solution. Reason why I mentioned it here, I tell a bit later.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
Хочу лишь подчеркнуть, что если ты просто будешь передавать клавиши из соседнего процесса симуляцией нажатий, то не факт что это даст детерминированный эффект. Что значит детерминированный? Ну это значит воспроизводимый. Так что надо или реплеи встроенные менять, или всё же встраиваться в приложение чтобы подсовывать кнопки в нужный момент.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
p4wn3r wrote:
p4wn3r wrote:
Eventually you reach am=an, and since it's invertible you can cancel out and have am-n=1.
Do you have any doubts about this? It's implicitly assumed that n<m, and the cancellation is justified because you can multiply both sides by a-n
My bad :( Yes, it's enough to show that it has to come back to 1.
p4wn3r wrote:
r57shell wrote:
Doesn't fact with powers go back to 1 work only about cyclic groups?
No, it works for all finite ones.
Ok, I'm lazy to check.
p4wn3r wrote:
(*) You don't need to know anything about phi(n) to show this particular statement, I don't know why you're bringing it up here.
My point was that sometimes you may bring in some general things and prove by them, claiming that it's easier, and get circular proof. It's not the case, but point was about: general case can be result instead of cause.
p4wn3r wrote:
(*) Why is knowing Bezout's identity a problem? It's a result used even in elementary number theory, abstract algebra is not the thing that adds it into the problem.
It's not a problem. Just additional "dependency" :D So, you need to know it and know its proof.
p4wn3r wrote:
(*) Regarding Lagrange's theorem and orders of elements, it's in the first chapter of any book.
Then we need to study theory of groups first chapter.
p4wn3r wrote:
The thesis I am trying to present here (unsuccessfully, it looks like) is that it's more productive to study, and even define, number theory in an algebraic manner right away. It takes some time to familiarize with algebra, yes, but it's much better to study it than spend lots of time on elementary proofs that don't have a suitable generalization, and are much longer.
I would say even more general: more you know, better tools you have. Usually any proof can be used somewhere else, at least its tricks.
Back to Fermat's Little Theorem. I'll gather all things together:
1) What is group: (closure, identity, invertible - what is multiplicative inverse)
It is first that you use when you claim that all invertible make a group.
oh, something is missing here again. You said it's shortcut to show that it's subgroup. Then we need to have group first (over multiplication!, because subgroups work only over the same operation). Anyway, keep going
2) What is subgroup.
3) Bezout's identity.
Now size of group is proven.
4) Prove that any element a generate subgroup - using this argument with a^n = a^m and finite size & invertible any element. Btw we skipped part of prove that it's indeed subgroup, not just array of powers.
5) Largange's theorem (closets, etc) (first chapter of group theory)
good list to study. Lets say "trivial, just from size of group = p-1" :)
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
p4wn3r wrote:
r57shell wrote:
p4wn3r wrote:
Notice that invertible elements in Zn, for n any number, form a group, because for any two a and b in Zn, ab-1 is also in Zn.
I think you mean (ab)-1.
No, I don't. You do not seem very familiar with algebra.Proving that for a, b in a set implies that ab-1 is in the set is a shortcut to prove that something is a subgroup.
Yes, I'm not familiar with shortcuts in proofs. But I'm familiar with many facts, like ap-1 = 1 (mod p) and aphi(n) = 1 (mod n), and that order divides phi(n) and so on. Also, that Zp is cyclic and exists generator. I don't dig into proofs, I heard them, but I don't remember them. It's kind of disclaimer.
Now, regarding to shortcut, and proficiency: You said ap-1 is trivial fact just from size. Now I wonder, did you mean it's trivial who is familiar with group theory and knows all that stuff about phi(n), Lagrange's theorem, Bezout's identity, orders of elements, orders of groups, subgroups, invertible elements, and so on? If yes, then I agree, it's trivial. And also trivial proof that Fermat's theorem for n = 3.
When I said "I don't know trivial proof" I meant prove with much fewer facts used, and much "simpler" facts. For example, you could prove Fermat's little theorem using Euler theorem a^phi(n) = 1(mod n) - but it's ugly way.
Now, regarding the shortcut. This fact is about any subgroup of any group. Now I want to prove it. First, I want to show that if H is subgroup then ab-1 is in G. Because b is in H then b-1 is in H, so ab-1 is also in H. This part is obvious.
Next, I need to prove opposite: if ab-1 is in H then e, ab, a-1, b-1 is in H. Alright, if ab-1 is in H, then if b = a we get aa-1 is in H (wasn't obvious until I tried a=b) It looks obvious but it's suspicious. It raises question: does it means that stating ab-1 is in H we assume that b-1 exists? Otherwise how can we tell that ab-1 is in H if we don't know that b-1 exists? So, from now on, I'll imply that we know that b-1 exists. But it's for any a, b so it also works for b = a so this means a-1 also exists. Then aa-1=e. But look! it's useless! existance of a-1 is already implying that e also exists. And we don't need to put b = a because b-1 already exists because a can be also b.
If this is exactly how shortcut works: imply that a-1 is in H already proven from the fact that ab-1 is in H is strange. Not obvious nor trivial. And, actually it's then identical to telling that identity and a-1 is in H and only after that you may claim ab-1 is in H, otherwise b-1 in that expression is meaningless.
If this is not how it works, then please explain, I don't get it.
Edit: Oh, looks like I understand now. The thing is: operation on H and G is the same. And we know that e from G is also e for H because operation is same. And we know that if b from H then b is also from G, then we can get b-1 in G and check that it is in H. Then yes, we can put a = b, a = e and so on and we get shortcut working.
p4wn3r wrote:
r57shell wrote:
p4wn3r wrote:
Now, take an element a and look at the subgroup it generates: {1,a,a^2, a^(d-1)}, where we write d as the size of this subgroup. Notice that we have a^d=1.
You need first prove that it can't stuck somewhere for eternity. Without additional knowledge all we know that all powers are invertible elements of Zn, in other words, values from 1 to p-1, but it doesn't prove that there is non-zero d for which a^d = 1.
Edit: Ah, I missed: you say it generate subgroup: hmm is it trivial?
The group is finite, so obviously it cannot get stuck forever.
No, why 1, a^1, a^2,a^3... can't correspond to 1,2,3,3,3,3,3,3,3,3,3? Each element is from Zn, but it doesn't go back to 1.
p4wn3r wrote:
It's quite general that the set of all powers of an element forms a group, which is abelian and cyclic. If you have doubts, you can check using the method I showed earlier.
I don't have doubts. I know that for any a I'll get back 1 because it is cyclic. I just don't remember proof. What you said doesn't look like a proof. "it is finite" - not an argument unless you use something in addition.
p4wn3r wrote:
r57shell wrote:
Next you use Lagrange's theorem, which is long lecture about orders.
I wholly disagree with this. The proof of Lagrange's theorem boils down to the simple fact that you can define cosets given a subgroup, and they form an equivalence relation with sets of the same size for each class.
So, now we need also knowledge about closets and their size.
p4wn3r wrote:
Anyway, it's my feeling that you don't appreciate the simplicity of the proof because you're not very familiar with abstract algebra.
Probably. Also, I don't know relationship about facts. Which fact comes first. You can't use fact that you'll prove later, for proving fact before, otherwise you'll get logic loop.
p4wn3r wrote:
This takes a long time to get used to, but I, for example, when I read somewhere that the size of a group is n, it immediately comes to me that if I take successive powers of an element a number of times that divides n, I'll get the identity. That's why I didn't even bother to provide a proof of this when I mentioned it.
Doesn't fact with powers go back to 1 work only about cyclic groups?
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
p4wn3r wrote:
I usually read Zp as the "ring with size p and modular arithmetic".
It doesn't matter how you read. If you plug in p = -5 into usual definition Zp = Z/pZ you'll have set: Zp = {{-5k+0 : k from Z}, {-5k+1 : k from Z}, {-5k+2 : k from Z}, {-5k+3 : k from Z}, {-5k+4 : k from Z} }
Which is identical to Z5
I had mistake in my previous reply. When I said about all divisible by p, for some reason I was talking about pZ, not about Z/pZ.
Also, if you think about remainders of division by (-5), they still from 0 to 4 in math notation.
p4wn3r wrote:
Notice that invertible elements in Zn, for n any number, form a group, because for any two a and b in Zn, ab-1 is also in Zn.
I think you mean (ab)-1. I agree, it's obvious: (ab)-1 = b-1a-1, abb-1a-1 = a*1*a-1 = 1 from associativity. b-1a-1 is in Zn because each is operand is in group.
Existance of inverse is identical to ax+bn=1 - is obvious, but Bezout's identity is not trivial. Yes, it works for 1...p-1, but I asked from the beginning how from size p-1 prove, so I assume that we know that size is p-1.
p4wn3r wrote:
Now, take an element a and look at the subgroup it generates: {1,a,a^2, a^(d-1)}, where we write d as the size of this subgroup. Notice that we have a^d=1.
You need first prove that it can't stuck somewhere for eternity. Without additional knowledge all we know that all powers are invertible elements of Zn, in other words, values from 1 to p-1, but it doesn't prove that there is non-zero d for which a^d = 1.
Edit: Ah, I missed: you say it generate subgroup: hmm is it trivial?
Next you use Lagrange's theorem, which is long lecture about orders.
Well... It doesn't look trivial. Most trivial proof that I know is from Mathologer video with necklace. There is other way to prove it using multiplication tables + diagrams but I don't like it.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
Had to restrain myself to not involve into that but now I can't :D
p4wn3r wrote:
In any case, Fermat's little theorem is proved when he discusses the structure of Z_p, when p is a prime (I think we can all argue that negative sizes for fields don't make sense, so it should be clear that p is positive here).
I disagree with that Z_p with negative don't make sense. Z_p most of time is defined as Z/pZ - this is so called 'factor group'. Here pZ is actually subgroup of Z, and each element of Z/pZ is actually is a whole set of numbers divisible by p. It's easy to show that pZ with negative p is same as with positive p. Example, p = 5, then pZ = 5*{...-3,-2,1,0,1,2,3...} = {...-15,-10,-5,0,5,10,15...}. when p = -5, then pZ = = -5*{...-3,-2,1,0,1,2,3...} = {...15,10,5,0,-5,-10,-15...} So it's just in reversed order, but order doesn't matter. so Z/pZ = Z/-pZ. Therefore, if Z_p is defined as Z/pZ, then negative p is possible. Personally I never heard of different way of difinition.
p4wn3r wrote:
The reason is that the theorem follows immediately from the fact that the multiplicative group of Z_p has size p-1. And that's it, no need to write down formulas. The statement is so good that it even gives you directions on how to prove it. (Why all nonzero elements of Z_p are invertible?)
I don't know proof from just size = p-1. Can you share it? I doubt it's trivial.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
Warp wrote:
1 + 100 + 1002 + 1003 + 1004 + ... + 100n
Just a few thoughts: for composite n its also composite. trivial fact. for n = 3 it is composite (even though 3 is prime). I don't see connection from n being prime. But this number is result of 9999/99 or 1111/11, but it didn't help.Edit: other thoughts:
Suppose p is our prime number, and n is also prime (using facts above)(102n-1)/99 = p (mod n)assume 99 != 0 (mod n) (otherwise n is 3 or 11)so we can multiply both sides by 99. and there is multiplicative inverse
of 99. everything is fine.102n-1 = p*99 (mod n)using theorem ap = a (mod p) for each prime p and any a10n2 = 10^2 (mod n)100-1 = p*99(mod n)99 = p*99 (mod n)1 = p (mod n)so p can be prime if p-1 is divisible by n, if n != 3 or 11so, if somehow you can prove that p-1 is not divisible by n then we have a proof.Solution: but I don't like it, found it by checking n = 5, and n = 7.
for odd number n = 2k+1, it can be represented as 9091*11111, just checked for factorization for 5so formula is a = (10n-1-1)/99*90+1 = (10n-10)/11+1, b = (10n-1)/9a*b = ((10n-10)/11+1)*(10n-1)/9 = (10n+1)*(10n-1)/99 = (102n-1)/99probably normal idea was (102n-1)/99 = (10n-1)*(10n+1)/99 = p, then notice that 10n-1 is divisible by 99 if n is even -> solution for even ones. otherwise it's divisible by 9, so we have to check that 10n+1 is divisible by 11 when n is odd. it is easy. 10^n = -1^n (mod 11)
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
This has no solution. I just describe what I did.
For the sake of not cheating, I derived parametrization myself.
a^2+b^2 = c^2, (we also want gcd(a,b,c) as small as possible)
b^2 = c^2 - a^2
c^2 = (c-a)(c+a)
Now, we want to prove that (c-a) and (c+a) are perfect squares or multiplied by two (about multiplied by two I discovered much later).
To prove it, first we claim that (c-a) and (c+a) can't be divisible by same odd number k.
both (c-a) and (c+a) can be divisible by same k if either i and j both divisible by k or k is even. it comes from equation:
c+a = 0 (mod k)
c-a = 0 (mod k)
-> 2c = 0 (mod k) and 2a = 0 (mod k)
if k is even, then either both c and a have remainder k/2. or both have remainder 0.
for k = 2, they should just have same parity.
if k is odd, then 2*c is divisible by k if and only if c divisible by k, similarly for a.
Thus, for odd p if both (c-a) and (c+a) divisible by p then c and a also divisible by p, and b^2 divisible by p^2 because it's multiple of (c-a)*(c+a), thus all three sides of triangle divisible by p and we can scale down triangle in p times. But we don't wan't to. We will find scaled down version first, and then scale it up by p if we want to.
This means (c-a) = 2^x*n^2, (c+a) = 2^y*m^2, where n and m is odd.
OR we can have x and y to be 1 or 0, if we allow n and m to be even. To have (c-a)*(c+a) to be perfect square we should have x+y = even. This means either (c-a) = n^2 and (c+a) = m^2, or (c-a) = 2*n^2 and (c+a) = 2*m^2. where n can be either even or odd.
For some reason, I didn't thought about 2n^2 and 2m^2 version, and thought only (c+a) and (c-a) both squares. But right now I see that common representation can be derived from 2n^2 and 2m^2. Probably if (c-a)*(c-b) is form of 2n^2 and 2m^2 then (c-b)*(c+b) is form of n^2 and m^2.
so, lets say n^2 = (c-a), and n^2+2nm+m^2 = (c+a)
then (c-a)+(c+a) = 2c = 2n^2+2nm+m^2
and c = (2n^2+2nm+m^2) / 2
similarly a = (2nm+m^2)/2
and b^2 = c^2 - a^2 = ((n^2 + (n+m)^2)/2)^2 - ((2nm+m^2)/2)^2
b = n*(n+m)
When both n, and m even we have c = (8x^2+8xy+4y^2)/2 and a = (8xy+4y^2)/2 both even.
Next, n is even and m is odd -> c and a are fractions because all except m^2 is divisible by 2.
Next, if n is odd and m is even -> c = (2n^2+4ny+4y^2)/2 and a = (4ny+4y^2)/2
now c is odd and a is even, so this is fine
and in the end, n and m both odd is also fine.
then area is a*b/2 = n*(n+m)(2nm+m^2)/4
and both sides multiplied by some rational s = x/y it should be:
n*(n+m)(2nm+m^2)*x*x/(y*y*4) = 6
thus n*m*(n+m)(2n+m)*x*x/24 = y*y
then (later on) i was trying to find those with x = 1, with hope I'll find them.
but first, i didn't like this version, and instead I tried:
(c-a) = n^2, (c+a) = m^2
and derived in similar way c = (n^2+m^2)/2, a = (n^2-m^2)/2, b = n*m
similarly a*b/2 = (n-m)*(n+m)*n*m/2
a*b*x/y*x/y/2 = n*m*(n-m)*(n+m)*x*x/(2*y*y) = 6
n*m*(n-m)*(n+m)*x*x/24 = y*y
and similarly I was looking for x = 1. so y*y should be perfect square.
this is where I got my print(i,j,((i-j)*(i+j)*i*j/24)**0.5)
and got (3, 1), (6, 3), (15, 5) ...
and posted (3k-k)*(3k+k)*3k*k/24
Then, after question about details, when I tried to output actual triangles, it turned out that they are similar.
Thus, I've found only one solution. Then, I noticed that if gcd(n,m) is d, then gcd(a,b,c) is at least d, so I did output only if gcd(i,j) and only found these:
3, 1
49, 1
3267, 2209
and no proof about infinite.
By the way, I was thinking that (n+m) and (n-m) to be also perfect squares, or 2*square, but it didn't work.
On the next day, I did google solutions, and all I've found is geometric out of thin air, and elliptic curve. Actually, even elliptic curve was out of thin air. I know math about elliptic curves, but I wouldn't say it's 'basic advanced knowledge'. For me, even derivation of pythagoras triples already 'basic advanced knowledge'.
Later on, I found video, where was normal proof that there is no similar triangle with area of one. But then, suddenly lecturer said: "if you have single solution of fixed area, you can find other solution using following formula:", and this formula is just the method we applied to prove about area one, just in general form. And also noted that it's basically doubling point of elliplic curve. I didn't want to verify it, anyway it was already cheating: googled solution. :)
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
p4wn3r wrote:
Could you share some details about the implementation of your code? Or, at least, the first few cases?
print(i,j,((i-j)*(i+j)*i*j/24)**0.5)
9 3 9.0
15 5 25.0
first one is 3,4,5 triangle
second one is 3,4,5 triangle also... oh
OH, I have mistake. then, fail. I apologize.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
p4wn3r wrote:
Prove that there are infinitely many right triangles with rational side lengths whose area equals 6.
Solved right now. I did use a little bit of programming though, to see if there is any solutions. As a proof that I solved it, I'll just leave following: (k*2)*(k*4)*(k*k*3)
Had to use some 'basic advanced knowledge' xD
p4wn3r wrote:
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
p4wn3r wrote:
Is it possible to place the vertices of an equilateral triangle on the points of a square grid?
Proof: No. Easy to prove. Area of any triangle with points on the grid is multiple of 0.5. Area of equilateral triangle with side L with points on grid is L*L*sqrt(3)/4 thus it's always irrational, because L*L = x*x+y*y for some x and y. In other words, area is always a whole number multiplied by sqrt(3)/4
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
I'm a bit late.
Just want to stress out:
1) Sonic has Death Egg 1, Death Egg 2 and Doomsday Zone. Knuckless ends in Sky Sanctuary
2) Knuckless has some different bosses.
I don't know about tails.
Personally, I would accept and go back to the problem when it become issue.
Side note: Diablo II LOD on speedruns.com Any% Normal has 2*3*7 = 42 categories :) Only two of them are empty. But there is also Any% Hell and Misc.
Experienced Forum User, Published Author, Player
(107)
Joined: 12/12/2013
Posts: 380
Location: Russia
Oh, how did I miss it? :o
Easy yes vote.
In pluto 2nd stage you can zip right behind that door at 3:43 time. there is gap in floor of room above, my script show it. I don't think it will give big advantage. Probably you can't do that until that thing explode.