• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

another question for nerds

 
Ranch Hand
Posts: 1934
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There are 1000 bulbs(from 1 to 1000) that can be switched on or off.
There are 1000 priests. Priest 1 goes and switches on from 1 through 1000 bulbs.
Priest 2 switches on/off switches that can be multiplied by 2.(so switch 2,4,6,..1000 are off now) Switch 3 does the same for swiches 3,6,9...999(so switch 6,12,18.. are on now).
At the end of 1000 priests, how many switches are on??
I am getting some ideas related to prime numbers for this question(that is non-primes does not have any say on the outcome, since what ever a non-prime does is cancelled out by some other nonprime).
Waiting for some answers from the nerds forum.
Dan
 
Ranch Hand
Posts: 1140
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I don't have a mathematical proof, but I used the following program to find the answer.

The answer is 1,4,9,16,25,36..........961, which are all proper squares!
[ February 25, 2004: Message edited by: Mani Ram ]
 
Ranch Hand
Posts: 1365
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I don't have a mathematical proof
Think about the number of factors a given number N has. When is the factor count odd? When is it even?
 
Ranch Hand
Posts: 1907
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Number of factors for any number(when number is not a square) will be always even(including that number and number '1')whereas number of factors for a number which is a square,number of factors will be always odd(as square root is counted only once and rest in pairs).Hence bulb with square number will be ON and remaining bulbs OFF.
[ February 25, 2004: Message edited by: Capablanca Kepler ]
 
Ranch Hand
Posts: 1170
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
1000
1000/2 = 500 odd numbered bulbs
(1000/2) /3 = ~166 (every odd bulb, and every third of those)
could be wrong, but thats whats off top of my head.
oh, 3rd switches bulbs back on? that would then be
500 + 166 = 666
hehe, is this a joke?
[ February 25, 2004: Message edited by: CL Gilbert ]
 
Kishore Dandu
Ranch Hand
Posts: 1934
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Gilbert,
The answer is already given by one of the other guys.
Sometimes, these kind of questions easy to answer, if you change your premise to a smaller number, like 1-100 instead of 1-1000.
Then you can easily nail the question. I was about to go your way, then backed off to 1-100 and got it.
Dan
 
Author
Posts: 6055
8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I use this question in interviews sometimes.
Most people tend towards primes. As a hint, I somtimes tell people to try working it out by brute force, and then see how they approach it. Usually they have to try up through 10, just doing 5-6 doesn't help.
The secret is to invert the problem. Most people think of it from the perspective of the priest, which lockers he touches. If you think of it from the locker's perspective (that is, what a single locker sees), it's obvious.
--Mark
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic