1 2
15 16 17
132 133
Posted: 1/30/2008 11:26 PM
Quote
Twelvepack
Joined: 5/2/2006
Posts: 1020
Location: Boulder, CO
I just realized that the best strategy for 500 pirates is for the first to propose to give himself all 100 coins. The first 298 pirates will die if they are willing to vote someone overboard simply because they are getting no coins, so for fear of death, 297 of the first 298 pirates will vote yes to this first offer. The second pirate will vote no to it only because he could make this same valid offer should the first die. As long as the first 298 cooperate, which they will (because not cooperating will result in everyone of them dieing) then the first gets all of the coins. an argument could be made that they would hold off until the 404th pirate offers 100 to himself, because this is the last point that cooperating would save their lives. I suppose that it depends on how you read the problem.
Has never colored a dinosaur.
Posted: 1/31/2008 12:51 PM
Quote
Gorash
Joined: 4/16/2005
Posts: 251
Right direction Twelvepack, but not all there is to it. And yes, it depends a little on how you read the problem.
Posted: 2/1/2008 11:24 PM
Quote
Dacicus
Editor, Player (67)
Joined: 6/22/2005
Posts: 1041
Here's a relatively simple, but potentially long, problem: Let the first 10 terms of the sequence a_n be 1, 6, 17, 36, 65, 106, 161, 232, 321, and 430 (n = 1, 2, ... , 10). Find an explicit formula for a_n in terms of n without a calculator, spreadsheet, or anything else that does the curve fitting for you. Also, prove that every term of a_n is an integer.
Current Projects: TAS: Wizards & Warriors III.
Posted: 2/2/2008 2:31 AM
Quote
snorlax
He/Him
Joined: 5/20/2007
Posts: 174
Location: Wisconsin
The differences in the consecutive terms are 5, 11, 19, 29, 41, 55, .... The differences in the differences is 6, 8, 10, 12, 14, the type of pattern which usually applies to differences between two squares. This leads me to believe that the formula for a_n is an expression of the third power. Let our expression be ax^3 + bx^2 + cx + d. Then we can use four equations: a + b + c + d = 1 8a + 4b + 2c + d = 6 27a + 9b + 3c + d = 17 64a + 16b + 4c + d = 36 Using a matrix for simplification to solve: 1 1 1 1 1 0 -4 -6 -7 -2 0 -18 -24 -26 -10 0 -48 -60 -63 -28 1 1 1 1 1 0 -4 -6 -7 -2 0 0 6 11 -2 0 0 12 21 -4 1 1 1 1 1 0 -4 -6 -7 -2 0 0 6 11 -2 0 0 0 -1 0 d = 0, c = -1/3, b = 1, a = 1/3. so a_n = (1/3)n^3 + n^2 - (1/3)n Testing the 5th term, this gives us (1/3)5^3 + 5^2 -(1/3)5 = 125/3 + 25 - 5/3 = 65 I am going to assume that this part is correct because it probably is. We are then left with proving that every term will be an integer. The only terms in a_n which could result in a non-integer are (1/3)n^3 and -(1/3)n. There are two cases for n: n is either a multiple of 3, or it isn't. If n is a multiple of 3, then clearly all terms will be integers, and the result will be an integer. Let's look at the other case. If n is not a multiple of 3, it can be broken into 2 parts, n mod 3, hereafter p, and n - (n mod 3), hereafter q. q can also be quickly seen as a multiple of three. Thus the part that we have to worry about making integral is (p+q)^3 - (p+q). Expanding gives us p^3 + 2qp^2 + 2pq^2 + q^3 - p - q. Removing all terms with just q in them gives us p^3 + 2qp^2 + 2pq^2 - p. p either equals 1 or 2, so we have 2 cases. If p equals 1, we have 1 + 2q + 2q^2 - 1, which simplifies to 2q + 2q^2, which is clearly a multiple of 3 as q is. If q equals 2, we have 8 + 8q + 4q^2 - 2, which simplifies to 8q + 4q^2 + 6, which also must be a multiple of 3. I'm sure I didn't do this the easiest way, and I kind of intuited the first step, but I think I showed what was required.
Posted: 2/2/2008 2:46 AM
Quote
Dacicus
Editor, Player (67)
Joined: 6/22/2005
Posts: 1041
I'm not quite clear on how you defined p and q. Is p the remainder when n is divided by 3, and q = n - p?
Current Projects: TAS: Wizards & Warriors III.
Posted: 2/2/2008 3:48 AM
Quote
snorlax
He/Him
Joined: 5/20/2007
Posts: 174
Location: Wisconsin
Dacicus wrote:
I'm not quite clear on how you defined p and q. Is p the remainder when n is divided by 3, and q = n - p?
Yes.
Posted: 2/2/2008 7:11 AM
Quote
FractalFusion
Editor, Skilled player (1939)
Joined: 6/15/2005
Posts: 3247
Glitchy TAS of 2013 Gameboy TAS of 2013 PSX TASer of 2010
snorlax wrote:
a_n = (1/3)n^3 + n^2 - (1/3)n ... I am going to assume that this part is correct because it probably is. We are then left with proving that every term will be an integer. ...
(1/3)n^3 + n^2 - (1/3)n = (1/3)(n)(n^2 - 1) + n^2 = (1/3)(n)(n+1)(n-1) + n^2 n(n+1)(n-1) is clearly divisible by 3; therefore a_n is an integer. snorlax, your way for the first step (guessing that it is a third-degree polynomial) seems best. It may be possible to solve using recurrence relations and generating functions, but that is hard to grasp.
Posted: 2/4/2008 7:18 PM
Quote
FractalFusion
Editor, Skilled player (1939)
Joined: 6/15/2005
Posts: 3247
Glitchy TAS of 2013 Gameboy TAS of 2013 PSX TASer of 2010
Another problem: Prove that in any set of 100 points on integer coordinates in 5-dimensional space, there exist 4 points such that the midpoint of each pair of points of those 4 has integer coordinates.
Posted: 2/5/2008 1:13 AM
Quote
Gorash
Joined: 4/16/2005
Posts: 251
Having an integer midpoint means that both points are in each dimension either odd or even. This property of being even or odd in 5 dimensions equals 2^5 = 32 different states in which a point may be. If you try to disprove the assumption by sorting 3 of each state into the 5d space, then you have 96 points, of which only ever 3 have the desired property. Whichever point you add as a 97th, it will be the forth for at least one configuration.
Posted: 2/8/2008 3:40 PM
Quote
Warp
Banned User, Former player
Joined: 3/10/2004
Posts: 7698
Location: Finland
Easy one: Deduce the (minimum) number of moves required to solve the Tower of Hanoi puzzle with 3 pegs and n discs. Harder one: By their nature, factorials tend to accumulate trailing zeroes. For example, 5! (120) has one trailing zero, 10! (3628800) has two trailing zeroes, 25! (15511210043330985984000000) has six trailing zeroes, etc. Write a function which, for an integer n, gives the number of trailing zeroes in n!.
Posted: 2/8/2008 4:03 PM
(Edited: 2/8/2008 4:11 PM)
Quote
zefiris
Joined: 4/11/2006
Posts: 487
Location: North of Russia :[
where floor(n) = integer part of n
Posted: 2/8/2008 4:10 PM
(Edited: 2/8/2008 4:14 PM)
Quote
Twelvepack
Joined: 5/2/2006
Posts: 1020
Location: Boulder, CO
Warp wrote:
Write a function which, for an integer n, gives the number of trailing zeroes in n!.
int(n/5^1)+int(n/5^2)+int(n/5^3)+int(n/5^4)... where int(x) returns the value of x, with any decmal value truncated away I think it ought to work.
Has never colored a dinosaur.
Posted: 2/8/2008 4:13 PM
Quote
zefiris
Joined: 4/11/2006
Posts: 487
Location: North of Russia :[
Twelvepack wrote:
int(n/5^1)+int(n/5^2)+int(n/5^3)+int(n/5^4)... I think.
Yup, that's what hides behind big function on my picture ^^
Posted: 2/8/2008 4:41 PM
Quote
Warp
Banned User, Former player
Joined: 3/10/2004
Posts: 7698
Location: Finland
"Deduce" kind of implied "show me your deduction process".
Posted: 2/8/2008 4:56 PM
Quote
zefiris
Joined: 4/11/2006
Posts: 487
Location: North of Russia :[
let's see. If n = 1 then obviously we have to do 1 turn. for any other n we first should move n-1 discs to second peg, then move n-th disc to last peg and move n-1 discs to third peg, so f(n) = 1 + 2*f(n-1) = 1 + 2*(1+2*f(n-2)) = ... = 1 + 2*(1+2*(1+2*(...1+2*f(1)))) = 1 + 2 + 2^2 + 2^3 + ... + 2^(n-1) = 2^n-1 as for the second one, we should just calculate how many times do we multiply by 10. 10 = 2*5, and as 5 meets rare, we must calculate, how many times do we have 5 as simple multiplier. It's obvious that we multiply by 5 every 5 steps, additionally we multiply by 5 every 25 steps etc... I hope what I wrote is understandable~ ^___^
Posted: 2/8/2008 8:06 PM
Quote
Warp
Banned User, Former player
Joined: 3/10/2004
Posts: 7698
Location: Finland
How about this: Find the largest n for which: 1) n is a prime. 2) The nth prime is smaller than 4200000000. As the answer, provide both n and the nth prime. (Ok, not really a math puzzle per se, but a programming task (or a 'using appropriate tools' task), but interesting nevertheless. Btw, I wrote a program to find the answer and it took 74 seconds to do so in my computer, using only standard C++.)
Posted: 2/8/2008 10:20 PM
Quote
AQwertyZ
Joined: 12/3/2006
Posts: 131
Location: Seattle
n = 198,996,071 nth prime = 4,199,999,261 Mathematica Code: 
bound = 4200000000;
s = 0;
While[Prime[Prime[2^(s + 1)]] < bound, s++];
x = 2^s;
For[t = s - 1, t ≥ 0, t--, If[Prime[Prime[x + 2^t]] < bound, x = x + 2^t]];
Print[Prime[x]]
Print[Prime[Prime[x]]]
Takes less than a second to run. It was convenient that Mathematica has a built in function Prime[n] that gives you the nth prime.
Posted: 2/8/2008 11:31 PM
Quote
snorlax
He/Him
Joined: 5/20/2007
Posts: 174
Location: Wisconsin
Warp wrote:
Easy one: Deduce the (minimum) number of moves required to solve the Tower of Hanoi puzzle with 3 pegs and n discs. Harder one: By their nature, factorials tend to accumulate trailing zeroes. For example, 5! (120) has one trailing zero, 10! (3628800) has two trailing zeroes, 25! (15511210043330985984000000) has six trailing zeroes, etc. Write a function which, for an integer n, gives the number of trailing zeroes in n!.
There are only 5 trailing zeroes in 25! because 5 goes into it 5 times. Not sure where your math went wrong as I don't know where to figure out the product without doing it longhand, and that's unnecessary.
Posted: 2/8/2008 11:33 PM
Quote
zefiris
Joined: 4/11/2006
Posts: 487
Location: North of Russia :[
There are only 5 trailing zeroes in 25! because 5 goes into it 5 times.
5 = 5*1 (1 in total) 10 = 5*2 (1+1 = 2) 15 = 5*3 (2+1 = 3) 20 = 5*4 (3+1 = 4) 25 = 5*5 (4+2 = 6) what's wrong? ^__^
Posted: 2/9/2008 7:39 AM
Quote
IronSlayer
Joined: 5/30/2007
Posts: 324
Warp wrote:
By their nature, factorials tend to accumulate trailing zeroes. For example, 5! (120) has one trailing zero, 10! (3628800) has two trailing zeroes, 25! (15511210043330985984000000) has six trailing zeroes, etc. Write a function which, for an integer n, gives the number of trailing zeroes in n!.
Leading zeros in n! = least integer function (n/(5^x)) + least integer function (n/5^(x-1))+....+ least integer function (n/5) where n>5^x but n<5^(x+1) Good old eighth grade math.... Edit Damn it, about a million people wrote it before me, and with nice imported graphics, too. My fault for not reading replies.
snorlax wrote:
There are only 5 trailing zeroes in 25! because 5 goes into it 5 times. Not sure where your math went wrong as I don't know where to figure out the product without doing it longhand, and that's unnecessary.
Apparently, realizing that five goes into 25 TWICE was what he did "wrong".
Posted: 2/12/2008 9:28 PM
Quote
Twelvepack
Joined: 5/2/2006
Posts: 1020
Location: Boulder, CO
The logic behind it is what is more interesting. All you really need to do is figure out how many 5s are in the prime factorization of x, because a trailing zero is caused by the existance of both a 2 and a 5 in the factorization, and its simple to show we have excess 2s.
Has never colored a dinosaur.
Posted: 2/13/2008 2:33 PM
Quote
Warp
Banned User, Former player
Joined: 3/10/2004
Posts: 7698
Location: Finland
One interesting question is whether the "number of trailing zeros in n!" function could be written as a non-iterative/non-recursive function (ie. one where the number of required operations does not depend on the parameter). If it can't, proving it could probably be quite hard.
Posted: 2/13/2008 9:22 PM
Quote
AQwertyZ
Joined: 12/3/2006
Posts: 131
Location: Seattle
If we plug 5^x in for n in the formula above, all the floor functions are unnecessary and we get: f(5^x) = 5^0 + 5^1 + ... + 5^(x-1) Since that is a geometric series, the formula simplifies to: f(5^x) = (5^x - 1) / 4 Replacing 5^x back with n gives: f(n) = (n - 1) / 4 So basically, when n is a power of 5 (n = 1, 5, 25, 125, ...), the number of trailing zeros can be calculated without any summations. My guess would be that it's impossible to create a generalized formula for any n that does not contain any iterations or recursion but you're right, proving that probably wouldn't be easy. Interestingly, my formula shows that on average, a trail zero is added once every 4 times n is incremented. EDIT I figured out a recursive version of the formula. I know this doesn't solve the problem but I thought I'd post it anyway. It's nice because it doesn't involve any logs. f(0) = 0 f(n) = floor(n/5) + f(floor(n/5))
Posted: 2/14/2008 12:26 AM
Quote
alden
Player (120)
Joined: 2/11/2007
Posts: 1522
It's interesting look as well at the other bases. In binary for example, the number of 0's is of course the total number of prime factors in the numbers from 1 to n that are 2. The recursive formula in this case is f(0) = 0 f(n) = floor(n/2) + f(floor(n/2)) And in the special case where n = 2^x, f(n) = n - 1 A similar recursive formula works for base 3, 5, 7 ... probably all the prime numbers. For base = 2x where x is a non-2 prime, f(0) = 0 f(n) = floor(n/x) + f(floor(n/x)) seems to always work as well (base 10 being an example of this). But, for bases of more complex sets of prime factors, like 12 or 18 the pattern breaks down ... can someone think of a more general recursive function?
I make a comic with no image files and you should read it. While there is a lower class, I am in it, and while there is a criminal element I am of it, and while there is a soul in prison, I am not free. -Eugene Debs
Posted: 2/15/2008 10:39 AM
Quote
Warp
Banned User, Former player
Joined: 3/10/2004
Posts: 7698
Location: Finland
AQwertyZ wrote:
f(0) = 0 f(n) = floor(n/5) + f(floor(n/5))
That's a much simpler and more beautiful answer to the problem. :)
1 2
15 16 17
132 133