Home » Other » General » Puzzle n°13 - light bulbs *
| Puzzle n°13 - light bulbs * [message #517054] |
Fri, 22 July 2011 02:52  |
 |
Littlefoot
Messages: 21823
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  |
 |
Michel Cadot
Messages: 68716
Registered: March 2007
Location: Saint-Maur, France, https...
|
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 #517419 is a reply to message #517061] |
Mon, 25 July 2011 23:07 |
rleishman
Messages: 3728
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!
|
|
|
|
|
|
Goto Forum:
Current Time: Fri Nov 22 15:23:18 CST 2024
|
] 
Blog
Search
Help
Members
Register
Login
Home
