veronica1999 said:
I have been working on this problem for a while and I am stuck,
Can I get some hints pls?
Thanks.
Hi veronica1999, :)
The number 1 should appear somewhere in the list. If 1 is the first number on the list, the list can only be written in one particular way under the given criteria. That is, \((1,2,3,4,5,6,7,8,9,10)\).
Suppose 1 appear at the \(k^{\mbox{th}}\) position of the list where \(k\neq 1\). Then 2 should precede 1. If 2 is not the 1st number, 3 should precede 2 and so on. Further suppose that \(n\) is the 1st number on the list and \(m\) be the maximum number that precedes 1. If \(m\) is not in the first position of the list(that is \(n\neq m\)) then \(m-1\) should precede \(m\), if \(m-1\) is not in the first position \(m-2\) should precede \(m-1\) and so on. This continues until \(m-i=n\) for some \(i=1,2,\cdots,m-2\). Therefore, \(k=m\).
In other words if you have 1 at the \(k^{\mbox{th}}\) position you have all the numbers upto \(k-1\) preceding 1.
Also you can see that according to the given criteria if \(k\neq 10\) number at the \((k+1)^\mbox{th}\) position should be, \(k+1\). If \(k+1\neq 10\) then the number at the \((k+2)^\mbox{th}\) position should be \(k+2\) and so on. This continues until \(k+j=10\) for some \(j=0,2,\cdots,8\).
So we only have to count the number of arrangements that could be made by the numbers that precedes 1. This is the number of arrangements that could be made from the situation where 1 is at the \(k^\mbox{th}\) position.
Also it can be seen according to the above discussion that, 2 or \(k\) should be at the \((k-1)^\mbox{th}\) position of the list.
Case 1: If \(k\) is at the \((k-1)^\mbox{th}\) position of the list then 2 or \(k-1\) should be at the \((k-2)^\mbox{th}\) position of the list.
Case 2: If \(2\) is at the \((k-1)^\mbox{th}\) position of the list then 3 or \(k\) should be at the \((k-2)^\mbox{th}\) position of the list.
Arguing in a similar fashion we can see that, every position before the \(k^\mbox{th}\) position up to the 2nd position can have two different values. Finally the remaining number can be put into the first position.
Therefore the number of arrangements when 1 is at the \(k^\mbox{th}\) position is, \(2^{k-2}\) where \(k=2,3,4,5,6,7,8,9,10\).
Summary:
1) If 1is the first number on the list\((k=1)\), then the list can be arranged in one way. That is, \((1,2,3,4,5,6,7,8,9,10)\).
2) There are \(2^{k-2}\) lists with 1 at the \(k^\mbox{th}\) position where \(k=2,3,4,5,6,7,8,9,10\).
Therefore the total Number of arrangements\( = 1+2^0+2^1+2^2+2^3+\cdots+2^8=512\)
Kind Regards,
Sudharaka.
