0
$\begingroup$

I have two questions here, with the first one concerning a solved example, while the second concerns possible constraints for $k$ given $n$.

1 . It is given in a solved problem in book titled Combinatorics, A guided Tour, by David Mazur that for a circular lock with $30$ digits from $0-29$, the possible values for a $4$ digit combination is: $30*27*27*27$.
For the first digit, the number of choices is obvious; & for the second the choices are :
=> $30$ - (the chosen first digit) - (two digits adjacent to the chosen first digit)
=> $27$
It is given that the choices for the 3rd digit are : $27$

I am unable to understand how the choices are $27$ for third digit. For me, it should :
$30$ - (two existing choices) -(either $3$ or $4$ adjacent digits) => either $25$ or $24$ choices

Similarly, it is given that the choices for the 4th digit are : $27$, which is not understandable at all too.

2 . The second question arose in my attempt to have a smaller example to understand the given solution. I took lock with $9$ digits from $0-8$ & combination of $3$ digits. I took the first digit as $0$, second one is having $7$ choices from $1-7$, while the third digit's choices vary with the actual second digit chosen.
Say, if the second digit is $2$, the choices available for the 3rd digit: $4,5,6,7$; while for the second digit of $3$, the choices available are : $5,6,7$.

So, my small example is not even getting a consistent value for the number of choices for the 3rd digit.

This makes me think that may be for $n=8$, the value of $k=3$ is too high.

So, in the given circular lock of $n$ digits, is there a bar on the number of combination digits ($k$) with the stated constraints.


Update - for 2nd question : The modification made in light of responses is shown below:

Say, if the second digit is $2$, the choices available for the 3rd digit: $0, 4,5,6,7,8$ --or $6$ choices; while for the second digit of $3$, the choices available are : $0,1,5,6,7,8$ --or $6$ choices.

So, effectively my second question is solved. enter image description here

$\endgroup$
  • 1
    $\begingroup$ A combination lock of this type does not allow adjacent digits to be identical or adjacent. A code of $5,10,10,2$ for example is not allowed since two $10$'s appear next to one another. A code like $5,10,5,2$ however is perfectly acceptable. You seem to be operating under the assumption that no entry may be equal or offbyone to any previous entry, but really we only care about the immediately preceding entry. $\endgroup$ – JMoravitz Sep 1 '18 at 14:18
  • $\begingroup$ @JMoravitz Nice catch, thanks a lot. So, third choice would be adjacent to either the 1st or the 2nd choice; & hence cannot have either one ($k=1, k=2$) & the two adjacent to that (i.e., to either $k=1$ or $k=2$). Similarly, the 4th choice would be adjacent to only one of the earlier three. But, my second question is unsolved still; & my approach comes near to it too; i.e. if $n=8$, then it is possible that the choices available for $k=3$ varies with the actual digit chosen for $k=2$. $\endgroup$ – jiten Sep 1 '18 at 14:27
  • $\begingroup$ Please give reason for downvote. Thanks in anticipation. $\endgroup$ – jiten Sep 1 '18 at 14:39
  • $\begingroup$ Even after the latest update you have not stated the second question. $\endgroup$ – Ross Millikan Sep 1 '18 at 15:06
  • $\begingroup$ @RossMillikan Please see the modified Update for the 'changed' second question. $\endgroup$ – jiten Sep 1 '18 at 15:11
1
$\begingroup$

In general, for such circular lock with $n$ digits and with the properties that consecutive digits in the password of length $k$ can't share the same digit as well as the neighboring digits.

For the first number, there is no restriction so there are $n$ options.

For the remaining $k-1$ digits, they have to avoid the digit that the previous digit has just chosen and also to avoid their neighbors, hence each of them have $n-3$ options.

Hence the general formula should be $n \cdot (n-3)^{k-1}$.

$\endgroup$
  • $\begingroup$ Please tell where I am wrong in getting $5$ choices in my Update with my small example of $n=8, k=5$ for the third digit; i.e for the second digit being $3$. $\endgroup$ – jiten Sep 1 '18 at 15:05
  • 1
    $\begingroup$ you miss out $0$. $\endgroup$ – Siong Thye Goh Sep 1 '18 at 15:14
0
$\begingroup$

The photo is too small for me to read, but for the first I would assume the restriction is that no number in the combination can be the same as or next to the previous one. That would say a combination like $1,13,1,12$ is acceptable. You are assuming the initial $1$ rules out $1,2,3$ for all future positions, but the factor $27$ says this is not the case.

For the second you don't quote the question or the book's result, so I can't help.

$\endgroup$
  • $\begingroup$ Please click on the image, & then again click for expanding it. $\endgroup$ – jiten Sep 1 '18 at 14:22
  • $\begingroup$ My second question is shown clearly in response to comment by @JMoravitz. $\endgroup$ – jiten Sep 1 '18 at 14:31
  • $\begingroup$ I still don't see the second question. It is hinted that you are assuming each number must be at least one away from all previous numbers and asking how many numbers can be chosen, In that case the most numbers you can choose is half, where you choose every other one like all the evens. You can run out at one third where you choose multiples of three because there isn't room for another. $\endgroup$ – Ross Millikan Sep 1 '18 at 14:43
  • $\begingroup$ Please see the modified Update for the 'changed' second question. $\endgroup$ – jiten Sep 1 '18 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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