Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Sep 25, 2012

USA Maths Olympiad Problem - 200th Puzzle

200th Puzzle of the CSE Blog

Source:
I got hold of the super awesome book I read 6 years back: "A Path to Combinatorics for Undergraduates: Counting Strategies". A must have for any math/olympiad enthusiast (Flipkart link to Imported Edition and Indian Edition) - Example 5.8 - USAMO 1990

Problem:
Let n be a positive integer. Find the number of positive integers whose base n representation consists of distinct digits with the property that except for the leftmost digit, every digit differs by +1 or -1 from some digit further to the left.

Update (26/12/2012):
No correct solution provided. Solution posted by me in comments!

8 comments:

  1. i have not worked out the exact answer but it can be solved in following way:
    choose a number belonging to{1,n-2} for the leftmost digit. Now for every next blank place there are exactly two choices of numbers provided the digit to immediate left is not 0 or n-1, if that is the case then for every remaining blank there is only 1 choice.If leftmost digit is n-1 then there is only one configuration possible.
    now add (n-2)(n-1) cases to get the answer

    ReplyDelete
  2. is the answer 2^(n + 1) - n - 2.
    I did it by considering for starting digit how many numbers are possible and then by adding for all the possible starting digits

    It was a bit lengthy

    ReplyDelete
  3. Let the symbols in base n be s[0],s[1]...s[n-1]
    Since all digits are to be distinct, therefore the number of digits in any number in solution set has to be <=n. So we will count number of solutions of each length and sum up.

    If the length if L (1<=L<=N), and the smallest digit of the number N is s[i], then N must be a permutation of digits s[i] to s[i+L-1] only; because if an intermediate digit s[k] was missing in N, then the occurance condition of digits just smaller and just larger than s[k] in N (that it must occur first in number of must have some parent with +1 or -1) will clash at the starting digit of N.
    Thus for length L, N-L+1 selections are possible, and the problem reduces to : "How many permutations of P={1,2,3...L} satisfy the condition that except for the leftmost number, every number differs by +1 or -1 from some number further to the left"

    And this problem can be solved fairly easily. Let i (1<=i<=L) be the first digit in a permutation. Then consider chains C1=i+1,i+2,i+3...L and C2=i-1,i-2,i-3...3,2,1
    Then in both chains, the previous digit has to come before the next one to satisfy the occurance constraint. This is simply the count of selecting |C1| positions from |C1|+|C2| (which is equal to L-1) positions and arranging both chains in order; which is C(|C1|+|C2|,|C1|) [where C(a,b) = combinatorial coefficient $^aC_b$ ]
    If i is starting number, there are C(L-1,L-i) ways. Summing for 0<=i<=L we get 2^(L-1)

    Since L length had (N-L+1) selections, there are (N-L+1)*(2^(L-1)) number for length L
    Summing for all lengths 1<=L<=N, we get : COUNT = 2^(N+1)-N-2

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. I think the solution given above is partially correct except that, the numbers in base N starting with 0 are also counted. For base N numbers there can be only N numbers which start with 0. Subtracting that from the count gives the correct answer - 2( 2^N - N + 1 ).

    ReplyDelete
  6. add 1 to my previous solution to include the case 0

    ReplyDelete
  7. In base n, the length of number may be 1, 2, 3, 4, ..., n

    Lemma 1: Number of n digit numbers that are formed using distinct digits from 0 to n-1 using each digit exactly once is 2^(n-1)
    Proof: Consider the last digit, convince yourself to the fact that the only two possibilities for the last digit are the numbers 0 and n-1. Then, proceeding in this manner, we have 2*2*2*...*2 = 2^(n-1) different numbers.

    Lemma 2: Numbers of length k following above constraint contain digits that are consecutive i.e. a k length number following above constraint will have k consecutive digits (0--k-1 or 1--k or ...)
    Proof: Take any valid sequence. Let m denote the minimum element and M denote the maximum element.
    Now, case1: M is not the first element, in which case M-1 has to be in the sequence
    case2: M is the first element, then at some position before m, m+1 has to be present, before which m+2 should be present. Continuing in this manner, we prove that M-1 has to be present at some position. Similarly using induction, we can prove that all numbers in the range m to M has to be present in the sequence.

    Proof: So, we sum over all k length sequences
    Now, one more thing has to be taken into account. If the k continuous numbers does not contain a '0', then number of k digit numbers will be 2^(k-1). IF the k continous digit numbers contain a '0', then number of k digit numbers will be 2^(k-1)-1 because 0 is not allowed to be at first position, which is possible in only one valid sequence
    So, at k digits, the number of valid sequences would be (n-(k-1))*2^(k-1) + 2^(k-1)-1
    So, we have summation of (n-(k-1))*2^(k-1) + 2^(k-1)-1 over k = 1 to n which is
    2^(n+1) - (n+2) + 2^(n) - 1 - n = 3*2^n -2n -3

    ReplyDelete
  8. Surprise! No correct solution. Someone should please improve the solution if my explanation is not good enough. Thanks

    Correct answer: 2^(n+1)- 2n - 2

    Solution:
    We apply a double recursion. Let a_n denote the number of suitable base n representations. Now we consider the suitable base (n+1) representations. These representations can be put into two disjoint classes:
    a) digit n is not in the representation; so this representation is also a suitable representation in base n
    b) digit n is the representation

    Assume that there are b_(n+1) suitable representations in the second class.

    Then a_(n+1) = a_(n) + b_(n+1)

    Its easy to show that b_(k+1) = 2^(k+1) - 2 (*Appendix)

    Solving the recurrence relation since a(2) = 2:
    a(n) = 2^(n+1) - 2n - 2
    Solution Completed.

    Appendix:
    TPT: b_(n+1) = 2^(n+1) - 2

    Outline:
    1) Consider the numbers in the set that consists of k digits exactly. Prove that those digits would be n, n-1, n-2, .. n-k+1
    2) The two sets corresponding to k digit numbers in b_(n+1) and b_n are really the "isomorphic" (shift digits by 1). So, in summation, only the number of numbers with n+1 digits are left.
    3) The number of numbers with n+1 digits in the set represented by b_(n+1) is 2^n
    Hence, b_(n+1) = b_(n) + 2^n and b_2 = 2
    Solving, b_(n+1) = 2^(n+1)-2


    ReplyDelete