MHB A Beginner's Guide to Starting a Project

[Ilikebugs]

I don't know where to startView attachment 6552

 

[topsquark]

So what do you get for "solving" one of these things? I think whoever helps you should get a cut.

-Dan

 

[Greg]

Hi Ilikebugs. Where do these problems come from?

 

[Ilikebugs]

my teacher puts it in a drive every week

 

[MarkFL]

my teacher puts it in a drive every week

I think to begin, I would imagine that Randi has the cards arranged in the same order she will seek them...for example suppose she will seek them in the order:

A B C D E F G H I J

and this is the order in which they are arranged. How many cards will she have to look at?

Next, imagine she will seek them in the same order as before, but this time they are arranged in the opposite orderr:

J I H G F E D C B A

How many cards will she have to look at?

Then, keeping the same order of seeking, but using at least two random orderings (not including the two orders previously checked), count how many cards she would have to look at. I recommend getting a deck of playing cards to conduct your trials.

What are your findings?

 

[Ilikebugs]

I got 2(2+4+6+8+10)=60

 

[johng1]

I don't have a proof yet, but I'm convinced that the answer for n cards is n(n+3)/2-1. So for n=10, the answer is 64. If I can come up with a proof, I'll post again. The computer verified the formula for values of n up to and including 10. For n=10, the value 64 is realized for initial
ordering of the cards ABCDEFGHIJ and search order BCDEFGHIJA; you can verify by hand that 64 "probes" are needed. Furthermore, the machine found that this is the only situation requiring 64 probes. This must lead to a proof, but I don't see it.

P.S. At first I thought as you did that the answer for n=10 cards is 60, but the machine convinced me otherwise.

 

[MarkFL]

I don't have a proof yet, but I'm convinced that the answer for n cards is n(n+3)/2-1. So for n=10, the answer is 64. If I can come up with a proof, I'll post again. The computer verified the formula for values of n up to and including 10. For n=10, the value 64 is realized for initial
ordering of the cards ABCDEFGHIJ and search order BCDEFGHIJA; you can verify by hand that 64 "probes" are needed. Furthermore, the machine found that this is the only situation requiring 64 probes. This must lead to a proof, but I don't see it.

P.S. At first I thought as you did that the answer for n=10 cards is 60, but the machine convinced me otherwise.

Interesting...I also thought 60 would be the maximum number too. (Thinking)

 

[Dethrone]

Here's a sketch for why 64 is the correct answer (procrastinating from studying for my exams...). If we think that the worse case scenario is when the cards are placed in position [1,2,3,4,5,6,7,8,9,10], and we search in the order [10,9,8,7,...], then that would yield 60. But, the true worse case scenario is when we search in the order [2,3,4,5,6,7,8,9,1], where the "first" element in the array is shifted $n$ times to the right, where $n$ is the size of the array. So, for $n$ cards, the answer is $n(n+1)/2-1$ + $n$.

 

[MarkFL]

Here's a sketch for why 64 is the correct answer (procrastinating from studying for my exams...). If we think that the worse case scenario is when the cards are placed in position [1,2,3,4,5,6,7,8,9,10], and we search in the order [10,9,8,7,...], then that would yield 60. But, the true worse case scenario is when we search in the order [2,3,4,5,6,7,8,9,1], where the "first" element in the array is shifted $n$ times to the right, where $n$ is the size of the array. So, for $n$ cards, the answer is $n(n+1)/2-1$ + $n$.

