December 2009
<<November December January>>
Let x be a 25-bit number, such that Πi=110(x&mi) is a nontrivial integer power (nk, n and k are integers, n>0 and k>1); where "&" stands for the Boolean bitwise AND function and the 10 hexadecimal masks mi are {0x1f, 0x3e0, 0x7c00, 0xf8000, 0x1f00000, 0x108421, 0x210842, 0x421084, 0x842108, 0x1084210}.
Find the minimal number of mask questions needed to find x, where a mask question m is asking whether (x&m) is zero.
It can be shown that, in our case, if x is known to be in a subset whose size is at most 4, then 2 mask questions would suffice to find it.
Submit your answer as a N-2 mask questions which when asked together (e.g. asking the third question without knowing the answer to the first two), would divide the set of possible numbers x into subsets of no more than 4 numbers each. You need not specify the last two which are composed based on the previous answers.
Update 12/04: The product should be an integer power of a *prime* number. Sorry for that and thanks for all the devoted solvers who tried the misleading version.
Update 12/09: Though x is a 25-bit number, it does not necessarily start with a leading 1.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
11/30/2009 @ 03:00 PM EST
Solution:
01/01/2010 @ 03:00 PM EST
List Updated:
12/29/2009 @ 03:00 PM EST
People who answered correctly:
Michael Brand (12/01/2009 06:43 PM EDT)
Donald T. Dodson (12/04/2009 08:27 PM EDT)
Andreas Stiller (12/04/2009 10:39 PM EDT)
Vladimir Sedach (12/06/2009 05:09 PM EDT)
Harald Bögeholz (12/06/2009 06:58 PM EDT)
Andreas Eisele (12/06/2009 07:57 PM EDT)
Pataki Gergely (12/07/2009 05:49 AM EDT)
Luke Pebody (12/07/2009 01:04 PM EDT)
Adam Daire (12/07/2009 01:56 PM EDT)
Daniel Bitin (12/07/2009 02:24 PM EDT)
Mark Mixer (12/08/2009 11:14 AM EDT)
Lachezar Hristov (12/12/2009 12:58 PM EDT)
Hongcheng Zhu (12/12/2009 02:43 PM EDT)
Dmitry Litvinenko (12/13/2009 08:17 AM EDT)
Lukasz Bolikowski (12/13/2009 05:15 PM EDT)
Nyles Heise (12/14/2009 12:36 AM EDT)
Dan Ignatoff (12/15/2009 04:22 AM EDT)
Ante Turudic (12/15/2009 07:51 AM EDT)
Corey Cerovsek (12/15/2009 03:10 PM EDT)
Joseph DeVincentis (12/15/2009 03:58 PM EDT)
Byron Rakitzis (12/17/2009 02:32 PM EDT)
Karl D'Souza (12/17/2009 06:41 PM EDT)
Albert Stadler (12/18/2009 10:17 AM EDT)
Chris Chen Xu (12/21/2009 09:29 PM EDT)
Dan Dima (12/22/2009 03:35 AM EDT)
John T. Robinson (12/22/2009 04:29 PM EDT)
Wu Hao (12/23/2009 10:23 AM EDT)
Michael D Moffitt (12/24/2009 01:22 AM EDT)
Irem Koprulu (12/27/2009 01:35 AM EDT)
Andrew Marut (12/30/2009 02:38 AM EDT)
Venkata Ramayya M (12/30/2009 11:56 AM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.