IBM Research | Ponder This | December 2009 challenges
Skip to main content

Ponder This

December 2009

<<November December January>>


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 webmaster.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: webmster@us.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 webmaster.