I had fun with this problem:
Andrew and Bob play the following game: given a finite set of positive integers A (fixed, which both know), Andrew chooses a number a that belongs to A, but tells nobody the value. Then, Bob can choose a positive integer b (member or not of A). Andrew must tell the number of positive divisors of the multiplication ab. Prove that Bob can choose b in such a way that he can figure out the number a, chosen by Andrew.
Andrew and Bob play the following game: given a finite set of positive integers A (fixed, which both know), Andrew chooses a number a that belongs to A, but tells nobody the value. Then, Bob can choose a positive integer b (member or not of A). Andrew must tell the number of positive divisors of the multiplication ab. Prove that Bob can choose b in such a way that he can figure out the number a, chosen by Andrew.
Let p1, p2, ... , pk be all the primes that divide at least one element of A.
@ For convenience, <n1, n2, ..., nk> denotes p1n1*p2n2*...*pknk.
@ Every element of A is of the form <n1, n2, ..., nk>.
@ The number of factors of <n1, n2, ..., nk> is (n1+1)*(n2+1)*...*(nk+1).
@ Given a set A, we wish to find b such that, over all w in A, bw has a distinct number of factors.
The statement, which we will make a little stronger, is that there exists a number b, which does not have prime factors other than p1, p2, ... , pk, such that, over all w in A, bw has a distinct number of factors.
We use induction on k.
If k=1, then A consists of distinct powers of p1. Since the number of factors of p1n is n+1 for all n≥0, then all elements of A have a distinct number of factors, so b=1 suffices.
Now suppose k>1 and assume the statement is true for all integers less than k.
Let A' be the set of all numbers <n1, ... , nk-1, 0> formed from the elements <n1, n2, ..., nk> in A, removing duplicates. By induction, there exists a number b'=<b1, b2, ...,bk-1, 0> such that multiplying each number <n1, ... , nk-1, 0> in A' by b' gives distinct numbers log(b1+n1+1)+log(b2+n2+1)+...+log(bk-1+nk-1+1) (this is the logarithm of the number of factors). Let d be the smallest absolute difference between two such possible numbers.
Let m be the smallest number such that log(m+y+1)-log(m+x+1)<d where y and x are the largest and smallest powers (respectively) of pk over all elements of A; such m exists because log is increasing and its derivative 1/x is always positive for x>0 and goes to 0 as x goes to infinity. Then let b=<b1, b2, ...,bk-1, m>. Then the logarithm of the number of factors log(b1+n1+1)+log(b2+n2+1)+...+log(bk-1+nk-1+1)+log(m+nk+1) is distinct over all <n1, n2, ..., nk> in A. So b is the number that we choose, completing the proof.
Edit: Fixed statement used in induction proof.
The number b is going to be something along the lines of b=a11a22a33... For the case where all the a in A are prime, this would be sufficient, as follows:
d(b) = 2x3x...x(N+1) = (N+1)! where N is the number of elements in A.
d(anb) = 2x3x...x(n-1)x(n+1)x(n+1)x(n+2)...x(N+1)
d(anb)/d(b) = (n+1)/n, which is different for every n and therefore d(ab) allows you to work out a.
I imagine a similar technique would allow you to generalise but I can't think how exactly.
(Note: I don't know how messy this might get, and will look into this tomorrow myself if there are no answers then. If it's too messy, ignore it).
I noticed a problem when playing L.A. Noire: Cole Phelps needs to interrogate a bus driver on duty whose route he inquires at the bus depot. Driving along the path in his car his partner remarks (all paraphrased) "This is taking forever." to which Phelps replies: "Chances are we're going to catch him half-way". Is this true?
You can complicate this question a lot, so for simplification state the problem like this: Given a closed non-self-intersecting path C of length L > 0 in the two-dimensional reals, a fixed point d (the bus depot, Phelps's car's starting point), a point p = d moving at speed |v_p| <= l_p representing Phelps's car and a point b /= p representing the bus moving at speed |v_b| <= l_b and /= 0 (all points on the path; a (positive) negative value for the speed denotes (counter-) clockwise direction, both speeds are constant and bounded).
What is the probability P(v_p, b, v_b) that Phelps encounters the bus b (that is p meets b) after having travelled at most L/2 distance from d? (oh, and assume they're never travelling in the same direction at the same speed if it helps)
Edit: Added bounds on speeds.
All syllogisms have three parts, therefore this is not a syllogism.
(Note: I don't know how messy this might get, and will look into this tomorrow myself if there are no answers then. If it's too messy, ignore it).
I noticed a problem when playing L.A. Noire: Cole Phelps needs to interrogate a bus driver on duty whose route he inquires at the bus depot. Driving along the path in his car his partner remarks (all paraphrased) "This is taking forever." to which Phelps replies: "Chances are we're going to catch him half-way". Is this true?
You can complicate this question a lot, so for simplification state the problem like this: Given a closed non-self-intersecting path C of length L > 0 in the two-dimensional reals, a fixed point d (the bus depot, Phelps's car's starting point), a point p = d moving at speed |v_p| <= l_p representing Phelps's car and a point b /= p representing the bus moving at speed |v_b| <= l_b and /= 0 (all points on the path; a (positive) negative value for the speed denotes (counter-) clockwise direction, both speeds are constant and bounded).
What is the probability P(v_p, b, v_b) that Phelps encounters the bus b (that is p meets b) after having travelled at most L/2 distance from d? (oh, and assume they're never travelling in the same direction at the same speed if it helps)
Edit: Added bounds on speeds.
I'll admit that I'm not keeping up with the symbols you're using or how you're modeling the problem, but if I'm not mistaken, if the bus is on a continuous cycle and last left the depot at a completely indeterminate time, wouldn't Phelps and the bus meet up, on average, in one-quarter the time it takes to complete the route? If they're traveling in opposite directions at roughly the same rate, they can be assured of meeting up at no later than half the time it takes to complete the route (corresponding to both Phelps and the bus leaving the depot at the same time). If the bus is just pulling into the depot, they meet instantaneously. The bus could be anywhere in its cycle and the distribution should be uniform, so the average length of time it takes for the two to meet up is one-quarter the length of the cycle (e.g., if it takes an hour to complete the route, they'll meet up in 15 minutes on average).
Here's a "come up with the most elegant proof" problem.
I noticed by application of the law of cosines and the law cos2(t) + sin2(t) = 1 that cos(2t) = 2cos2(t) - 1. If we substitute in x = cos(t) and x' = cos(2t), then this takes the very compact and elegant form
x' = 2x2 - 1.
Now pretend you don't know any trigonometry but still want to prove this fact. At first I tried drawing the two relevant triangles on the unit circle (I'll provide a figure if requested), but I could find no simple geometric relationship between x and x'. I think that this strategy may not be fruitful because x is a length and x' is written in terms of x2, which we traditionally associate with an area. I was finally able to prove the identity by algebraically defining both the unit circle and a circle centered at (x, y) which intersects points (1, 0) and (x', y'). You're free to do so yourself, but there's a decent amount of algebra involved, including the definitions of those two circles, two applications of the Pythagorean theorem, and culminating in the quadratic formula, which fortunately simplifies nicely.
I tend to believe that elegant identities conceal elegant proofs. Is there a simple proof without the use of trigonometry that x' = 2x2 - 1, where x' is associated with twice the angle of x? Bonus points if you can prove it geometrically with minimal algebra.
cos(2t) = 2cos2(t) - 1
...
Is there a simple proof without the use of trigonometry
Here is one I came up with that uses only geometry and the definition of cos x. The diagram shows that cos(2x) = 2 cos2(x) - 1
It helps to remember the geometric proof of cos(a+b)=cos(a)cos(b)-sin(a)sin(b).
RGamma wrote:
I noticed a problem when playing L.A. Noire: Cole Phelps needs to interrogate a bus driver on duty whose route he inquires at the bus depot. Driving along the path in his car his partner remarks (all paraphrased) "This is taking forever." to which Phelps replies: "Chances are we're going to catch him half-way". Is this true?
You can complicate this question a lot, so for simplification state the problem like this: Given a closed non-self-intersecting path C of length L > 0 in the two-dimensional reals, a fixed point d (the bus depot, Phelps's car's starting point), a point p = d moving at speed |v_p| <= l_p representing Phelps's car and a point b /= p representing the bus moving at speed |v_b| <= l_b and /= 0 (all points on the path; a (positive) negative value for the speed denotes (counter-) clockwise direction, both speeds are constant and bounded).
My image of the problem is somewhat different. Typically a bus travelling along a bus route runs on a road from point A to another point B, and then from point B back to point A along the same road. (There are of course variations on bus routes so this is not always true in real life, but this is the model that first comes to mind.) I also assume that the road is not self-intersecting, and that the bus depot is at one of the endpoints (say, point A). Upon learning the bus driver's route while at point A, and setting off from point A towards point B, we may assume the bus is anywhere on the route in either direction with uniform probability, and we want to find the average distance travelled by Phelps before meeting the bus along the road, whichever direction the bus is driving.
I use v to denote the speed of Phelps's car, v0 to denote the speed of the bus, and d to denote the driving distance from point A to point B. Graph the function of
- distance travelled by Phelps in order to meet the bus
vs.
- position of the bus at the moment Phelps leaves point A towards point B, in terms of the distance the bus had travelled since last leaving point A.
If v>v0, then the graph is as follows:
The average distance travelled is clearly d/2, that is, halfway.
If v<v0, then the graph is as follows:
Here, the average distance travelled is vd/(v+v0), which for v<v0 is less than d/2.
So, according to this model, the comment about meeting halfway is true only if the speed of Phelps's car is equal to or faster than the speed of the bus.
cos(2t) = 2cos2(t) - 1
...
Is there a simple proof without the use of trigonometry
Here is one I came up with that uses only geometry and the definition of cos x. The diagram shows that cos(2x) = 2 cos2(x) - 1
It helps to remember the geometric proof of cos(a+b)=cos(a)cos(b)-sin(a)sin(b).
A wonderful proof without words! There's hardly even much geometry in it! Thanks, FractalFusion!
What is the smallest natural number n such that n has some power whose the last trillion decimal digits are all ones?
i.e., nk ends in 111....111 (a trillion 1's) ( ͡° ͜ʖ ͡°)
If k doesn't have to be natural, then wouldn't n be 2? (Edit: Which would make k = log (111...111) / log (2))
I am still the wizard that did it.
"On my business card, I am a corporate president. In my mind, I am a game developer. But in my heart, I am a gamer." -- Satoru Iwata
<scrimpy> at least I now know where every map, energy and save room in this game is
I just want to add that I solved the problem so well that the problem had to be changed. :D
I am still the wizard that did it.
"On my business card, I am a corporate president. In my mind, I am a game developer. But in my heart, I am a gamer." -- Satoru Iwata
<scrimpy> at least I now know where every map, energy and save room in this game is
standup maths posted a math challenge: https://www.youtube.com/watch?v=Gh8h8MJFFdI
In short: 36 is a square number (because it's 6*6) and a triangular number (because it's 8*(8+1)/2). The question is: Are there other numbers that are also square and triangular at the same time? In other words, there exist some integers n and m for which n2=m*(m+1)/2. And if they are, what is the pattern?
Not much of a spoiler, but 36 is not the only such number, and there exist others. However, the second part of the question is more difficult.
The second part is solving a quadratic Diophantine equation. There is an algorithm to do so, you just have to know it.
The solution is of the form:
m = 1/4 ((3-2 sqrt(2))^k+(3+2 sqrt(2))^k-2),
n = ((3-2 sqrt(2))^k-(3+2 sqrt(2))^k))/(4 sqrt(2)),
k element Z, k >= 2
For positive m, n.
The first few solutions are:
m = 8, n = 6
m = 49, n = 35
m = 288, n = 204
m = 1681, n = 1189
m = 9800, n = 6930
Build a man a fire, warm him for a day,
Set a man on fire, warm him for the rest of his life.
In short: 36 is a square number (because it's 6*6) and a triangular number (because it's 8*(8+1)/2). The question is: Are there other numbers that are also square and triangular at the same time? In other words, there exist some integers n and m for which n2=m*(m+1)/2. And if they are, what is the pattern?
We can rewrite n2=m(m+1)/2 as follows:
n2=m(m+1)/2
2n2=m2+m
8n2+1=4m2+4m+1
8n2+1=(2m+1)2
(2m+1)2-2(2n)2=1
a2-2b2=1 where a=2m+1, b=2n
This is a Pell equation. It is well-known that the solutions are given by an+bn*sqrt(2)=(a1+b1*sqrt(2))n=(3+2*sqrt(2))n
which can also be represented by the recursive formula:
an+1=3an+4bn
bn+1=2an+3bn
The first few solutions for a,b are
1, 0 (m=0, n=0)
3, 2 (m=1, n=1)
17, 12 (m=8, n=6)
99, 70 (m=49, n=35)
577, 408 (m=288, n=204)
3363, 2378 (m=1681, n=1189)
19601, 13860 (m=9800, n=6930)
and so on.
Amaraticando wrote:
What is the smallest natural number n such that n has some power whose the last trillion decimal digits are all ones?
The answer is n=71.
We want to find the smallest n such that there exists an integer k where the last trillion digits of nk are all ones. Some facts:
@ nk=1 (mod 10)
@ nk=11 (mod 20)
@ nk=11 (mod 50)
@ nk=11=3 (mod 4)
@ nk=1111=7 (mod 16)
Then:
@ n cannot be 0,2,4,5,6,8 (mod 10).
@ n cannot be 3,7,9 (mod 10); otherwise k is even and nk is a perfect square. But nk=3 (mod 4), which cannot be a perfect square.
@ n cannot be 1 (mod 20) since nk=11 (mod 20)
@ n cannot be 1 (mod 50) since nk=11 (mod 50)
@ n cannot be 11 since the residues of 110, 111, 112, ... (mod 16) are 1, 11, 9, 3, 1, ... , but nk=7 (mod 16)
@ n cannot be 31 since the residues of 310, 311, 312, ... (mod 16) are 1, 15, 1, ... but nk=7 (mod 16)
So the least possible candidate is n=71. We show that this is the solution.
We prove by induction:
1) For each m≥4, there exists a k for which 71k ends in 11...1 (m 1's)
2) For each m≥5, there exists a k for which 71k ends in 300...01 (m-2 0's)
Base step:
1) 7113=1111 (mod 10000)
2) 71250=30001 (mod 100000)
Induction:
Suppose that statement 1 is true for m and statement 2 is true for m+1. Let i be a value for which 71i ends in x11...1 (m 1's) where x is a digit, and let j be a value for which 71j ends in y300...01 (m-1 0's), where y is a digit. Let z be 7*(11-x) mod 10. Then 71i+z*j ends in w11...1 (m 1's) where w= (x+3*z) mod 10 = (x+3*7*(11-x)) mod 10 = (x+11-x) mod 10 = 1. So statement 1 is true for m+1. Furthermore, 7110*j ends in 300...01 (m 0's), regardless of y. So statement 2 is true for m+2. This completes the induction.
Since statement 1 is true for m = one trillion, we have that n=71 is the solution to the problem.
Edit: Fixed some bad notation.
Is 65536 the only power of 2 that doesn't have, in its decimal representation, any digit that's a power of 2 (ie. 1, 2, 4 or 8)?
65536 is the only power of 2 up to 2^40000000000 that doesn't have digits 1,2,4,8. I wrote a program to find other candidates based on their last 51 digits (i.e. mod 10^51). The program returned
16^7525657339 (last 51 digits 69707999760379505 77776399363966007 57506995373735936), and
16^9881236075 (last 51 digits 66955906599977637 96566660539696359 56056903569637376),
but using logarithms shows that
16^7525657339≈3.244240*10^9061794384, and
16^9881236075≈1.770509*10^11898193811,
so they don't work. Note that a power of 2 that doesn't have digits 1,2,4,8 must be a power of 16.
Unfortunately, as to whether one can prove that 65536 is the only power of 2 that doesn't have digits 1,2,4,8, I don't think it is possible to do so. Given a positive integer n, there always exists a power of 2 for which the final n digits do not have 1,2,4,8, so mod 2^m or 5^m arguments don't work. There don't appear to be any other mod arguments either, and there don't appear to be arguments based on the first few digits or on special factorizations.
So for all we know there could be a power of 2 consisting solely of the digits 5 and 6; the chance of that is practically zero but there appears to be no way to prove that it is actually zero.
There are problems based on manipulating digits in base 10 or what a number looks like in base 10 that are very easy to pose and seem almost impossible to solve. For example, the 196 problem is one such problem. Very often the best that can be done is the use of heuristic arguments which treat sufficiently large numbers as numbers with random digits; if applied to this question, the probability that there is a power of 2 greater than 2^40000000000 that doesn't have digits 1,2,4,8 is, I think, (1/(1-0.6))*(0.6)^40000000000, or whatever number that is close to zero. This is of course invalid math logic, but there is nothing else to work with.
Joined: 11/14/2011
Posts: 68
Location: Brookline, MA
Here is a nifty problem about polytopes. I and another member of AOPS have analyzed it and came up with the answer. Here it is.
Let p0 and p1 be two parallel (n-1)-dimensional hyperplanes in Rn that are a unit distance apart. Let A be a unit (n-1)-hypercube in p0 and B be a regular (n-1)-orthoplex in p1 such that the orthogonal projections of B's vertices onto p0 are at the centers of the (n-1)-cells of A. Let C be the convex hull of (A U B). Find the formulas for following features of C:
(a) It's n-Volume Vn.
(b) It's Surface (n-1)-Volume Sn.
(c) It's circumradius Rn.
Given a positive integer n, there always exists a power of 2 for which the final n digits do not have 1,2,4,8, so mod 2^m or 5^m arguments don't work.
How do you know that?
It's based on a few facts. If g is a primitive root modulo p^2 where p is an odd prime, then g is a primitive root mod p^n for all n≥2. Since 2 is a primitive root mod 25, then 2 is a primitive root mod 5^m. So for every number b that is not a multiple of 5, there exists a k for which 2^k=b mod 5^m.
Scale this by multiplying by 2^m. So for every number c that is a multiple of 2^m but not 5, there exists a k for which 2^k=c mod 10^m.
So it is enough to construct an m-digit number consisting only of digits 0,3,5,6,7,9 that is a multiple of 2^m but not 5, as follows: The ones digit is of course 6. Now supposing that you have a k-digit number d (possibly with leading 0's) that is a multiple of 2^k, extend to a k+1-digit number by adding to the left an even digit if d is a multiple of 2^(k+1) or an odd digit if d is not. The resulting number is a multiple of 2^(k+1). Since there are both even digits (0,6) and odd digits (3,5,7,9) to choose from, it is possible to construct such a number using only these digits.
Note that that's why I mentioned "So for all we know there could be a power of 2 consisting solely of the digits 5 and 6".
It helps to remember the geometric proof of cos(a+b)=cos(a)cos(b)-sin(a)sin(b).
The average distance travelled is clearly d/2, that is, halfway.
If v<v0, then the graph is as follows:
Here, the average distance travelled is vd/(v+v0), which for v<v0 is less than d/2.
So, according to this model, the comment about meeting halfway is true only if the speed of Phelps's car is equal to or faster than the speed of the bus.
