|
I took a swing at it and I did 2 problems lol. One for the morning and one for the afternoon. It's really cool and hard.
That was some epic 6 hour battle hahaha!!
Anyways the last problem is pretty hard, I couldn't do it so if anyone want to have a go at it! please! 
We have a sequence:
a0, a1, ..., a2009
a0 = 0, always
ai for i>=1 has to be either one of these:
ai = 2^k + aj for any non-negative integer k, and for any aj such that j<i
or
ai = aj mod ak, for j, k < i (doesn't matter if j<k or k<j)
a2009 = n, always. n is ANY positive integer.
so to rephrase the problem, in case it's not clear or it might help you understand it better:
if we start with 0 on a0, how can we make any positive integer n in 2009 steps, filling a0, then a1, a2, ... finally ending with n at a2009 where each time we try to fill some ai we must obey one out of these 2 rules:
1) ai is a sum of 2^k and aj for some aj occuring before ai
or
2) ai is a mod of ak and aj, where ak and aj occurs before ai (does not matter if ak occurs before or after aj)
How to do it?! I get this feeling we'll eventually run out of usable bits as 2^k can only add some 1 bit of information per iteration, I just dunno haha. This procedure must be made in constant and not linear time since 2009 is just some fancy cap. I feel that you should hit your target goal n say, at the 10th step then just repeat n over and over as n mod some large number.
Anyways take a swing at it!!
edit:
by mod I meant the element in the modulo class, i.e. b mod c is an element of {0, 1, ..., c-1}
|
|
|
cant you just say
a0 = 0
a1 = 2^0 + a0 = 1
a2 = 2^1 + a0 = 2
a3 = 2^1 + a1= 3
a4 = 2^2 + a0 = 4
a5 = 2^2 + a1 = 5
Like that you can make any number you want once you reach your number you can just ceep repeating the samething. in example if n were 5 you would ceep saying
an = 2^2 + a1
|
|
|
|
|
I've been looking around for interesting maths based problem solving sites and figured you guys might have some suggestions. Currently I'm slowly working through projecteuler.net
|
On December 06 2009 22:41 Marradron wrote:
cant you just say
a0 = 0
a1 = 2^0 + a0 = 1
a2 = 2^1 + a0 = 2
a3 = 2^1 + a1= 3
a4 = 2^2 + a0 = 4
a5 = 2^2 + a1 = 5
Like that you can make any number you want once you reach your number you can just ceep repeating the samething. in example if n were 5 you would ceep saying
an = 2^2 + a1
Surely that process only works for n<=2009
|
Umm, either I haven't read your question correctly or you haven't got the right one, but how about:
a0 = 0
a1 = 2^0+a0 = 1
a2 = 2^1 + a0 = 2
a3 = a4 = ... = a2008 = 2^1+a0 = 2 (you could make these any number you want really)
If n is odd, then n = 1 mod 2 = a1 mod a2, so a2009 can be n.
If n is even, then n = 0 mod 2 = a0 mod a2, so a2009 can be n.
Edit: I think there was a misunderstanding: when the OP says ai = aj mod ak, he doesn't mean ai is congruent to aj mod ak, but that ai = aj % ak, or in other words that ai is the remainder when aj is divided by ak.
|
I did 4 problems but I didn't really try this one.. it sounded way too hard lol. What exactly are you trying to figure out? which values of n are possible? or whether given an n if it's possible to do it.
|
Okay...I think I've got it.
First let's notice that 2 is a generator modulo 3^r for all r. That is, the set of residues of 2^k mod 3^r over all k are all of the residues relatively prime to 3^r. This can be shown because 2 is a generator mod 9, and then the standard primitive root lifting argument shows it for all r > 2.
Therefore, we know that if 3^r >> n, we can write n as the remainder of 2^k * 3^l mod 3^r for some k and l (let 2^k = n mod 3^r and l be the number of 3s dividing n). All we then need to show are that we can construct 2^k * 3^l and 3^r in a constant number of steps.
We have a_0 = 0. Let a_1 = 2^m for m >> r, k, and l, a_2 = 2^m + 1, and a_3 = 2^m + 3. Now we let a_4 = 2^(m*l + k) and a_5 = 2^(m*r). a_6 = a_4 % a_3 = 2^k * 3^l, and a_7 = a_5 % a_3 = 3^r. Finally a_8 = a_6 % a_7 = (2^k * 3^l) % (3^r) = n.
It's easy to then get a_2009 to be equal to n.
|
On December 06 2009 22:56 Ludrik wrote:
I've been looking around for interesting maths based problem solving sites and figured you guys might have some suggestions. Currently I'm slowly working through projecteuler.net
Old Putnam problems are available http://www.unl.edu/amc/a-activities/a7-problems/putnamindex.shtml
I went through some of these while preparing for the Putnam exam. Some of these can be done without anything more than freshman calculus, but many require undergraduate real analysis or abstract algebra.
|
|
|
I did not take the test, I am just using what I think the OP means.
|
On December 07 2009 01:44 Hamster1800 wrote:
I did not take the test, I am just using what I think the OP means.
Sorry mixed you up with someone else in the thread. Could you elucidate to me how you got a7? 2^(m*r) % 2^m +3 doesn't seem to equal 3^r for many values of m and r (I made sure m >> r too), though it's true for some of them.
|
On December 07 2009 01:14 searcher wrote:
a series a0...a2008 such that a2009 can be any n
Such a series is impossible to construct, so it is obvious that this wasn't the question. You can't construct larger numbers with the mod operation and you certainly can't create every n in N using just 2^k+c with a finite choice of c and for any k.
|
On December 07 2009 02:02 searcher wrote:Show nested quote +On December 07 2009 01:44 Hamster1800 wrote:
I did not take the test, I am just using what I think the OP means. Sorry mixed you up with someone else in the thread. Could you elucidate to me how you got a7? 2^(m*r) % 2^m +3 doesn't seem to equal 3^r for many values of m and r (I made sure m >> r too), though it's true for some of them.
Oh you are right, it is (-3)^r (+2^m if need be)....Just take r to be even. Unfortunately, there's still a problem in a_6. I'll look into it later when I have more time, but someone else can probably fix it before then.
|
On December 07 2009 02:10 Klockan3 wrote:Show nested quote +On December 07 2009 01:14 searcher wrote:
a series a0...a2008 such that a2009 can be any n Such a series is impossible to construct, so it is obvious that this wasn't the question.
Not if you used my original interpretation of what the OP meant by "ai = aj mod ak", which I took to be "ai is congruent to aj modulo ak". Since I have realized that my interpretation is most likely wrong (otherwise my trivial solution above would be correct) I should probably remove that comment.
|
On December 07 2009 02:11 Hamster1800 wrote:Show nested quote +On December 07 2009 02:02 searcher wrote:On December 07 2009 01:44 Hamster1800 wrote:
I did not take the test, I am just using what I think the OP means. Sorry mixed you up with someone else in the thread. Could you elucidate to me how you got a7? 2^(m*r) % 2^m +3 doesn't seem to equal 3^r for many values of m and r (I made sure m >> r too), though it's true for some of them. Oh you are right, it is (-3)^r (+2^m if need be)....Just take r to be even. Unfortunately, there's still a problem in a_6. I'll look into it later when I have more time, but someone else can probably fix it before then.
Do you use the % for a modulus operation? Like 23%9=5?
Then at least I would get 2^(m*r)%2^m+3 =(2^m)+3*(1-2^r) if m>>r.
|
On December 07 2009 02:19 Klockan3 wrote:Show nested quote +On December 07 2009 02:11 Hamster1800 wrote:On December 07 2009 02:02 searcher wrote:On December 07 2009 01:44 Hamster1800 wrote:
I did not take the test, I am just using what I think the OP means. Sorry mixed you up with someone else in the thread. Could you elucidate to me how you got a7? 2^(m*r) % 2^m +3 doesn't seem to equal 3^r for many values of m and r (I made sure m >> r too), though it's true for some of them. Oh you are right, it is (-3)^r (+2^m if need be)....Just take r to be even. Unfortunately, there's still a problem in a_6. I'll look into it later when I have more time, but someone else can probably fix it before then. Do you use the % for a modulus operation? Like 23%9=5? Then at least I would get 2^(m*r)%2^m+3 =(2^m)+3*(1-2^r) if m>>r.
2^(m*r) = (2^m)^r = (-3)^r mod (2^m+3). What you have is 2^(m+r).
To fix the other part, we were looking at 2^(m*l+k). If l is even, we're fine since (-3)^l = 3^l. If l is odd, we'll break it into two steps: 2^(m*(l-1) + k) and then 2^(m*(l-1) + k + 1) + 2^(m*(l-1) + k) = 3*2^(m*(l-1)+k), which will be congruent to 3*((-3)^(l-1)*2^k) = 3^l * 2^k.
|
On December 06 2009 23:14 searcher wrote:
Umm, either I haven't read your question correctly or you haven't got the right one, but how about:
a0 = 0
a1 = 2^0+a0 = 1
a2 = 2^1 + a0 = 2
a3 = a4 = ... = a2008 = 2^1+a0 = 2 (you could make these any number you want really)
If n is odd, then n = 1 mod 2 = a1 mod a2, so a2009 can be n.
If n is even, then n = 0 mod 2 = a0 mod a2, so a2009 can be n.
Edit: I think there was a misunderstanding: when the OP says ai = aj mod ak, he doesn't mean ai is congruent to aj mod ak, but that ai = aj % ak, or in other words that ai is the remainder when aj is divided by ak.
the latter is what I meant.
|
|
|
|
|
|
EPT
Starcraft has become my nerd activity of choice.
