Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -

Unique Codes


Best Answer m00li, 27 April 2014 - 01:05 PM

Spoiler for Still struggling with it but

EDIT: the last term for F(n) should read n-[n/2]C[n/2]f(n-[n/2]) where [k] is the max integer <=k

Go to the full post


  • Please log in to reply
13 replies to this topic

#11 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1427 posts
  • Gender:Male

Posted 27 April 2014 - 04:21 PM

Spoiler for partial solution
It looks like it's heading towards DrXP's solution, but I can't tell for sure.
  • 0

#12 m00li

m00li

    Junior Member

  • Members
  • PipPip
  • 71 posts

Posted 29 April 2014 - 11:12 PM

I still think the correct answer for n digit string is given by 

= nC0f(n) + n-1C1f(n-1) + n-2C2f(n-2) + n-3C3f(n-3) + ......    +  n-[n/2]C[n/2]f(n-[n/2]) 
putting n = 10, we get F(10) = 3349507;
where f(n) = (subfactorial(n+1))/n
 
I wrote a vba code to do the simulation and it confirms the answer too. The values for first few n's are:
 
n F(n) 3 5 4 21 5 106 6 720 7 4547 8 36696 9 332769 10 3349507
 
 
Here's the vba code:
 
 
Dim arrlen As Integer
Dim counter As Long
Sub randomd()
j = 1
position = 1
counter = 0
Dim i_arr As Variant
i_arr = Array(1, 3, 7, 4, 10, 6, 8, 2, 9, 5)
arrlen = UBound(i_arr) + 1
ReDim Preserve i_arr(1 To arrlen)
Call perm(ByVal i_arr, j, ByVal position)
Sheet2.Cells(1, arrlen + 1) = counter
End Sub
 
Sub perm(ByVal i_arr, ByRef j, ByVal position)
For i = position To arrlen
    temp = i_arr(position)
    i_arr(position) = i_arr(i)
    i_arr(i) = temp
    If position = arrlen Then
    'For k = 1 To position: Sheet2.Cells(j, k) = i_arr(k): Next k
    satisfies = True
    k = 3
    While satisfies And k <= arrlen
    If i_arr(k) - i_arr(k - 1) = 1 And i_arr(k - 1) - i_arr(k - 2) = 1 And satisfies Then satisfies = False
    k = k + 1
    Wend
    If satisfies Then counter = counter + 1
    j = j + 1
    End If
    Call perm(ByVal i_arr, j, ByVal position + 1)
Next i
End Sub

  • 0

#13 m00li

m00li

    Junior Member

  • Members
  • PipPip
  • 71 posts

Posted 30 April 2014 - 06:06 AM

 

I still think the correct answer for n digit string is given by 

= nC0f(n) + n-1C1f(n-1) + n-2C2f(n-2) + n-3C3f(n-3) + ......    +  n-[n/2]C[n/2]f(n-[n/2]) 
putting n = 10, we get F(10) = 3349507;
where f(n) = (subfactorial(n+1))/n
 
I wrote a vba code to do the simulation and it confirms the answer too. The values for first few n's are:
 
n                             F(n)
3                              5
4                             21
5                           106
6                           643 
7                        4547
8                      36696
9                    332769
10                3349507
 
 
Here's the vba code:
 
 
Dim arrlen As Integer
Dim counter As Long
Sub randomd()
j = 1
position = 1
counter = 0
Dim i_arr As Variant
i_arr = Array(1, 3, 7, 4, 10, 6, 8, 2, 9, 5)
arrlen = UBound(i_arr) + 1
ReDim Preserve i_arr(1 To arrlen)
Call perm(ByVal i_arr, j, ByVal position)
Sheet2.Cells(1, arrlen + 1) = counter
End Sub
 
Sub perm(ByVal i_arr, ByRef j, ByVal position)
For i = position To arrlen
    temp = i_arr(position)
    i_arr(position) = i_arr(i)
    i_arr(i) = temp
    If position = arrlen Then
    'For k = 1 To position: Sheet2.Cells(j, k) = i_arr(k): Next k
    satisfies = True
    k = 3
    While satisfies And k <= arrlen
    If i_arr(k) - i_arr(k - 1) = 1 And i_arr(k - 1) - i_arr(k - 2) = 1 And satisfies Then satisfies = False
    k = k + 1
    Wend
    If satisfies Then counter = counter + 1
    j = j + 1
    End If
    Call perm(ByVal i_arr, j, ByVal position + 1)
Next i
End Sub

 

 

EDIT: corrected the n:F(n) table above


  • 0

#14 plasmid

plasmid

    Senior Lolcat

  • VIP
  • PipPipPipPip
  • 1427 posts
  • Gender:Male

Posted 30 April 2014 - 03:30 PM

m00li's answer of 3349507 seems correct. I couldn't follow the VB code's logic for making permutations (a subroutine seems to be calling itself?) and I don't have MS Office, so I wrote a perl script to calculate it, and it gave the same answer.
 
#!/usr/bin/perl
use strict;
use warnings;

# The "implicit" starting permutation for this program to
# avoid copying any triplets from is
# 0 1 2 3 4 5 6 7 8 9
# since that makes programming easier.
# This will generate permuatations, see if any
# triplets appear in the permutation, and if not then
# print the permutation and increase the counter

my $counter = 0;

# This uses List::Permutor to generate permutations
# If you don't already have it installed, from the command
# prompt, run "cpan List::Permutor"
# (or run "cpan App::cpanminus" then "cpanm List::Permutor")

use List::Permutor;
my $permutor = List::Permutor -> new(0..9);
while (my @perm = $permutor -> next()) {
  # For each permutation, check for consecutive triplets
  # If there are no triplets, increase the counter and print
  # the permutation
  my $notriplets = 1;
  TRIPLETLOOP: for(my $triplet=0; $triplet<8; $triplet++) {
    if(($perm[$triplet] == $perm[$triplet+1]-1) &&
       ($perm[$triplet] == $perm[$triplet+2]-2)) {
      $notriplets = 0;
      last TRIPLETLOOP;
    }
  }
  if($notriplets) {
    print "Permutation " . ++$counter . ": @perm\n";
  }
}
print "Found $counter permutations with no triplets\n";
I also couldn't understand post 10 at first, but now it seems to make sense.
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users