Friday, July 12, 2013

100-lightbulb problem, with my solution

Q: There are 100 switched-off light bulbs along a staircase. Visitor #1 walks upstairs, pushing the on/off switch at each bulb. Visitor #2 walks upstairs hitting bulb #2,4,6...100. Visitor #3 to #100 each walks upstairs. In the end how many light bulbs are on? Can you tell me which bulbs are on? Can you tell me how many times each bulb has turned on?

For each integer between 1 and 100, factor it into "prime" factors. For eg, 72 = 2x2x2x3x3. Each integer is then expressed in the "Beautiful" form like A^n x B^m x C^p... where ABC are increasing prime numbers and nmp are exponents. For eg, 72 = 2^3 x 3^2.

Now (n+1)(m+1)(p+1)... is the number of "toggles" received by the light bulb. For eg, Bulb#72 gets 12 toggles. Bulb 10 gets 4 toggles (due to 2^1 x 5^1). Bulb 13 gets 2 toggles (due to 13^1).

Now let me defined Group-E and Group-O --
If (n+1)(m+1)(p+1)... is even, then the light bulb is in Group-E.
If (n+1)(m+1)(p+1)... is odd, then the light bulb is in Group-O.

Now, (n+1)(m+1)(p+1)... is usually an even integer. It's odd only if n,m,p... are all even -- for eg Bulb#4, #64, #36, ...-- Group-O. It's easy to list all of them.

2^2,  2^4,  2^6,  3^2 , 3^4,  5^2,  7^2
2^2x3^2,  2^2x5^2

For all the "prime" bulbs like #2, #3 ... #37..., the beautiful form looks like A^1, so these prime bulbs each gets 2 toggles exactly. Therefore Group-E.

Special cases -- Bulb #1 gets togged only once -- Group-O.

It turned out Group-O is the group of square numbers.



No comments:

Total Pageviews

my favorite topics (labels)

_fuxi (302) _misLabel (13) _orig? (3) _rm (2) _vague (2) clarified (58) cpp (39) cpp_const (22) cpp_real (76) cpp/java/c# (101) cppBig4 (54) cppSmartPtr (35) cppSTL (33) cppSTL_itr (27) cppSTL_real (26) cppTemplate (28) creditMkt (14) db (65) db_sybase (43) deepUnder (31) dotnet (20) ECN (27) econ/bank` (36) fin/sys_misc (43) finGreek (34) finReal (45) finRisk (30) finTechDesign (46) finTechMisc (32) finVol (66) FixedIncom (28) fMath (7) fMathOption (33) fMathStoch (67) forex (39) gr8IV_Q (46) GTD_skill (15) GUI_event (30) inMemDB (42) intuit_math (41) intuitFinance (57) javaMisc (68) javaServerSide (13) lambda/delegate (22) marketData (28) math (10) mathStat (55) memIssue (8) memMgmt (66) metaProgram` (6) OO_Design (84) original_content (749) polymorphic/vptr (40) productive (21) ptr/ref (48) py (28) reflect (8) script`/unix (82) socket/stream (39) subquery/join (30) subvert (13) swing/wpf (9) sysProgram` (16) thread (164) thread_CAS (15) thread_cpp (28) Thread* (22) timeSaver (80) transactional (23) tune (24) tuneDB (40) tuneLatency (30) z_ajax (9) z_algoDataStruct (41) z_arch (26) z_arch_job (27) z_automateTest (17) z_autoTrad` (19) z_bestPractice (39) z_bold (83) z_bondMath (35) z_book (18) z_boost (19) z_byRef^Val (32) z_c#GUI (43) z_c#misc (80) z_cast/convert (28) z_container (67) z_cStr/arr (39) z_Favorite* (8) z_FIX (15) z_forex (48) z_fwd_Deal (18) z_gz=job (33) z_gzBig20 (13) z_gzMgr (13) z_gzPain (20) z_gzThreat (19) z_hib (19) z_IDE (52) z_ikm (5) z_IR_misc (36) z_IRS (26) z_javaWeb (28) z_jdbc (10) z_jobFinTech (46) z_jobHunt (20) z_jobRealXp (10) z_jobStrength (15) z_jobUS^asia (27) z_letter (42) z_linq (10) z_memberHid` (11) z_MOM (54) z_nestedClass (5) z_oq (24) z_PCP (12) z_pearl (1) z_php (20) z_prodSupport (7) z_py (31) z_quant (14) z_regex (8) z_rv (38) z_skillist (48) z_slic`Problem (6) z_SOA (14) z_spring (25) z_src_code (8) z_swingMisc (50) z_swingTable (26) z_unpublish (2) z_VBA/Excel (8) z_windoz (17) z_wpfCommand (9)

About Me

New York (Time Square), NY, United States
http://www.linkedin.com/in/tanbin