Home » Other » General » Puzzle n°13 - light bulbs *
Puzzle n°13 - light bulbs * [message #517054] Fri, 22 July 2011 02:52 Go to next message
Littlefoot
Messages: 19540
Registered: June 2005
Location: Croatia, Europe
Senior Member
Account Moderator
It is summer; all people (who aren't on a vacation) do is recover unrecoverable databases, cope with unformatted forum messages, drink too much coffee, read last month's news and seem to be bored. So here's an easy one for you who don't have anything smarter to do.




There are 100 light bulbs, 100 switches (one per light bulb) and 100 men.
  • The 1st man comes and pushes every switch (i.e. all lights are now ON).
  • The 2nd man comes and pushes every 2nd switch (i.e. bulbs 2, 4, 6, 8, ... are now OFF)
  • The 3rd man comes and pushes every 3rd switch (i.e. switches 3, 6, 9, ...) and - depending on bulb state, some of them are switched ON, some OFF
  • ...
  • The 100th man comes and pushes the 100th switch
How many light bulbs are still ON?

[Updated on: Fri, 22 July 2011 02:54]

Report message to a moderator

Re: Puzzle n°13 - light bulbs * [message #517058 is a reply to message #517054] Fri, 22 July 2011 03:23 Go to previous messageGo to next message
Michel Cadot
Messages: 58959
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
Brute force:
SQL> col light format a5
SQL> with 
  2    bulbs as ( select level bulb from dual connect by level <= 100 ),
  3    men as ( select level man from dual connect by level <= 100 )
  4  select bulb, 
  5         decode(mod(count(decode(mod(bulb,man),0,1)),2), 1, 'ON', 'OFF') light
  6  from bulbs, men
  7  group by bulb
  8  order by bulb
  9  /
      BULB LIGHT
---------- -----
         1 ON
         2 OFF
         3 OFF
         4 ON
         5 OFF
         6 OFF
         7 OFF
         8 OFF
         9 ON
        10 OFF
        11 OFF
        12 OFF
        13 OFF
        14 OFF
        15 OFF
        16 ON
        17 OFF
        18 OFF
        19 OFF
        20 OFF
...
        80 OFF
        81 ON
        82 OFF
        83 OFF
        84 OFF
        85 OFF
        86 OFF
        87 OFF
        88 OFF
        89 OFF
        90 OFF
        91 OFF
        92 OFF
        93 OFF
        94 OFF
        95 OFF
        96 OFF
        97 OFF
        98 OFF
        99 OFF
       100 ON

so:
SQL> with 
  2    bulbs as ( select level bulb from dual connect by level <= 100 ),
  3    men as ( select level man from dual connect by level <= 100 ),
  4    lights as ( 
  5      select bulb, 
  6             decode(mod(count(decode(mod(bulb,man),0,1)),2), 1, 'ON', 'OFF') light
  7      from bulbs, men
  8      group by bulb
  9    )
 10  select count(decode(light, 'ON', 1)) nb_on
 11  from lights
 12  /
     NB_ON
----------
        10

Regards
Michel

[Updated on: Fri, 22 July 2011 03:25]

Report message to a moderator

Re: Puzzle n°13 - light bulbs * [message #517059 is a reply to message #517058] Fri, 22 July 2011 03:28 Go to previous messageGo to next message
Littlefoot
Messages: 19540
Registered: June 2005
Location: Croatia, Europe
Senior Member
Account Moderator
I knew it won't be difficult.

Did you notice WHICH bulbs have remained switched ON?
Re: Puzzle n°13 - light bulbs * [message #517061 is a reply to message #517059] Fri, 22 July 2011 03:42 Go to previous messageGo to next message
Michel Cadot
Messages: 58959
Registered: March 2007
Location: Nanterre, France, http://...
Senior Member
Account Moderator
I should say square. Wink

Regards
Michel
Re: Puzzle n°13 - light bulbs * [message #517419 is a reply to message #517061] Mon, 25 July 2011 23:07 Go to previous messageGo to next message
rleishman
Messages: 3700
Registered: October 2005
Location: Melbourne, Australia
Senior Member
Very cool. I had a go at proving it, and reduced it to the following statements:
- The ON lights have been switched an ODD number of times
- A light is switched once for each of its positive factors (including 1 and the number itself)
- Only perfect squares have an odd number of factors

That last one was a bit tougher to prove:
- Non-squares may be represented in 1 or more ways as [n = a x b, where 1 <= a < b <= n]. a and b always appear in pairs, so no matter how many different factorizing pairs, there are always an even number of factors.
- Squares may be represented as [n = a x a] exactly once, and [n = a x b, where 1 <= a < b <= n] an even number of times as above. Total number of factors: ODD!
Re: Puzzle n°13 - light bulbs * [message #517426 is a reply to message #517419] Tue, 26 July 2011 00:59 Go to previous message
Littlefoot
Messages: 19540
Registered: June 2005
Location: Croatia, Europe
Senior Member
Account Moderator
Very cool, Ross, very!
Previous Topic: Puzzle n°12 - Arithmetic expressions for a given result (24 game) *
Next Topic: spacing issue
Goto Forum:
  


Current Time: Tue Sep 02 15:17:07 CDT 2014

Total time taken to generate the page: 0.06215 seconds