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!
i have not worked out the exact answer but it can be solved in following way:
ReplyDeletechoose 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
is the answer 2^(n + 1) - n - 2.
ReplyDeleteI 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
Let the symbols in base n be s[0],s[1]...s[n-1]
ReplyDeleteSince 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
This comment has been removed by the author.
ReplyDeleteI 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 ).
ReplyDeleteadd 1 to my previous solution to include the case 0
ReplyDeleteIn base n, the length of number may be 1, 2, 3, 4, ..., n
ReplyDeleteLemma 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
Surprise! No correct solution. Someone should please improve the solution if my explanation is not good enough. Thanks
ReplyDeleteCorrect 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