August 13th, 2007
Post solutions here.
Pages: 1 2
This entry was posted
on Monday, August 13th, 2007 at 3:51 pm and is filed under Math, Riddles.
You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.
August 13th, 2007 at 5:02 pm
lemma: for any 5 given integers there is an arrangement of operators (just like in the riddle) for which the formula equals 0 (mod 5)
proof: by looking at the partial sums and using pigeon-hole principle if none of them equal 0 (mod 5)
lemma 2: for any 2 given integers there is an arrangement of operatos for which the formula equals 0 (mod 2)
proof: obvious
proof of riddle: split the 23 numbers into (runs of) 3 5-tuples and 4 couples, and seclude which group with parenthesis. (3*5+2*4 = 23)
in each group of i numbers arrange the operatos between them so the formula they produce equals 0 (mod i)
add multiplicative operator * between each group.
we get (5k1)*(5k2)*(5k3)*(2n1)*…(2n4) = 2000*z.
August 15th, 2007 at 3:27 am
I did the exact same same solution, and since it’s Ronnie who replied, I can now rest assure my solution is correct
i have to say that at first i was very much afraid of this riddle, and wasn’t really sure why it was posted as “easy riddle”, however it turned out to fun…
August 16th, 2007 at 2:54 am
I finally had time to think about the first extra credit question, and its not that hard – 23 is indeed a tight bound.
Consider the case of 22 ones.
August 17th, 2007 at 1:14 pm
Very cool riddle! I also felt like Dan and would never have tuched this riddle with a 10-foot pole if it wasn’t for the “easy” icon.
Regardinig extra credit question no. 2, I’ll start by stating the obvious rule that we get by generalizing this riddle:
for every N=5^a*2^b and K=5a+2b, (N,K) is a valid pair.
August 17th, 2007 at 1:24 pm
By the way, does Ronnie’s lemma generalize to any prime? I did not understand the proof with the pigeonhole principle so I can’t say so myself (I have “proven” it stupidly by just enumerating the entire tree, so generalizing my “proof” is hard. I can probably just think of this myself but I don’t feel like it so I’ll use the blog’s computing power instead)
If it does, we get the even more general relation that for every
N = p1^a1 + p2^a2 + p3^a3 + … Where p1,p2,p3,… are primes,
K = p1*a1 + p2*a2 + …
then (N,K) is a valid pair.
August 17th, 2007 at 2:25 pm
Hey Matan,
a) my lemma for p=5 generalizes for any number actually (although it’s obvioulsy not tight, for example 2000).
I’ll explain more thoroughly for p = 5. I look at the partial sums of n1..n5: s(i).
if some s(i) equals 0 (mod 5) then simply put operators so the formula would look like this:
(n1+..n(i))*n(i+1)*..n5 = s(i)*… = 0 (mod 5).
if not, then there must be two sums s(i)=s(j) (mod 5) (i
August 17th, 2007 at 2:29 pm
(message was cut!)
… (i
August 17th, 2007 at 4:21 pm
Hi Ronnie,
First, I want to appologize for your messages being cut.
The reason is that all the text of the comments is filtered before it is entered into the database (otherwise people would be able to post harmful javascript code and use XSS). Now, there is a bug in the filtering mechanism (its a wildly used mechanism – I haven’t written it!). It is too severe, if you enter the < sign all the text after it will be cut off.
You might be wondering how I was able to use the < sign before (oops, I did it again!), well until I fix the bug you can use the ampersand sign followed by the letters “lt” and a semi-colon (4 symbols in all). FYI – lt stands for less than. And yeah – I know its ugly…
BTW – you can still use the > sign regualrly (at least I hope! If this sentence makes sense than it worked
)