1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Counting, kinda

  1. Jul 18, 2005 #1
    Here and stat question I can’t seem to get, probably because I’ve never taken a stats class so any suggestions would be welcome.

    If there is a digital safe, that takes 3 inputs from 00-99. How many numbers would you have to enter to try every possible combination. But here is the catch; there are no break points.

    So for example if you entered 23,75,01,28,52 you would have entered the combinations: 23,75,01 and 75,01,28 and 01,28,52.

    I have no clue how to do this.
  2. jcsd
  3. Jul 19, 2005 #2
    What I'm thinking of first is the directed multigraph with the 1,000,000 possible 3-input sequences as vertices, and directed edges from each (A-B-C) vertex to the corresponding (B-C-D) vertices (representing the four-input sequence, A-B-C-D, which gives two three-vertex sequences). Perhaps this graph has a Hamiltonian path or circuit? I'm not sure; a simpler case, with inputs of only 0 or 1 (hence 2^3=8 possible sequences), has a Hamiltonian path:

    0001110100 (10 inputs, 8 sequences):
    (000, 001, 011, 111, 110, 101, 010, 100)

    Maybe you can use some kind of induction?
  4. Jul 19, 2005 #3
    I have no clue what a Hamiltonian path is, please explain.
  5. Jul 21, 2005 #4


    User Avatar
    Science Advisor
    Homework Helper

    To simplify matters, I'd start with a safe that is opened by one of the combinations: {000,001,010,011,100,101,110,111} and a keypad that has two keys, [0] and [1]. Now ask the same question.

    I might write back again as I think about this and there is a light.
  6. Jul 22, 2005 #5
    JonF - some maybe useful information is here.

    The best case would be that no sequences need be repeated, in which case you'd need 1,000,002 inputs.

    Too much simplification. :smile:
  7. Jul 22, 2005 #6
    This is tricky.

    You want to form the shortest overall sequence which contains all possible triples
    from a basis size of 100.

    For the two-symbol two-token problem the brute-force solution is:

    AA, AB, BA, BB -> AABBA

    ... Oh blast. I'm an EE not a statisitcian!
  8. Jul 22, 2005 #7
    I see this problem similarly to rachmaninoff, although my methods of thought are probably more uncouth because I'm not well-read in math. In any case, this problem seems analogous to: If you have x number of vertices, how many of them can be connected by a drawn line without a pencil being lifted? Of course that is the case for 2-inputs, and your question would involve points being connected into triangles. Hopefully I will think of something less redundant to say when I get time to think about this, although rachmaninoff might have given the answer
    Last edited by a moderator: Jul 22, 2005
  9. Jul 22, 2005 #8


    User Avatar
    Science Advisor
    Homework Helper

    Well to start off with the we know that 999'998 is a lower bound for the amount of numbers you have to type in. Perhaps if you came up with an algorithm that generated all combinations you'd have an upper bound and you could take it from there :uhh:
  10. Jul 22, 2005 #9


    User Avatar
    Science Advisor
    Homework Helper

    Let {i, ii, iii, iv, v, vi, vii, viii} = {000, 001, 010, 011, 100, 101, 110, 111}.

    So it looks like you need at most 3 zeroes in a row and at most 3 ones in a row: 000111 will take care of i, viii, ii, iv. Great progress! :smile: Now append 01; this also covers vi (last 3 digits of 00011101) and vii (last 3 but 1 digit). Appending a zero covers iii (last 3 digits of 000111010). Yet another zero and v is covered (last 3 digits of 0001110100). I am nowhere near a formulaic representation, though.
  11. Jul 22, 2005 #10
    I think I may be onto something. Mathworld had a nice tidbit at http://mathworld.wolfram.com/HamiltonianGraph.html stating that all platonic solids have a hamiltonian path. I can only conjecture that a hamiltonian path can be represented as lines connected by a common vertex, triangles connected by a common side, tetrahedrons connected by a common face, etc.

    The problem can be visualized by thinking of all the possible combinations as 300 vertices floating in space, numbered in such a way that a triangle formed between 3 of the points would represent one combination of the safe. These 300 vertices I envision, when completely connected, as forming a 300-simplex. Given Pascal's Triangle's ability to completely describe the construction of an n-simplex via its n+1'th row (for example the 2nd element gives the number of vertices it should contain, 3rd element the number of sides, 4th the number of faces, etc), I believe the answer should be found somewhere around the 301st row of Pascal's Triangle.

    I have a tendency to go off on huge tangents though, so this idea may be just plain wrong. :tongue:
  12. Jul 22, 2005 #11
    You're thinking of planarity - it's not the same as Hamiltonian or Eulerian path existance.

    Actually 1,000,002.

    Was already done in post #2 - takes 10 inputs in the best case.

    Seems right - but I don't follow the Pascal argument following it. Just to be clear - you're using inputs as vertices (I was using sequences) - makes a big difference.
  13. Jul 22, 2005 #12


    User Avatar
    Science Advisor
    Homework Helper

    Doh! You are right.
  14. Jul 22, 2005 #13


    User Avatar
    Science Advisor
    Homework Helper

    That's the answer I came up with, now you've confirmed that I'm one of the best. :smile: What is a Hamiltonian path, though? Can't have anything to do with a Hamiltonian matrix (a matrix of 2nd derivatives, if my memory serves), can it?
  15. Jul 22, 2005 #14
    A Hamiltonian path is just a way to traverse a graph going through each vertex exactly once. If the vertices are the sequences AaBbCc, and the edges connect potentially "consequtive" sequences like AaBbCc--BbCcDd, then a Hamiltonian path would give you a sequence of inputs AaBbCcDdEe...Zz which gives every 3-input sequence without repeating. This would give you 1000000 sequences with 1000002 successive inputs 'Nn'. This could be useful, because you could potentially prove the existance of such a path without naming it explcitly (I haven't figured it out yet, of course).
  16. Jul 22, 2005 #15


    User Avatar
    Gold Member

    I just realized that proving the existence of a Hamiltonian path in the graph that represents this problem will not be enough to show that the minimum number of inputs is 2 + number of vertices. This is because the graph we are talking about is directed. For example, consider the case of a safe that takes a set of two numbers, and each of these numbers is either a zero or a one. The vertices can be represented by the ordered pairs (0,0); (0,1); (1,1); (1,0). In the graph an edge would be drawn between (0,0) and (0,1) because if the current state is (0,0), then an input of 1 will change the state to (0,1). However, if the current state is (0,1), no input will cause the next state to be (0,0). The arrows do not go both ways. In this particular case it is possible to make a Hamiltonian path that goes along the graph with the right direction every time, but there may be a case where a Hamiltonian path can be drawn in the undirected graph which would be impossible to translate into a code. We should either look for a new approach to this problem or deal with this complication somehow.
  17. Jul 22, 2005 #16
    I was under the impression that something we call a Hamiltonian path, defined on a directed graph, is in fact directed? Because an undirected 'path' on a directed graph would, as you show, often be useless.
  18. Jul 22, 2005 #17


    User Avatar
    Gold Member

    You're right. I forgot that Hamiltonian paths were defined on directed graphs as well. But still, the approach of proving the existence of a Hamiltonian path is more complicated than it seems because of the directedness of the graph.
  19. Jul 23, 2005 #18

    find any three digit number
  20. Jul 23, 2005 #19
  21. Jul 23, 2005 #20
    i also have an algorithm for the 1million&2 digit sequence. i need someplace to upload a 1,000,002 Byte file.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Counting, kinda
  1. Counting (Again) (Replies: 2)

  2. Silly kinda question. (Replies: 3)

  3. Its kinda difficult (Replies: 3)