Ponder This Challenge - December 2009 - Finding 25 bits number using masks

Ponder This Challenge:

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

Solution

• Click here to view the solution

  The product is even, so it must be a power of 2, which means that every one of the 10 terms has only one bit set. The condition actually implies that x encodes a permutation on 5 elements. N=7 questions are needed and, for example, the N-2=5 mask questions {0x83, 0x700, 0x41800, 0x288000, 0xc00010} divide the 120 possibilities into subsets of no more than 4 elements. It is easy to show that 2 more questions suffice.

Solvers

• 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)
• V (12/06/2009 05:09 PM EDT)
• ladimir 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)