wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Another How Many Integers Riddle...
        
(Message started by: Dudidu on Nov 20^th, 2003, 9:57am)

Title: Another How Many Integers Riddle...
Post by Dudidu on Nov 20^th, 2003, 9:57am

How many integers [in] {1,2,..., 5000} have a binary representation such that the number of 1's is a multiple of 3 ?

P.S. If your using a computer to exhaustively check all the binary representations you will only get half of the points ;).

Title: Re: Another How Many Integers Riddle...
Post by towr on Nov 20^th, 2003, 11:33am

If it the range went to some power of two it'd be a lot easier..

Title: Re: Another How Many Integers Riddle...
Post by TenaliRaman on Nov 20^th, 2003, 9:33pm

::[hide]
lets first look at interval (0,4095)
it takes 12 bit representation
so number of required integers,
C(12,0)+C(12,3)+C(12,6)+C(12,9)+C(12,12)

for the interval (4096,5000)
it takes 13 bit representation
things to note :
1>the 13th bit is already set (13 is MSB for me)
2>and for 5000 whose binary representation is
1001110001000, we note that the second highest bit set is 10th bit.
So the number of required integers in this interval,
C(10,2)+C(10,5)+C( 10,8 )

So the total is the sum of the above two,
which comes to
1708

but i have actually calculated for the interval (0,5119)
there are some extras, this is were i have to go manual and find the ones i need to remove from my count.

manual count gave me 39 extras.

so the actual required number of integers,
1708 - 39
=1669
[/hide]::

Title: Re: Another How Many Integers Riddle...
Post by towr on Nov 21^st, 2003, 1:03am

I did it fairly similar, but I got a different (hopefully correct) answer
::[hide]5000 = 4096+512+256+128+8
so the number of ones would be
C(12,3)+C(12,6)+C(12,9)+C(12,12)+ // # up to 4096
C(9,2)+C(9,5)+C(9,8)+ // one 1 from 4096, so we need 2,5 or 8 more
C(8,1)+C(8,4)+C(8,7)+ // 2 1's from 4096+512, 1,4 or 7 extra needed
C(7,0)+C(7,3)+C(7,6)+ // 3 1's from 4096+512+256, so 0,3 or 6 more needed
C(3,2) = 1668
[/hide]::

Title: Re: Another How Many Integers Riddle...
Post by TenaliRaman on Nov 21^st, 2003, 3:46am

you are right towr.
i did not see that 0 wasn't in the given set .. i had considered 0 earlier hence i got 1 more than your answer.

Title: Re: Another How Many Integers Riddle...
Post by Dudidu on Nov 23^rd, 2003, 4:47am

TenaliRaman and towr,
Your solution ([hide]1668[/hide]) is correct, well done ;D !
(and ,of course, you get all of the points ;)).