All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Close neighbours (Posted on 2013-04-15) Difficulty: 3 of 5
Denote by S the set of all binary integers that can be written using exactly m zeros and n ones, leading zeros permitted.

How many couples in this set differ exactly by one?

Check your formula for m=6, n=3 and for m=3, n=6.

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution Comment 1 of 1

If the lower integer of the pair ends in 00, the number of 1's will rise at the expense of the 0's

If the lower integer ends with 01, they become 10 and the numbers of 1's and zeros stay the same.

If the lower integer ends with 10, they become 11 and the number of 1's rises at the expense of the 0's.

If the lower integer ends 11, they both become 0, decreasing the count of 1's by two and increasing that of 0's by two. The carry of 1 can either increase the  1 count of the pair to the left by 1, by zero, or again reduce it by 2.

So, of the C(m+n,m) numbers with m zeros and n 1's, only the ones ending in 01 differ by 1. The count of these numbers is C(m+n-2,m-1).

In the test cases presented:

for m=6, n=3; C(7,5) = 21

All the combinations of 6 zeros and 3 1's:

111000000 000000111 000001011 000001101 000001110 000010011 000010101 000010110
000011001 000011010 000011100 000100011 000100101 000100110 000101001 000101010
000101100 000110001 000110010 000110100 000111000 001000011 001000101 001000110
001001001 001001010 001001100 001010001 001010010 001010100 001011000 001100001
001100010 001100100 001101000 001110000 010000011 010000101 010000110 010001001
010001010 010001100 010010001 010010010 010010100 010011000 010100001 010100010
010100100 010101000 010110000 011000001 011000010 011000100 011001000 011010000
011100000 100000011 100000101 100000110 100001001 100001010 100001100 100010001
100010010 100010100 100011000 100100001 100100010 100100100 100101000 100110000
101000001 101000010 101000100 101001000 101010000 101100000 110000001 110000010
110000100 110001000 110010000 110100000

Those that differ by 1:

 13           000001101      14           000001110
 21           000010101      22           000010110
 25           000011001      26           000011010
 37           000100101      38           000100110
 41           000101001      42           000101010
 49           000110001      50           000110010
 69           001000101      70           001000110
 73           001001001      74           001001010
 81           001010001      82           001010010
 97           001100001      98           001100010
 133          010000101      134          010000110
 137          010001001      138          010001010
 145          010010001      146          010010010
 161          010100001      162          010100010
 193          011000001      194          011000010
 261          100000101      262          100000110
 265          100001001      266          100001010
 273          100010001      274          100010010
 289          100100001      290          100100010
 321          101000001      322          101000010
 385          110000001      386          110000010

The count of these:
 21
 
For m=3, n=6, C(7,2) = 21:

All the combinations of 3 zeros and 6 1's:

111111000 000111111 001011111 001101111 001110111 001111011 001111101 001111110
010011111 010101111 010110111 010111011 010111101 010111110 011001111 011010111
011011011 011011101 011011110 011100111 011101011 011101101 011101110 011110011
011110101 011110110 011111001 011111010 011111100 100011111 100101111 100110111
100111011 100111101 100111110 101001111 101010111 101011011 101011101 101011110
101100111 101101011 101101101 101101110 101110011 101110101 101110110 101111001
101111010 101111100 110001111 110010111 110011011 110011101 110011110 110100111
110101011 110101101 110101110 110110011 110110101 110110110 110111001 110111010
110111100 111000111 111001011 111001101 111001110 111010011 111010101 111010110
111011001 111011010 111011100 111100011 111100101 111100110 111101001 111101010
111101100 111110001 111110010 111110100

Those that difffer by 1:

 125          001111101      126          001111110
 189          010111101      190          010111110
 221          011011101      222          011011110
 237          011101101      238          011101110
 245          011110101      246          011110110
 249          011111001      250          011111010
 317          100111101      318          100111110
 349          101011101      350          101011110
 365          101101101      366          101101110
 373          101110101      374          101110110
 377          101111001      378          101111010
 413          110011101      414          110011110
 429          110101101      430          110101110
 437          110110101      438          110110110
 441          110111001      442          110111010
 461          111001101      462          111001110
 469          111010101      470          111010110
 473          111011001      474          111011010
 485          111100101      486          111100110
 489          111101001      490          111101010
 497          111110001      498          111110010
 
 count of these:
 21
 
 The basic test program, in this case for 6 zeros and 3 1's:
 
 DECLARE SUB permute (a$)
 CLS
 a$ = "111000000": h$ = a$
 DIM used(512), bsave$(512)
 DO
   PRINT a$; " ";
 
   v = 0
   FOR i = 1 TO LEN(a$)
     v = v * 2 + VAL(MID$(a$, i, 1))
   NEXT
   used(v) = used(v) + 1: bsave$(v) = a$
   IF used(v) > 1 THEN PRINT "error": STOP
   permute a$
 LOOP UNTIL a$ = h$
 PRINT
 FOR i = 2 TO 512
 IF used(i) = used(i - 1) AND used(i) = 1 THEN
   tot = tot + 1
   PRINT i - 1, bsave$(i - 1), i, bsave$(i)
 END IF
 NEXT
 
 PRINT tot

Edited on April 15, 2013, 9:55 pm
  Posted by Charlie on 2013-04-15 16:28:18

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information