wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> st. edmundsbury's riddle
        
(Message started by: Moti on Nov 24^th, 2002, 1:45pm)

Title: st. edmundsbury's riddle
Post by Moti on Nov 24^th, 2002, 1:45pm

Long ago in st. edmundsbury monastery, as father peter told on one occasion, they were flooded with so many mice that the head of the monastery ordered to gather all the cats from the area to get rid of the rodents.
records were kept and on the end of the year they found that
exactly 1,111,111 mice were killed.
if every cat killed an equal number of mice, try and say how many cats were envolved.

(could be more than one answer)

Title: Re: st. edmundsbury's riddle
Post by Garzahd on Nov 24^th, 2002, 5:52pm

Must the cats be equally ravenous?

If so, then you're just asking for the prime factorization of that number, which is 1 (hungry kitty!), 239, 4649, 1111111 (presenting a new sort of infestation problem).

Title: Re: st. edmundsbury's riddle
Post by william wu on Nov 24^th, 2002, 7:43pm

the problem seems underspecified ...

Title: Re: st. edmundsbury's riddle
Post by Moti on Nov 25^th, 2002, 12:57am

I'm very sorry guys.

i was very tired when writing this.

of course every cat killed an equal number of mice.

Title: Re: st. edmundsbury's riddle
Post by william wu on Nov 25^th, 2002, 8:32am

All cats eat the same number of mice. Thus we want to evenly partition the group of mice such that every cat is allocated the same integer number of mice (assuming that no mouse was jointly fragged by more than one cat). So if we can figure out the size of a partition, we can divide 1111111 by that number to get the number of cats. Put more simply, we just need to know what integers divide evenly into 1111111. We can factorize the number 1111111 to get possible partition sizes:

>> factor(1111111)

ans =

239 4649

1111111 happense to have only these two large prime factors, which makes our list of possible answers short.

If every cat eats 239 mice, then there were 4649 cats involved in the purge.

If every cat eats 4649 mice, then there were 239 cats involved in the purge.

Title: Re: st. edmundsbury's riddle
Post by Moti on Nov 25^th, 2002, 8:39am

God bless you, William wu. :) :) :)

Title: Re: st. edmundsbury's riddle
Post by icon on Nov 25^th, 2002, 8:50am

william,

did you do this by hand or there is some program which bruteforces them?

ciao

Title: Re: st. edmundsbury's riddle
Post by Moti on Nov 25^th, 2002, 8:55am

although its been a long time since i did any programing.
i suppose you can just write a program that divides
a given number by a growing integer.
and gives you only the numbers that produced whole numbers
by division.

:D

Title: Re: st. edmundsbury's riddle
Post by towr on Nov 25^th, 2002, 9:09am

There are programs that can factor in a smart way..
Even the trial version of Derive 5 can do it..

Title: Re: st. edmundsbury's riddle
Post by jeremiahsmith on Nov 25^th, 2002, 10:55pm

Well, you could just have 1,111,111 cats who each kill one, or, alternatively, have a single überCat who killed all 1,111,111 :) (Well, the puzzle description does specify cats plural...darn...I was looking forward to seeing the überCat. :( )

Title: Re: st. edmundsbury's riddle
Post by william wu on Dec 8^th, 2002, 3:51pm

icon: I used the canned factor() function in MATLAB, which uses the sieve method.

jeremiah: Oops I forgot those cases. Yea, nice catch.

Title: Re: st. edmundsbury's riddle
Post by jon_G on Dec 8^th, 2002, 6:28pm

At first I thought this was a trick question but after a little thinking I knew it wasn't. My first thought was 1,111,111cats. I love the ubercat. ;)