Home » Other » General » Puzzle n°13 - light bulbs *
Puzzle n°13 - light bulbs * Fri, 22 July 2011 02:52
 Littlefoot Messages: 21678Registered: June 2005 Location: Croatia, Europe Senior MemberAccount 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
 Michel Cadot Messages: 67887Registered: March 2007 Location: Nanterre, France, http://... Senior MemberAccount 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
 Littlefoot Messages: 21678Registered: June 2005 Location: Croatia, Europe Senior MemberAccount 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
 Michel Cadot Messages: 67887Registered: March 2007 Location: Nanterre, France, http://... Senior MemberAccount Moderator
I should say square.

Regards
Michel
Re: Puzzle n°13 - light bulbs * [message #517419 is a reply to message #517061] Mon, 25 July 2011 23:07
 rleishman Messages: 3728Registered: 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
 Littlefoot Messages: 21678Registered: June 2005 Location: Croatia, Europe Senior MemberAccount 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 Jun 22 03:37:32 CDT 2021