Yes, now it makes sense to me the think of the "worst case scenario" for $n$ cards (let's call this $W_n$) to be:

$$W_n=\sum_{k=2}^{n}(k)+n=\frac{n(n+1)}{2}-1+n=\frac{n^2+3n-2}{2}$$

This avoids the case where the desired card is in the leftmost position, but all other positions 2-10 are utilized and guarantees two occasions where the desired card is in the rightmost position. Basically, we can have all positions where positions 1-10 are realized, and because of swapping, we can replace the smallest (1) with the largest ($n$) to get the maximum, which you and John got with your orderings. (Yes)

edit: Interestingly, it appears that the best cast scenario $B_n$ is:

$$B_n=\sum_{k=1}^{n}(k)=\frac{n(n+1)}{2}$$

And that occurs when the cards are ordered in the seek order. And after all cards have been swapped during the best case trial, they are now in the order for the worst case if the same seek order is used. :D

 

[johng1]

I really didn't understand Mark's proof and have been stewing about the problem. I'm finally satisfied. For those of you who know programming, I include the program I wrote. The proof occurs as comment before method processPerm in class Permutation.

package permproblem;

public class Permproblem {

   public static void main(String[] args) {
      int n=10;
      Permutation b=new Permutation(n);
      b.generatePerms(n);
      
      System.out.println(b.maxProbes);
   }
   
}

package permproblem;

/* Given the array a with components 1..n in order and a permutation of 
   1..n perm, search the array a for perm[i], i=1..n.  Count the probes
   necessary for each search.  After each search is concluded with perm[i]
   foune at a[j], if j>0 swap the components a[j] and a[j-1].  The total number
   of probes for all the components perm[i] is counted.  Then the maximum
   number of probes for all permutations is n(n+3)/2-1.  This max occurs
   only for the permutation perm: 1 2 3 .. n-2 0.  Proof?  The program shows
   this is true for n up to 10.
*/
public class Permutation {
   int n;
   int[] perm;
   int[] a;
   boolean[] found;
   int maxProbes = 0;

   Permutation(int n1) {
      n = n1;
      perm = new int[n+1];
      a = new int[n+1];
      found=new boolean[n+1];
      int i;
      for (i = 1; i <= n; i++) {
         perm[i] = i;
      }
   }

/* for i=1 to n, searches for perm[i] in array a, initially for all i, a[i]=i.
   The number of probes (number of times a given component of a is examined)
   is counted.  Originally, if perm[i] is found at component j of a with j!=1,
   a[j] and a[j-1] are swapped.  However, if a[j-1] has already been found,
   this swap is not necessay for the counting of the number of probes.  So
   a boolean array found is maintained with a[k] true iff k has been 
   found.  So the swap is done only when a[j-1] has found[a[j-1]] false.  
   Count the number of swaps executed as moves; there is at most one move for
   each search for perm[i]. Then probes=n(n+1)/2+moves: the number of probes
   for perm[i] is i plus the number of times perm[i] has moved to the "right"
   in array a.  "Clearly" with this revision, there can be at most n-1 moves;
   when the search for perm[n] occurs the condition found[a[j-1]] is true.
   Finally then the maximum number of probes is n(n+1)/2+n-1=n(n+3)/2-1.  This
   maximum is achieved for perm equal to 2 3 4 ... n 1; as to why this is the
   only permutation with n-1 moves, I'm tired of thinking of the problem.
*/   
   void processPerm() {
      int i, m, j, probes = 0, moves = 0;
      for (i = 1; i <= n; i++) {
         a[i] = i;
         found[i] = false;
      }
      for (i = 1; i <= n; i++) {
         m = perm[i];
         found[m] = true;
         j = 1;
         while (j <= n && a[j] != m) {
            j++;
         }
         probes += j;
         if (j > 1 && !found[a[j - 1]]) {
            swap(a, j, j - 1);
            moves++;
         }
      }
      if (probes > maxProbes) {
         maxProbes = probes;
      }
   }

// merely swaps components b[i] and b[j]   
   void swap(int[] b, int i, int j) {
      int temp = b[i];
      b[i] = b[j];
      b[j] = temp;
   }
  
// "standard" recursive generation of all permutations of 1..n;  initial call
// has perm[i]=i for all i   
   void generatePerms(int n) {
      if (n == 1) {
         processPerm();
         return;
      }
      int i;
      for (i = n; i >= 1; i--) {
         if (i != n) {
            swap(perm, i, n);
         }
         generatePerms(n - 1);
         if (i != n) {
            swap(perm, i, n);
         }
      }
   }

 

[MarkFL]

I really didn't understand Mark's proof and have been stewing about the problem...

I didn't intend for my post(s) to be taken as any kind of proof, just my musings on the explanations given by others. :D