There are 365 cards with 365 different numbers. Each step, we can choose 3 cards $a_{i},a_{j},a_{k}$ and we know the order of them (examble: $a_{i}<a_{j}<a_{k}$). With 2000 steps, can we order 365 cards from smallest to biggest??
Problem
Source:
Tags: combinatorics, combinatorics unsolved, algorithm
29.06.2016 14:15
Suppose that there are $n$ numbers in a sorted list, where $n<365$. Then there would be $n+1$ locations for a new number. Try proving that you would need $\lceil \log_3 (n+1) \rceil$ steps to find the location of the new number.
29.06.2016 15:54
d__ wrote: Try proving that you would need $\lceil \log_3 (n+1) \rceil$ steps to find the location of the new number. Nice! I think the idea to do this one is the same as binary search algorithm. Let $a$ be the position of the new number in the sorted list. We need to find $a$. Here is an algorithm to do that: 1) In the range $[ 1,n+1]$, pick a new number and two known numbers which are in position $\lceil \tfrac 13 (n+1) \rceil$ and $\lceil \tfrac 23 (n+1) \rceil$ in the sorted list. 2) If $a< \lceil \tfrac 13 (n+1) \rceil$ then perform 1) in the range $\left [ 1, \lceil \tfrac 13 (n+1) \rceil \right )$. Similarly to the case $\lceil \tfrac 13 (n+1) \rceil < a < \lceil \tfrac 23 (n+1) \rceil$ and $n+1 \ge a>\lceil \tfrac 23 (n+1) \rceil$. This will gives us at most $\lceil \log_3 (n+1) \rceil$ steps to locate new number. Hence, for $265$ cards, we can do at most $$\sum_{i=2}^{365} \lceil \log_3 (i+1) \rceil=1+2(3^2-3)+3(3^3-3^2)+4(3^4-3^3)+5(3^5-3^4)+6(365-3^5)=1825.$$So it is possible to order $365$ cards with $2000$ steps.
29.06.2016 17:46
why we have it?? $$\sum_{i=2}^{365} \lceil \log_3 (i+1) \rceil=1+2(3^2-3)+3(3^3-3^2)+4(3^4-3^3)+5(3^5-3^4)+6(365-3^5)=1825.$$I think this is wrong!
30.06.2016 00:41
ductiena1k43 wrote: why we have it?? $$\sum_{i=2}^{365} \lceil \log_3 (i+1) \rceil=1+2(3^2-3)+3(3^3-3^2)+4(3^4-3^3)+5(3^5-3^4)+6(365-3^5)=1825.$$I think this is wrong! Here is how I calculate it. Let $f(x)= \lceil \log_3 x \rceil$. From $3$ to $365$: There are $1$ number ($3$ exactly) that has $f(x)=1$. $3^2-3$ numbers (from $4$ to $9$) that has $f(x)=2$. $3^3-3^2$ numbers (from $10$ to $3^3$) that has $f(x)=3$. $3^4-3^3$ numbers (from $3^3+1$ to $3^4$) that has $f(x)=4$. ... $365-3^5$ numbers (from $3^5+1$ to $365$) that has $f(x)=6$.
30.06.2016 01:55
I know that . But I think $f(4)=1,f(5)=1,...$ However, the answer is 1825 is right. Tell me why?????
30.06.2016 02:30
ductiena1k43 wrote: I know that . But I think $f(4)=1,f(5)=1,...$ However, the answer is 1825 is right. Tell me why????? This is a ceiling function $\lceil \rceil$, not floor function $\lfloor \rfloor$ so $f(4)=2,f(5)=2$.
30.06.2016 02:54
Another question: How would you go about proving that you can't do it with 1824 steps?