Help Needed: Solving a Stat Question with No Breaks

[JonF]

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.

 

[rachmaninoff]

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?

 

[JonF]

I have no clue what a Hamiltonian path is, please explain.

 

[EnumaElish]

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.

 

[rachmaninoff]

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.

To simplify matters, I'd start with...

Too much simplification.

 

[Antiphon]

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!

 

[vsage]

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

 

[Zurtex]

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:

 

[EnumaElish]

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].

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! 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.

 

[vsage]

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:

 

[rachmaninoff]

If you have x number of vertices, how many of them can be connected by a drawn line without a pencil being lifted?

You're thinking of planarity - it's not the same as Hamiltonian or Eulerian path existence.

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.

Actually 1,000,002.

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}

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

These 300 vertices I envision, when completely connected, as forming a 300-simplex.

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.

 

[Zurtex]

Actually 1,000,002.

Doh! You are right.

 

[EnumaElish]

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

That's the answer I came up with, now you've confirmed that I'm one of the best. 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?

 

[rachmaninoff]

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 existence of such a path without naming it explcitly (I haven't figured it out yet, of course).

 

[LeonhardEuler]

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.

 

[rachmaninoff]

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.

 

[LeonhardEuler]

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.

 

[bao_ho]

0001002003004005006007008009011012013014015016017018019021022023024025026027028029031032033034035036037038039041042043044045046047048049051052053054055056057058059061062063064065066067068069071072073074075076077078079081032083084085086087088089091092093094095096097098099111211311411511611711811912212312412512612712812913213313413513613713813914214314414514614714814915215315415515615715815916216316416516616716816917217317417517617717817918218318418518618718818919219319419519619719819922232242252262272282292332342352362372382392432442452462472482492532542552562572582592632642652662672682692732742752762772782792832842852862872882892932942952962972982993334335336337338339344345346347348349354355356357358359364365366367368369374375376377378379384385386387388389394395396397398399444544644744844945545645745845946546646746846947547647747847948548648748848949549649749849955565575585595665675685695765775785795865875885895965975985996667668669677678679687688689697698699777877978878979879988898999

find any three digit number

 

[bao_ho]

000100200300400500600700800901101201301401501601701801902102202302402502602702802903103203303403503603703803904104204304404504604704804905105205305405505605705805906106206306406506606706806907107207307407507607707807908103208308408508608708808909109209309409509609709809911121131141151161171181191221231241251261271281291321331341351361371381391421431441451461471481491521531541551561571581591621631641651661671681691721731741751761771781791821831841851861871881891921931941951961971981992223224225226227228229233234235236237238239243244245246247248249253254255256257258259263264265266267268269273274275276277278279283284285286287288289293294295296297298299333433533633733833934434534634734834935435535635735835936436536636736836937437537637737837938438538638738838939439539639739839944454464474484494554564574584594654664674684694754764774784794854864874884894954964974984995556557558559566567568569576577578579586587588589596597598599666766866967767867968768868969769869977787797887897987998889899900

 

[bao_ho]

i also have an algorithm for the 1million&2 digit sequence. i need someplace to upload a 1,000,002 Byte file.

 

[bao_ho]

make that 2,000,006 Bytes

 

[rachmaninoff]

What's your algorithm?

 

[bao_ho]

<html>
<head>
<script>
dec = ["00","01","02","03","04","05","06","07","08","09",
"10","11","12","13","14","15","16","17","18","19",
"20","21","22","23","24","25","26","27","28","29",
"30","31","32","33","34","35","36","37","38","39",
"40","41","42","43","44","45","46","47","48","49",
"50","51","52","53","54","55","56","57","58","59",
"60","61","62","63","64","65","66","67","68","69",
"70","71","72","73","74","75","76","77","78","79",
"80","81","82","83","84","85","86","87","88","89",
"90","91","92","93","94","95","96","97","98","99"];


for(a = 0; a<=99; a++)
{
str = "," + dec[a];
for(b = a; b<=99; b++)
{
for(c = a+1; c<= 99; c++)
{
str += "," + dec[a] + "," + dec + "," + dec[c];
}
}
document.write(str);
}
document.write(",00,00");
</script>
</head>
</html>

 

[bao_ho]

http://geocities.com/bao_ho/digitalsafe.zip << here's the txt sequence in zip format
this account has daily bandwidth limit.

 

[bao_ho]

btw, there are 99! of these combinations

 

[bao_ho]

or is it factorial(100) ?

 

[JonF]

could we think of each entry as a 6 digit number, use bao_ho method, then count the number of characters and subtract 3?

 

[Townsend]

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.

Is repitition allowed? For example could I enter 00,00,00 for the first three numbers?

 

[bao_ho]

could we think of each entry as a 6 digit number, use bao_ho method, then count the number of characters and subtract 3?

come again?

 

[JonF]

bao_ho: Another way to think of the input is as a 6 digit number, so if you generated a list like yours and you entered all the numbers on it that would give you all possible combos without any repeats. I don’t know why I was thinking of subtracting 3 last night. So the total number of numbers you would have to enter is the numbers that algorithm would generated for a 6 digit number?


Townsend:repitition is allowed