2
$\begingroup$

Given a whole number N..

Arrange 1 to N in a sequence such that no two numbers have their average sitting between them...

Note - If N=20.. average of 19 and 2 = 10.5 is not a whole number .. hence we do not need to worry about such numbers and their averages.. In other words, if average of two numbers is not a whole number.. we assume that their average does not exist in the list 1 to N..

$\endgroup$
7
  • 3
    $\begingroup$ When you say 'sitting between them' do you mean that the two are one item apart with the one item in between them being their average? Or do you mean that for any $s_i, s_j$ if $s_k=\frac12(s_i+s_j)$ then we shouldn't have $i\lt k\lt j$? $\endgroup$ Aug 21, 2013 at 16:39
  • $\begingroup$ It means.. for any si,sj if sk=1/2(si+sj) then we shouldn't have i<k<j $\endgroup$
    – abipc
    Aug 21, 2013 at 16:59
  • 2
    $\begingroup$ What does this have to do with computer science? Suggest migrating to math.stackexchange. $\endgroup$ Aug 21, 2013 at 17:06
  • 1
    $\begingroup$ @D.W. I suspect if this question were moved to math.SE they'd ask why it wasn't on cs; at its heart the question is asking about a construction, an algorithm, much more than it's asking about any mathematical structure. To me this is akin to e.g. a question about topological sorting, but possibly even more pragmatically oriented. $\endgroup$ Aug 21, 2013 at 19:57
  • 3
    $\begingroup$ My rough guideline for 'is a question (in)appropriate for cs.SE?' is 'would this feel out of place in e.g. Knuth or Sedgewick?'; questions that are about structures or operations upon them, essentially. This feels like such a 'structural' question to me. $\endgroup$ Aug 21, 2013 at 19:59

2 Answers 2

5
$\begingroup$

Here's a simple recursive construction for the more restrictive version of the problem. First of all, note that the average of an odd number and an even number is never a whole number; if $a=2i-1$ and $b=2j$, then $\frac12(a+b)=i+j-1+\frac12$. This means that if we put the $\lceil N/2\rceil$ odd numbers $a_i$ first (in some as-yet-to-be-determined order) and then the $\lfloor N/2\rfloor$ even numbers $b_j$ (likewise, in some as-yet-to-be-determined order), then we can be guaranteed that the average of a $a_i$ and a $b_j$ can never be between them (because it'll never be a whole number), so we've split the problem into two subproblems: one for the set of odd numbers $a_i$ and one for the set of even numbers $b_j$.

But note now that if we have two odd numbers $a_m=2m-1$ and $a_n=2n-1$, then their average is $2\left(\frac{m+n}2\right)-1$, and so the subproblem of 'sorting' the $a_i$ correctly is exactly the same as sorting the numbers $c_i\in 1\ldots n$, where $c_i=\frac{a_i+1}{2}$ and $n=\lceil N/2\rceil$; a similar result holds true for the even numbers $b_j$. This means that we can keep applying the same procedure to both of these groups recursively. For instance, when $N=8$ this construction produces the ordering $15372648$. Note that if we subtract one from these values and look at the numbers $0\ldots(N-1)$, then this ordering is $04261537$; looking at the bit patterns for these numbers ($000, 100, 010, 110, 001, 101, 011, 111$) shows that they're just the bit patterns of the numbers $0\ldots 7$, reversed! This 'bit reversal' shuffle is used by Fast Fourier Transform (FFT) algorithms to correct the output ordering of their data (see, for instance, http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html ).

In fact, this construction shows that there are at least $O(2^{N/2})$ such orderings, since at each of the $N/2$ 'internal' nodes we can choose to either put the odd or the even numbers first without spoiling the result. These don't exhaust all of the orderings, though; for instance, we can exchange $2$ and $7$ in the constructed $N=8$ ordering to get the ordering $15327648$ which also clearly satisfies the constraint but can never be constructed by this procedure (since odd and even numbers are 'intermingled'). I don't know how many of the $N!$ orderings of $1\ldots N$ actually satisfy the problem.

$\endgroup$
6
  • $\begingroup$ +100? eh? Let me try my best to come up with an algorithm.. i will google as well.. $\endgroup$
    – abipc
    Aug 21, 2013 at 17:29
  • $\begingroup$ marking it as correct .. because it gives me a BIG idea to work towards the algo.. $\endgroup$
    – abipc
    Aug 21, 2013 at 17:30
  • $\begingroup$ @Steven.. Can we say that the solution is any ordering such that no triplet (any 3 numbers in the sequence) is an AP? $\endgroup$
    – abipc
    Aug 21, 2013 at 17:44
  • $\begingroup$ @abipc I would instead have said that that's another way of defining the problem. $\endgroup$ Aug 21, 2013 at 17:57
  • $\begingroup$ :) rightly..although it did give me something to think about.. $\endgroup$
    – abipc
    Aug 21, 2013 at 18:01
0
$\begingroup$

An algorithm to make sure that no three numbers(anywhere in the sequence) are in AP, which will yield the answer -

Given N
start with array A[] = 1, 2.. N-1, N (AP with diff = 1)
Split A into two APs (with diff =2) A1 and A2 so that no triplet (2 terms in A1 and 1 term in A2 or 2 terms in A2 and 1 term in A1) are in AP.
Apply the same logic on A1 and A2 (now for AP with diff=4 and so on) recursively
Do this until the splitted sequences have a length atmost 2.
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.