Or answering using words:
First you get the sum of all the data points by opening up the average
4.4*n
then you add the new data point
+9.2
and finally you calculate the average again (don't forget the increased amount of data points)
/(n+1)
now the result should be 4.7
=4.7
((4.4*n)+9.2)/n+1) = 4.7
...[shenanigans]...
n = 15
n+1 = 16
Warning: Might glitch to creditsI will finish this ACE soon as possible
(or will I?)
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Firstly, being h=OE the height of the OBC triangle, and n=EC, we see that:
h² = 23² - (30-n)² = 16² - n²
Thus, (30-n)² - n² = 23² - 16² and n = 209/20
And h² + (209/20)² = 256. So h = (23/20)*sqrt(111)
Now, being g=AF the height of the triangle ABC, and m = FC.
Again, g² = 27² - (30-m)² = 22² - m².
(30-m)² - m² = 27² - 22², and m = 131/12.
Thus, g² + (131/12)² = 22², and g = sqrt(52535)/12.
Let's put this image in a Cartesian plane, being b = (0,0).
O = (30-n,h) and A = (30-m,g).
So, if d = OA, d² = [(30-n) - (30-m)]² + (g-h)².
d² = [(30-209/20) - (30-131/12)]² + (sqrt(52535)/12-(23/20)*sqrt[111])²
Solving this equation, d is *almost* 7:
d = sqrt([61421/30] - 23*sqrt(388759/15)/2)/2
which is approximately 7.0000000857...
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
This problem appeared in a Brazilian math olympiad, so it should be solvable without much math knowledge required:
Being n's prime factorization = (p1)^q1 * (p2)^q2 * (p3)^q3 (...) * (pk)^(qk).
And being f(x) = q1*p1^(q1-1) * q2*p2^(q2-1) * q3*p3^(q3-1) (...) * qk*pk^(qk-1).
Prove that there are infinite natural numbers n so that:
f(n) = f(n-1) + 1
Being n's prime factorization = (p1)^q1 + (p2)^q2 + (p3)^q3 (...) + (pk)^(qk).
And being f(x) = q1*p1^(q1-1) + q2*p2^(q2-1) + q3*p3^(q3-1) (...) + qk*pk^(qk-1).
Prove that there are infinite natural numbers n so that:
f(n) = f(n-1) + 1
Just to be clear.
Do you mean n = (p1)^q1 * (p2)^q2 * (p3)^q3 * ... * (pk)^qk ? That is normally how a prime factorization is written out.
If so, is it correct that f(n) = q1*p1^(q1-1) + q2*p2^(q2-1) + q3*p3^(q3-1) + ... + qk*pk^(qk-1) ?
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
FractalFusion wrote:
BrunoVisnadi wrote:
Being n's prime factorization = (p1)^q1 + (p2)^q2 + (p3)^q3 (...) + (pk)^(qk).
And being f(x) = q1*p1^(q1-1) + q2*p2^(q2-1) + q3*p3^(q3-1) (...) + qk*pk^(qk-1).
Prove that there are infinite natural numbers n so that:
f(n) = f(n-1) + 1
Just to be clear.
Do you mean n = (p1)^q1 * (p2)^q2 * (p3)^q3 * ... * (pk)^qk ? That is normally how a prime factorization is written out.
If so, is it correct that f(n) = q1*p1^(q1-1) + q2*p2^(q2-1) + q3*p3^(q3-1) + ... + qk*pk^(qk-1) ?
Of course! Sorry, I wrote that completely wrong! The '+' symbols in both n prime factorization and f(x) should replaced by '*' symbols. Thanks for pointing that out, I'll edit my post.
Being n's prime factorization = (p1)^q1 * (p2)^q2 * (p3)^q3 (...) * (pk)^(qk).
And being f(x) = q1*p1^(q1-1) * q2*p2^(q2-1) * q3*p3^(q3-1) (...) * qk*pk^(qk-1).
Prove that there are infinite natural numbers n so that:
f(n) = f(n-1) + 1
This problem is difficult. I have a method to do it but the latter part feels like something from an advanced number theory textbook. I looked for an ingenious trick (it is an Olympiad question after all) but I couldn't find one. The proof I have is as follows:
Note: A square-free integer is one which is a product of distinct primes; that is, every prime divisor occurs to degree 1 in the prime factorization.
We have the following facts:
@ f(x*y)=f(x)*f(y) if gcd(x,y)=1.
@ f(p)=1 if p is prime.
@ f(13^2)=26.
@ f(3^3)=27.
Therefore:
@ f(N)=1 if N is square-free.
@ f(A*13^2)=26 if A is square-free and 13 does not divide A.
@ f(B*3^3)=27 if B is square-free and 3 does not divide B.
We want to prove that there are infinitely many A,B which satisfy the above and such that A*13^2+1=B*3^3 (or in other words 169A+1=27B).
Consider solutions (A,B) to 169A+1=27B. One solution is (A,B)=(23,144). Then for every integer M, (27M+23,169M+144) is a solution.
So we want to prove that there are infinitely many M>=0 which satisfy the following (condition (#)):
@ 27M+23 is square-free and 13 does not divide it, and
@ 169M+144 is square-free and 3 does not divide it.
We may reword condition (#) as:
1) 2^2=4 divides neither 27M+23 nor 169M+144.
2) 3 does not divide 169M+144.
3) 5^2=25 divides neither 27M+23 nor 169M+144.
4) 13 does not divide 27M+23.
5) k^2 divides neither 27M+23 nor 169M+144 for all odd k>=7.
Let N>10^6 be a number divisible by 2*3*5*13. Let S(N) be the number of M between 0 and N-1 that satisfy condition (#). We want to show that, as N grows without bound, then so does S(N). Then
S(N)>= N*(2/4)*(2/3)*(23/25)*(12/13) - R(N)
where R(N) is the sum of all 2*ceiling(N/k^2) over all odd k between 7 and sqrt(169N+144). Note that gcd(27M+23,169M+144)=1. The (2/4)*(2/3)*(23/25)*(12/13) comes from the conditions 1 to 4 and the R(N) from condition 5. Now:
R(N) <= N*( sum{i=3 to infinity} 2/(2i+1)^2 ) + 2*sqrt(169N+144)/2
Note that sum{i=3 to infinity} 2/(2i+1)^2 is less than the integral from x=2 to infinity of 2/(2x+1)^2 dx, which is 1/5=0.2 . Furthermore, since N>10^6, sqrt(169N+144)<sqrt(400N)=20*sqrt(N)<20*(N/10^3)=0.02N . Therefore R(N)<0.22N, and so
S(N) >= 0.28N - R(N) > 0.28N - 0.22N = 0.06N .
So then as N goes to infinity, so does S(N). QED
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Thanks for your answer!
Yeah, this Olympiad does require pretty specific knowledge sometimes, unfortunately.
I could understand most of your solution, and I'm happy because what I wrote in the Olympiad was pretty similar with the beginning of your solution, so I might gain some partial points. I got to f(27) = 27, f(169) = 26, f(a*27) = 27 and f(b*169) = 26, being a a square free not divisible per 3 and b a square free not divisible per 13, so that 27a = 169b + 1. But at that moment I couldn't get any beyond that.
I can kinda understand the principle of your solution, but I have some questions about it:
1) Why didn't you include 5^2 as one of the possibilities of odd k^2? Is there a reason to that?
2) I'm not used at all with math terms in English. I didn't even know what gcd means. Could you say what 'ceiling' means in ''2*ceiling(N/k^2)?
3) I know this is the part that requires some further knowledge, so I might not understand it, but could you explain a bit deeper how you got to ''R(N) <= N*( sum{i=3 to infinity} 2/(2i+1)^2 ) + 2*sqrt(169N+144)/2''?
lol, I was afraid Dirichlet's theorem was needed. I don't handle square-free techniques well, so I supposed there were infinite solutions n = 13²*p such that n + 1 = 2*3³*q , where p and q are both primes. This might be the case...
So, we can conclude that 54q - 169p =1, a diophantine equation that has solutions:
q = 169*x + 72 ; p = 54*x + 23
According to Dirichlet's theorem, there're infinitely many x's such that q are prime and p are prime. However, I can't know if both conditions are met simultaneously infinitely many times :( .
I will try to write FractalFusion's solution in a paper. BTW, there must be some clever solution, because the smallest n is 13013, kinda big to discover without a computer within 1.5 hours (3 problems/4.5 hours).
EDIT: typo.
The idea is, we need to prove that there are infinitely many (A,B) satisfying 169A+1=27B where A,B are square-free and 13 does not divide A and 3 does not divide B. Even though we don't specifically know in general if a number is square-free, we can determine that infinitely many such (A,B) exist because there are "not enough multiples of k^2 to cover everything". For example, the probability that a randomly selected "large" number is square-free is (3/4)(8/9)(24/25)... = product{p prime} (1-1/p^2) = 6/pi^2.
In the case of this problem, the probability that a "large" (A,B) satisfying 169A+1=27B also satisfies the other conditions is P = (2/4)(2/3)(23/25)(47/49)(119/121)(12/13) * product{p prime >= 17} (1-2/p^2). It suffices simply to show that P>0, although I think the value of P is closer to 0.26 or so. For a rigorous proof, it is better to state it as how I defined S(N) (number of M between 0 and N-1 for which A=27M+23 and B=169M+144 satisfies the conditions). It is sufficient to consider first the M for which these are satisfied (accounting for (2/4)(2/3)(23/25)(12/13)N, or about 0.28N of the numbers)
1) 2^2=4 divides neither 27M+23 nor 169M+144.
2) 3 does not divide 169M+144.
3) 5^2=25 divides neither 27M+23 nor 169M+144.
4) 13 does not divide 27M+23.
and then subtract these possible cases, regardless of overlap (which can be bounded by 0.22N)
5) k^2 divides neither 27M+23 nor 169M+144 for all odd k>=7.
ceiling(x) is the smallest integer greater than or equal to x. I guess there are different terms in other languages, but I learned it as "floor" (greatest integer less than or equal to x) and "ceiling".
R(N), which is an upper bound for number of M that do not satisfy condition 5, is the sum of all 2*ceiling(N/k^2) over all odd k between 7 and sqrt(169N+144). We know that ceiling(N/k^2) <= (N/k^2) + 1, so we can bound using
R(N) <= N*( sum{i=3 to infinity} 2/(2i+1)^2 ) + 2*sqrt(169N+144)/2
The reason why the starting k for R(N) is chosen to be 7 is because this is the first point where the bound for R(N) is smaller than the estimate for the other conditions (the bound for that summation of square reciprocals is smaller for a larger starting k). Of course, if we made the starting k for R(N) to be much higher, then we can get a more accurate estimate for S(N), but this method proves that S(N)>0.06N, which is good enough for this problem.
By the way, you don't even need to figure out any specific (A,B) for this method, even though (77,482) gives the n=13013 that Amaraticando stated.
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
I'll put here another problem from that olympiad. I think this one is a bit easier:
Is it true that there is a polynomial f(x) with rational coefficients, but at least one non integer, which degree is n>0, a polynomial g(x) with only integer coefficients, and a set S with n+1 integer elements so that g(t) = f(t) to every t that belongs to S?
I held off replying for a couple days because I thought it was easy enough that someone else would have replied. Perhaps there would have been a response if the fact that it was an Olympiad question was omitted.
Suppose that there is a polynomial f(x) with at least one non-integer coefficient, deg(f)=n, g(x) is an integer polynomial, and S is a set of n+1 integers such that f(t)=g(t) for all t in S. Let h(x)=g(x)-f(x). Note that h(x) is not the zero polynomial since f and g cannot be the same. Now h(t)=0 for all t in S, so h has at least n+1 integer roots and so deg(h)≥n+1. Since deg(f)=n, then deg(g)≥n+1. So h is a polynomial with at least one non-integer coefficient, such that the coefficients of xn+1, xn+2, ... , are all integers.
Let s1, s2, ..., sn+1 be elements of S. Then h=(x-s1)(x-s2)...(x-sn+1)k(x), where k(x) is a polynomial of degree m=deg(h)-(n+1). Now k must have at least one non-integer coefficient; otherwise h is an integer polynomial. Let k=amxm+am-1xm-1+...+a1x+a0, and let i be the largest integer (0≤i≤m) such that ai is not an integer. Then the (n+1+i)th coefficient of h is equal to:
{coefficient of xn+1+i} (x-s1)(x-s2)...(x-sn+1)(amxm+...+aixi+...+a1x+a0)
=
ai - ai+1*sum{j=1 to n+1}(sj) + ai+2*sum{1≤j(1)<j(2)≤n+1}(sj(1)*sj(2)) - ...
+ (-1)m-i*am*sum{1≤j(1)<...<j(m-i)≤n+1}(sj(1)*...*sj(m-i)),
which is ai plus an integer, which is not an integer. This contradicts that the coefficients in h of xn+1, xn+2, ... , are all integers.
Therefore the answer to
Is it true that there is a polynomial f(x) with rational coefficients, but at least one non integer, which degree is n>0, a polynomial g(x) with only integer coefficients, and a set S with n+1 integer elements so that g(t) = f(t) to every t that belongs to S?
is no.
By the way, the statement that f(x) has rational coefficients is a red herring; the answer is no even if f(x) is allowed to have any real coefficients, as long as it has at least one non-integer coefficient.
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Thanks for answering, again. I'll point out something about the other problem you solved:
I think there is a way to avoid using integrate do determinate Σ (2/(2x+1)^2), k from 3 to infinity. See if you think that's correct:
We know that Σ 1/x^2 is pi²/6. Thus, Σ 1/(2x)^2 = Σ 1/4x^2 = pi²/24.
It's easy to tell that Σ 1/(2x)}2 + Σ 1/(2x-1)^2 = Σ 1/x^2.
That means Σ 1/(2x-1)^2 = pi²/6 - pi²/24 = pi²/8
Since we only wanted values from 3 to infinity for Σ 1/(2x+1)^2, we will only want values from 4 to infinity for Σ 1/(2x-1)^2.
So we got R(N)/2 = pi²/8 - (1 + 1/9 + 1/25) , which is less than 0.085 .
So R(N) is less than 0.17.
Here I'm considering N as the whole natural numbers set. Since (1/2)(2/3)(12/3)(23/25)(8/9) = ~0.25, and 0.25-0.17 = 0.08, there must be 0.08N, and thus, infinite solutions for f(n) = f(n-1) + 1 in N.
Joined: 12/28/2007
Posts: 235
Location: Japan, Sapporo
BrunoVisnadi wrote:
We know that Σ 1/x^2 is pi²/6.
To prove this is not so easy as bounding its value. Its proof requires some Fourier calculus, or something related to tough computation of trigonometric functions, which is/are more complicated than FractalFusion's estimate. Except for that, your argument looks fine.
Retired because of that deletion event.
Projects (WIP RIP): VIP3 all-exits "almost capeless yoshiless", VIP2 all-exits, TSRP2 "normal run"
Hm, I didn't think of a proof without using calculus.
If you are allowed to use Σ 1/x^2 = pi²/6 without proof, then your argument works. But even if you aren't allowed to use that, you can still show that Σ {i=9 to infinity, i odd} 1/i^2 < 1/8, since by rounding each term of the sum up to the next power of 1/2:
1/9^2 + 1/11^2 + 1/13^2 + ...
<
4*1/8^2 + 8*1/16^2 + 16*1/32^2 + ... = 1/16 + 1/32 + 1/64 + ... = 1/8 = 0.125.
So R(N)<0.125*2=0.25.
Then filtering out the multiples of 1/2^2 twice, 1/3, 1/5^2 twice, 1/7^2 twice, 1/13 gives (1/2)(2/3)(23/25)(48/49)(12/13) = ~0.277, and 0.27-0.25=0.02. So S(N)>0.02N.
BrunoVisnadi wrote:
Here I'm considering N as the whole natural numbers set. Since (1/2)(2/3)(12/3)(23/25)(8/9) = ~0.25, and 0.25-0.17 = 0.08, there must be 0.08N, and thus, infinite solutions for f(n) = f(n-1) + 1 in N.
By the way, the (8/9) isn't necessary. In the equation 169A+1=27B, A can never be a multiple of 3, so you don't need to filter out a multiple of 1/3^2 in A. The only condition related to multiples of 3 is that B is not a multiple of 3, which (2/3) covers already. I also guess you meant (12/13) instead of (12/3).
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Ah, the (8/9) was actually because of the B not being a multiple of 9 condition, but now I realize that since 27 is multiple of 9, 27N + 23 will never be a multiple of 9 for every N.
I was thinking about another way to prove that S(N) grows without bound as N does. I don't know if this is easier or not. (I will state it more carefully as well.)
Let's see the condition again (this time, I merged the 5^2 into odd k^2 case).
1) 2^2=4 divides neither 27M+23 nor 169M+144.
2) 3 does not divide 169M+144. (3^2 never divides 27M+23)
3) 13 does not divide 27M+23. (13^2 never divides 169M+144)
4) k^2 divides neither 27M+23 nor 169M+144 for all primes k>=5, k not 13.
S(N) is the number of M between 0 and N-1 for which 1-4 are satisfied. Assume that N is sufficiently large and a multiple of (2^2)*3*13.
Now, I didn't explicitly state before, but the congruences of M with the congruences of 27M+23 and 169M+144 are linked. If b and n are relatively prime then the equation bM + c = 0 (mod n) has the class of solutions M = (b^(-1))c (mod n). So approximately N/n of the numbers have bM + c divisible by n (exact when N is divisible by n). When N is not divisible by n, then it is at least floor(N/n) and at most ceiling(N/n).
Also, for a given M, 27M+23 and 169M+144 are relatively prime (since they are a solution (A,B) to 169A+1=27B), so it is impossible for a number greater than 1 to divide both of them at the same time.
Let T be the set of M between 0 and N-1 that satisfy condition 1. Then |T| = 2N/4 = N/2. (There are two congruences mod 4 that M cannot be in).
Now the number of T that do not satisfy condition 2 is N/3 - 2N/12 = N/6. (Of the congruence mod 3 that M is in, there are two congruences mod 12 that M cannot be in.)
The number of T that do not satisfy condition 3 is N/13 - 2N/52 = N/26. (Of the congruence mod 13 that M is in, there are two congruences mod 52 that M cannot be in.)
For each prime k>=5 (other than 13), the number of T for which k^2 divides 27M+23 or 169M+144 is at most 2*ceiling(N/k^2) - 4*floor(N/(2k)^2) < 2N/k^2 + 2 - 4N/(2k)^2 + 4 = N/k^2 + 6. (Of the two congruences mod k^2 that M is in, there are four congruences mod (2k)^2 that M cannot be in.)
So by summing over all odd 5<=k<=sqrt(169N+144), the number of T that do not satisfy condition 4 is at most (N/5^2 + N/7^2 + ... ) + 6*sqrt(169N+144) < N/4 + o(N). (The upper range is sqrt(169N+144) since if k>sqrt(169N+144), then k^2 is larger than both 27M+23 and 169M+144 for all M between 0 and N-1. 1/5^2 + 1/7^2 + ... < 1/4 using the same argument as in my previous post, but with calculus, you can get < 1/6. o(N) refers to little o notation.)
So then S(N) > N/2 - N/6 - N/26 - N/4 - o(N) = 7N/156 - o(N) ~ 7N/156 as N goes to infinity.
Saw this abstract linear algebra question on a test today and wanted to share it (posting it off of memory so somethings may be off):
Let A,B,M be nxn matricies which have real entries where n is a natural number, where AM=MA and A and B share the same characteristic polynomial.
Prove det(A- MX) = det(B - XM) if X is an nxn matrix with real entries.
Let A,B,M be nxn matricies which have real entries where n is a natural number, where AM=MA and A and B share the same characteristic polynomial.
Prove det(A- MX) = det(B - XM) if X is an nxn matrix with real entries.
Is the problem correct? I'm coming up with
M=A=
1 0
0 0
B=
0 0
0 1
X=
1 0
0 1
and AM=MA and A and B have the same characteristic polynomial, and this gives me det(A- MX) = 0 ≠ -1 = det(B - XM).
Pi is defined as the ratio between the circumference and the diameter of a circle.
This ratio is constant, regardless of the diameter. Everybody kind of takes this for granted, just because they say it is. But this got me thinking how exactly could one prove that the ratio is constant? This doesn't seem to be trivial to prove. It doesn't even seem trivial to see intuitively.
Let A,B,M be nxn matricies which have real entries where n is a natural number, where AM=MA and A and B share the same characteristic polynomial.
Prove det(A- MX) = det(B - XM) if X is an nxn matrix with real entries.
Is the problem correct? I'm coming up with
M=A=
1 0
0 0
B=
0 0
0 1
X=
1 0
0 1
and AM=MA and A and B have the same characteristic polynomial, and this gives me det(A- MX) = 0 ≠ -1 = det(B - XM).
Ah, the given was AM = MB instead of AM = MA, mistyped
Pi is defined as the ratio between the circumference and the diameter of a circle.
This ratio is constant, regardless of the diameter. Everybody kind of takes this for granted, just because they say it is. But this got me thinking how exactly could one prove that the ratio is constant? This doesn't seem to be trivial to prove. It doesn't even seem trivial to see intuitively.
Saw this abstract linear algebra question on a test today and wanted to share it (posting it off of memory so somethings may be off):
Let A,B,M be nxn matricies which have real entries where n is a natural number, where AM=MB [corrected] and A and B share the same characteristic polynomial.
Prove det(A- MX) = det(B - XM) if X is an nxn matrix with real entries.
It's not specified whether this is true for any X or if there merely exists an X. I'll assume you mean there exists an X because that's the proof I'm coming up with.
My proof relies on M being invertible, which wasn't specified. I suppose you might be able to re-work it in such a way that it doesn't require inverting M. I kind of doubt it, though, since M-1 shows up explicitly in my solution.
A and B are similar because B = M-1AM. So that's neat.
Also, we know det(A-λI) = det(B-λI). That's more useful. Let's start there.
det(A-λI) = det(B-λI)
Replace I on the left with MM-1. Replace I on the right with M-1M:
det(A-λMM-1) = det(B-λM-1M)
Now just commute λ on the left hand side because it is a scalar.
det(A-MλM-1) = det(B-λM-1M)
Finally, identify X as λM-1. Now we have
det(A-MX) = det(B-XM)
QED.
EDIT: now that it's solved, the image is from here https://en.wikipedia.org/wiki/Almost_integer
