Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Хочу лишь подчеркнуть, что если ты просто будешь передавать клавиши из соседнего процесса симуляцией нажатий, то не факт что это даст детерминированный эффект. Что значит детерминированный? Ну это значит воспроизводимый. Так что надо или реплеи встроенные менять, или всё же встраиваться в приложение чтобы подсовывать кнопки в нужный момент.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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
(97)
Joined: 12/12/2013
Posts: 376
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.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Glitches are nice, pace is fast, that's why yes vote. It was entertainming.
It doesn't seem well optimized because of moments like at time 2:03, and 13:22-13:35. In first - moving up for a moment then down. It's either mistake or rng manipulation, but I don't think it's rng. Second time just some additional walk... Also looks like you could use sword sooner.
Only after watching I did notice "Rerecords: 1923" - another sign of that.
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
Well, I wrote a program, actually few, to use my strategy above.
And, here is what I got:
First, I tried to make this program without taking nice moves, and as expected I got a bit above 632 rough estimate. But it was due to bug. Then I add binary search in case when only one poisoned is remaining, and got 541: and was like o_O. I made some debug output, and it turned out that 541 was from 99 positives, and for some reason it said in this case you need 7 steps. And, it actually true, because we have 99 positives, and we decide from 99, so power of two is 7 not 9 as I've mentioned above. But, obviously I had a bug. And bug was with range of possible positives, so not all positives was considered. After it was fixed I got 633 and was like - why it's dumb and can't find 632 steps described above. And, it turns out that description above has mistake. :D Correct calculation is following: 333 (groups) + 301(summary size of groups) - 1 (we don't check last one) = 633. So, even with binary search, it wasn't able to find better than 633 steps "dumb approach". So, I had to add advanced knowledge that we already used a bit. It's when there are all negative in positive group, then remaining one is poisined. It's very tricky to apply correctly, because in some cases there are more 'empty' groups, in some cases there are less of those. So, idea is to find out number of minimum emtpy groups using pigeonhole principle or something similar. For example, if there are 99 positives, then there is possible that all of groups not empty. And, number of positives is always less than number of poisoned, so this information not enough to derive minimum number of 'empty' groups. So, I had to also consider how many poisoned drinks we got after tests one by one. And, knowing this information, if we have found 88 drinks among 99 positives, it means that at least 11 groups is empty, so at least 11 additional drinks are found! After this addition, I got result 568! So, in worst case you can solve it in 568 steps using this approach if my calculations and my program is right :D
Now, a bit about worst case. Surprisingly, worst case turns out to be 85 positives. My program says that you need 333 tests to test groups, then 85 largest groups one by one except one in each group = 4+3*(85-1) - 85 = 171. And, it says worst case is when we found 85 poisoned drinks during 171 tests, so none of them are empty. And we have to find 15 poisoned drinks among 85 remaining drinks under suspicion. And, in worst case it says we need 64 steps for that.
I thought worst case would be 75 positives, but my program tells it needs 558 steps, other interesting thing is that for 75 and less positives, worst found drinks is range with 75 in it, so 75 is also worst. And with decreasing number of positives this range is increasing.
I need to mention, that I was always considering as worst case is when positive groups are largest in size. I think following proof works: if we know how to find out poisoned drinks in K steps for largest sizes, then we can always add 'dummy' - non poisoned drinks and do all our operations with them even though we know they are not poisoned. Thus, we have groups of largest possible sizes, and we know how to solve them in K steps. So, always consider largest groups in summary size.
Okay, it was results of using strategy mentioned in previous post with some kind of pigeonhole principle applied. Now, thoughts regarding optimality.
I though about entropy approach, and depending on positive and negative groups any consequent group size is varies. But lets for a moment forget about this fact. Lets assume we know list of sizes. We know that all negative (no poisoned drinks in group) - whole group is decided. So, in the end we only need positive groups. Also, lets assume we don't use intersecting groups. And here is what I think: now we know only total number of poisoned drinks we have, but no information about number of poisoned drinks within groups. It means, in worst case any next group that pick drinks from several groups may have positive result and gives no information. It's not strict statement. It's just intuition, it's not proof and very likely is wrong. But I think so because we get more information (intuitively) if we split this set of picked drinks by groups that was already picked, we get more information. For example, if we try set 3,4,5,6 and we already tried set 1,2,3,4 and also 5,6,7,8, so better would be split our set into two: 3,4 and 5,6. So, if we try 3,4 and it's positive, we know that 3,4,5,6 positive, and also know that 3,4 is positive. but if 3,4 is negative, we know 3,4 is negative, and if we want to know about 5,6, we just also check 5,6. So, two checks to know about two sets. But if we use 3,4,5,6 we will need three checks in worst case. It's just intuition, not a proof. Also, we don't know how many poisoned drinks within the group. And best way to find out is to check all of them. So, if we belive in this, then we have to find out how many poisoned among all groups, and we need again check all of them one by one. This leads to question: how large is total size of all positive groups using entropy method? I don't know. it's hard task. Actually, better to know what maximum total size of all groups for each possible number of positive groups. Then, I can try my approach with it, and probably it could be better. But we know that this size is not greater than (positives*3)+1.
Other thing: for n > 1 to find (n-1) poisoned drinks from n you need n-1 steps. Even though entropy is same as to find 1 among n. You can't do better. because the only one set for test can reveal answer: pick non poisoned one. I think similarly you can prove for n > 2 that you need n-1 steps to find (n-2) poisoned drinks among n drinks. Also, optimal way to find out how many poisoned drinks among n require n steps.
Other idea is following, if I always pick largest positive groups among picked groups size, then imagine we don't care about probability, and just trying to minimize for each possible number of positive groups total size of largest of them. I didn't think in this way much, so I can't say anything about it yet.
Ah, I didn't mention, that to find 2 poisoned drinks among n there is better strategy similar to binary search, but I was lazy to add it. Idea is to try to find two non-intersecting largest groups that are both positive. And then, do binary search within them. Also, it may be better for larger number of poison drinks as well.
Also, little note: my program can't find better than 999 steps solutions for number of poisoned drinks from 333 and above. first less than 999 steps is 998 steps for 332 poisoned drinks :)
Experienced Forum User, Published Author, Player
(97)
Joined: 12/12/2013
Posts: 376
Location: Russia
HHS wrote:
If we want to minimize the worst case, the best I could come up with was doing groups of 3, and then doing them one by one, for 631 measurements in total. (Special case: if you end up with 100 positives in the first step, you'll at most need to make 200 additional measurements.)
For groups of 3 there is following thing: lets assume we have 100 positives. Then, we know that in each group should be exactly one poisoned drink. So, if we test one by one within group, then as soon as we find poisoned one move onto next group. So worst case: we try two of drinks and none of them is poisoned, and we know for sure that last one is poisoned. Therefore in this case 2 tests is enough for group. So after we have 100 positives, we can solve with 200 tests. Tricky part is how we find 100 positives. If we have already 99 positives, there is chance that we have 99 positives, or 100 positives, so we need to dicide it. In good case we have 99 positives and many groups left: then we can do binary search! But in worst case we have 99 positives when we have left exactly one group that may have poisoned or not. So we need to test all groups in worst case. Assuming that there are 332 groups of 3 and 1 group of 4, then we need 333 tests to find out number of positives. In case with 100 positives we can solve in 333+200 = 533 tests in total. And, it's not worst case. The worst case is when positives are 99. This means that one of group has two poisoned dinks, and we don't know which. For each group there is a chance we have two in it. If after two tests within group we have no positives, it means last one is positive - only two tests. But there is case a bit worse: if we have second test positive, we don't know do we have two or one positive. So strategy is to check third one. In worst scenario we have all groups no yes no answers to poison test, and in the last one we don't need to do last test because we know that last group has two positives. And last group has 4 drinks, so in total, in this case we can solve in 333 + 300 - 1 = 632 tests. Now, things go even more complicated. We know that we should do 2 test at least for each group, then why not do them in the first place, and dicide stuff later? For last group we will do three tests. After 201 tests we have three kinds of groups: 0,1,2 poisoned drink found. For groups with 0 we know poisioned drink. If we have group with 2 poisoned drink found - no additional tests is need. So, we have left with only groups with 1 poisoned drink found. And our goal to find where is last one of two. We can do it with binary search. So we can solve using this strategy this case in 333 + 201 + 9
= 543 steps, where 9 is smallest power of two greater than 333. This leads to question: is it worst case? What if we have 98 positives? this may lead to 2 groups of two! How to deal with it?
You can do similarly with groups of 4.
In short: things are complicated. I don't know optimal solution.
HHS wrote:
How close can we get to the theoretical minimum of 469?