BrainDen.com - Brain Teasers
• 0

## Question

A set of 50-long vectors whose elements

are hexadecimal numbers is created as

follows:

```
1. A set is created containing exactly
one hex vector.
2. A vector V is randomly chosen from
the vectors already in the set.
3. A copy of V is made, call it W.
4. Independently of all of the other
elements of W, each element of W is
either left alone (with probability
0.5) or changed (again with
probability 0.5) to one of the other
15 possible hex values, each of the
15 being equally likely to be chosen.
5. W is added to the set.  We will call
V the predecessor of W.
6. If the set has fewer than 100
vectors, go to step 2.
7. Stop
[/code]

The resulting set of 100 hex vectors is

given below in random order.  For each

vector, find which line in the list

contains its immediate predecessor. If

you think that a vector is the one

placed in the set by step 1 above, put

0 as the line number of its predecessor.

predecessors as indices in the vector

starts 67,18,1,0,18.... then you are

saying that the first vector in the list

had the 67th vector as its predecessor;

the second and fifth both had 18 as

predecessor; the third had the first as

predecessor; the fourth on the list was

made by step 1 and has no predecessor.

Your score in this contest is how many

correctly identified predecessors are

in your list.  I suspect that is nearly

impossible to get all 100 correct, but

I'm interested in finding out how well

the predecessor list can be

reconstructed.

[code]
05E583CCD6A5C70A8231A4B8C704E411EEC501AA9D3B3DDAB4
6A35544C487B9E2D5064334FDD98D6428CEA934902415293E6
D44CA796164A893AE525E838F7914848D0E6146BFA45EE418E
E68DC342051778DC532EEB770770FFAB46C9FA162D0E7F549B
BE3E6B1D9DB746614B2FDF5C7DBCA07E9B68C31C5D07B9BF8F
6D39117FA08A1869093A37D028DD742140EFC13E304A7C4919
AE4FB79B964637345BEBD370F790BC4BD9E61A1A3D8BC9402B
9091AB3FE87BC555DDA04C0D6887D94325ECE2C962F6597464
C629F094C82A9A6DBA6BEBB442982C4DD9E6C24363215A028C
4A05554C8F72E0F6DFEB443C670608A58A29BCEB9E165B6F16
8D39BC1FAA2318E4093A35C428DA7421906F033BEB483C2869
4BD728A391B49517F1D199CC91F07839F972CA3E03FC5D11D7
9B36C963D6BE7595F48C2C6DD9FB8555A3E4C00386DA86E0FC
93FC89A4687C488D9AB77427D239385D8BB7C03A73E40C111F
C0241593CC44C345B66BEBBD52982C467BE6C943E5315792A8
FF24F4D23C26A6CC9FDF88B6AA78758A33E747E71DBB8E3CCE
61E9E36D661668D972A2E52087E20BF48B6601FF9D812AF1BA
7D23A72CAAACB06605CAE339281E24FF7CEEC526A0C6754599
386E744A8932517A692305F20FB357848D923983E3E1C44587
66E4FCA3DF004B994262DC2C77C25B558F65CF1B329182CABE
909BFB3FB87BC57FFDABE50DDD97444425EC52C9F2F66AE464
E2ABBDC9EE4778D3FB15BDA60750F9FB3EC0BABA00047FD714
6F861160BF8A2265297848D9F83977114EEFCCBE31417CFEF9
A494889B6626B57D75F9B4B3F8310C62C214AB269E3B65B7BA
64E583CC8D726C01D218F43C4703AC1581F9B07A9EB4506F19
CA77D491C3B5B09A6A6AE8F84854A4F479E64F465288789E90
CA77F799CA95B03D4A6AE880425EA4FD79E6D04A3341784494
8634F7A3DFE84B944063DCAF6730BB521F6D0F153BE582CFBE
B03FF095687BAE3DFA6BEC89D498D444D1E6C24962416A4467
F97231D36984B675BDC4FBE9675CB1BF636C931F041F58B600
6215CBEB21810EF86AE33D8A76C4B06DFF54C040659A574FC8
983BC033DFEE7594EE6C0C6AEF9B9B55AB8AC40BE501863B41
63E687CDDD186C613C18F4FCBD03AC152201087A9E645F4219
9498F3A724DB6177B6F8C9FBB7EC309D2EF033A04E3BE5C6BA
CB99F09968AAB03DEA6BE3804298BC4DD9E6C24A6341CA448C
D52A9776961A89E9F5A8ED48F89136F71277A6FBE8E907489E
D2A415DCCC449325B46BEEBECDB82C077B16F93DE821F870A6
D5F197A6961B9EE9CA083E4BF82016F5C277ABDBFA8902489E
6492AA188C3AE7C408B2EEE0FD31B64FD9E34AE15D00301F83
51C7794D691B568D6A6EE4FD92B5B5739962B655E3E8FC438C
DD54F0EB262EAA32417746701A71B54DDEFD9A676DFBEC448E
64E58BCCD384ACC4221193EB4B090CF9D3F638AA913E42DAB0
23E586CCF3841CCAB91193EB4509B3E3DD26383AEE3E42D0B6
DF4CA790167AB13AE525E85437114878806DAF6C2A424E413E
5FC174456912517A692EE4FDF2B5B58BE992A353E3E5CC4381
98EBF033DFE045944E62DC0A7DCB5BF51F6ACF9BB59186ABBE
209F50D59B2BAE2D4A6BF52394881041327046D909715A5478
5D231B2CAAA5B069065AE7A928D724F109EEC54E304A734919
EE8B13C29E2778D35826BB770770619B4EC8BA1B7D0B7F8593
6D663FFB8A4E323B715B427065E3F2FB698F0A383B81CD4024
8489E09CF64A473482BB60E03765BCEDF7E114684D603E4C4E
E275D2D1E7B7B5167407D72B542E9EF4A9575A002F2A742ED1
E3F9509D685A889DBA17194D9298B77DD996CD4A6361C6410C
2094FE3FB87BCB0EEEAEB50DC4D2744625EC52F9B2166AED64
89E81CA330C54B992262932C37F1CB558B35CF1B359132C80E
40FA151CCC4A9045B60BE4EDD2282C6972E6294D6771079BA8
40F8155CCC4A40E5B80B4FED6F27EC6572E627FD67711488A8
44FA1C1C074390437606F483D2282269928D299D1771076BAC
BE7FC3159E47386F5B2FD96C0764604B4B981A1B5D0B7F808B
DDF4F7EBF626DA373FC706D01A079EBDA1F73A6765FBEC448E
702FB0D34E7B9E24FE6C2637DDF8D10221E6A5A609F05AE3AA
825804AA31E599997C62996C07F1CB558B35961B455DA2910E
9F99E39BF687688353DDF7AB37E1021E21F4E0A09E3B85C40D
D499F09B864AB734EBBBE3E0F791BC4DD9E61A6A6D4B3A448E
3499805BF625B47E3EB3CEEBF7410C5D2EE63CA06AFBF5468A
EFC98C9B868A6886539BF7FB3E15321B9CFE2020EE3B8574B8
10F8865EAA091DEFA80B4B7D6C272C2522E68FCD4721138AA8
4879509DB87AB89D161C191D9028277C375BCD5A63E1CB4104
DC2CA786361A89E9E425E338F59149F2D024B4BBFA4B33419E
8605E0A0F6EA473682D9C0C2576E75A9F7E314638D60B24CDE
9499839B66266477BEFDF4BBF7E10C9A2EF631A09E3B85C6BA
4418150924FBB17796F8598587EA30916ED03B2A493F75C6BA
5AF7A3A646141D936DBE23399516BF889BC3055013D8E304E2
F922F3D36024A665EDCAE8D91A7CB52D53FD337D0D1F804104
66E4DDA3DF004BF96268DB2C7E895B558F9517F527988D9ABE
603FB045487B9E2DFE6B093FDD98D68231E6A54902405A636A
FF2AB5D3DC2CA625817FD8621871153DFCF2C1ED0FBB1AC1CE
C273CDB9CA95B0340F6AE6C92257AFF38902C04A3041784917
1A2BF39E9AE7B07D406AEF804E5874CD28F940F63541788484
66E2E3C3D6E06E9972A8E52C87E30C558F6631AB9E818ACABA
B685557A677270BEDFAB44CC67E6B2F5772EBAECBE155B6F76
```

## Recommended Posts

• 0

What you actually ask is to arrange given vectors into an ordered (rooted) tree that has the highest probability of construction according to given rules and vectors out of all possible ordered trees.

But observe, that when creating set of vectors according to given rules it is equally likely to produce vector W from vector V and to produce vector V from vector W. Therefore changing the root of the tree to any other node will not alter the probability of the tree, but will alter the relation of precession.

Finding the (non-ordered) tree with highest probability is definitely doable, but choosing the root is just guessing.

##### Share on other sites

• 0

What you actually ask is to arrange given vectors into an ordered (rooted) tree that has the highest probability of construction according to given rules and vectors out of all possible ordered trees.

But observe, that when creating set of vectors according to given rules it is equally likely to produce vector W from vector V and to produce vector V from vector W. Therefore changing the root of the tree to any other node will not alter the probability of the tree, but will alter the relation of precession.

This is a good observation but it ignores the bushing of the tree that is induced by step 2 of the way I made the vectors.

The ordered tree which I made has the root node having a larger number of children than its distant ancestors. If, for example,

one were to use one of my leaf nodes as root, it would have no more than one child -- hardly likely for the actual root node used

in my 7-step algorithm. Now, I am certainly not well versed in tree structures, and one of the reason I posed this problem was

to learn a bit about them from people like you who obviously know more than I do.

Finding the (non-ordered) tree with highest probability is definitely doable, but choosing the root is just guessing.

I'm not exactly sure what you mean here. I suppose you mean that you can pick anything as root and find the most

probable tree from that point. If you were to do this, I could certainly score your answer sensibly.

I'd like to hear more discussion on how step 2 affects the type of tree. My gut feeling tells me it narrows the

search for a possible root node. I am not at all adamant on this point. Please tell me what you think. Thanks.

##### Share on other sites

• 0

A set of 50-long vectors whose elements

are hexadecimal numbers is created as

follows:

```
1. A set is created containing exactly

one hex vector.

2. A vector V is randomly chosen from

the vectors already in the set.

3. A copy of V is made, call it W.

4. Independently of all of the other

elements of W, each element of W is

either left alone (with probability

0.5) or changed (again with

probability 0.5) to one of the other

15 possible hex values, each of the

15 being equally likely to be chosen.

5. W is added to the set.  We will call

V the predecessor of W.

6. If the set has fewer than 100

vectors, go to step 2.

7. Stop

```
The resulting set of 100 hex vectors is given below in random order. For each vector, find which line in the list contains its immediate predecessor. If you think that a vector is the one placed in the set by step 1 above, put 0 as the line number of its predecessor. As your answer, specify the list of predecessors as indices in the vector list. So, for example, if your answer starts 67,18,1,0,18.... then you are saying that the first vector in the list had the 67th vector as its predecessor; the second and fifth both had 18 as predecessor; the third had the first as predecessor; the fourth on the list was made by step 1 and has no predecessor. Your score in this contest is how many correctly identified predecessors are in your list. I suspect that is nearly impossible to get all 100 correct, but I'm interested in finding out how well the predecessor list can be reconstructed.
I miss brainden. This isn't as optimal as I'd like, but it'll do for now.

```

Order   Parent

1	73

2	94

3	22

4	33

5	78

6	60

7	71

8	59

9	78

10	90

11	66

12	37

13	32

14	8

15	55

16	40

17	43

18	26

19	12

20	61

21	99

22	59

23	56

24	99

25	37

26	65

27	77

28	60

29	8

30	87

31	25

32	73

33	34

34	43

35	24

36	50

37	43

38	92

39	45

40	57

41	32

42	87

43	78

44	85

45	74

46	19

47	44

48	78

49	26

50	78

51	73

52	51

53	5

54	37

55	96

56	49

57	24

58	37

59	97

60	71

61	50

62	9

63	78

64	4

65	43

66	25

67	24

68	19

69	68

70	68

71	9

72	50

73	87

74	17

75	94

76	67

77	87

78	43

79	9

80	73

81	87

82	77

83	69

84	65

85	5

86	63

87	73

88	42

89	86

90	74

91	96

92	61

93	24

94	37

95	61

96	26

97	34

98	34

99	73

100	13

```

Edited by bushindo
##### Share on other sites

• 0

I miss brainden. This isn't as optimal as I'd like, but it'll do for now.

Order Parent
1 73
2 94
3 22
4 33
5 78
6 60
7 71
8 59
9 78
10 90
11 66
12 37
13 32
14 8
15 55
16 40
17 43
18 26
19 12
20 61
21 99
22 59
23 56
24 99
25 37
26 65
27 77
28 60
29 8
30 87
31 25
32 73
33 34
34 43
35 24
36 50
37 43
38 92
39 45
40 57
41 32
42 87
43 78
44 85
45 74
46 19
47 44
48 78
49 26
50 78
51 73
52 51
53 5
54 37
55 96
56 49
57 24
58 37
59 97
60 71
61 50
62 9
63 78
64 4
65 43
66 25
67 24
68 19
69 68
70 68
71 9
72 50
73 87
74 17
75 94
76 67
77 87
78 43
79 9
80 73
81 87
82 77
83 69
84 65
85 5
86 63
87 73
88 42
89 86
90 74
91 96
92 61
93 24
94 37
95 61
96 26
97 34
98 34
99 73
100 13
` `

Your score is 92 out of 100! Nice. But you didn't pick a root node.

##### Share on other sites

• 0

Your score is 92 out of 100! Nice. But you didn't pick a root node.

Interesting puzzle. I really enjoy working on this. If I have to guess, I'd say that the root node is

78

##### Share on other sites

• 0

Interesting puzzle. I really enjoy working on this. If I have to guess, I'd say that the root node is

78

Your score just increased to 93. Would you mind describing how you attacked the problem?

##### Share on other sites

• 0

Your score just increased to 93. Would you mind describing how you attacked the problem?

My pleasure

I first wrote a function that takes in two 50-dimensional vectors and then returns the number of elements at corresponding index that are the same. For instance, for the first two vectors

```
05E583CCD6A5C70A8231A4B8C704E411EEC501AA9D3B3DDAB4

6A35544C487B9E2D5064334FDD98D6428CEA934902415293E6

```
the shared number is 2 because the elements at index 4 and 8 are the same. Call this shared number of elements N. The problem is posed in such a way that for any parent-child pair, N is binomially distributed with mean 25 and standard deviation 3.5. By going 2 standard deviation to the left and right of the mean, we see that 95% of the time, a parent-child pair will have an N in the interval [18, 32]. I then looped through the list of 100 vectors. For each vector V, I find the number of shared elements between V and the other 99 vectors. I then print the vectors whose number of shared elements with V is between 18 and 32. This give me the following list of potential parent-child relationships.
```
"Vector  1"

73

"Vector  2"

37 94

"Vector  3"

22 59

"Vector  4"

33 64

"Vector  5"

53 78 85

"Vector  6"

60

"Vector  7"

71

"Vector  8"

14 29 59

"Vector  9"

71 78 79

"Vector  10"

74 90

"Vector  11"

25 66

"Vector  12"

19 37 43 65 78

"Vector  13"

32 100

"Vector  14"

8

"Vector  15"

55

"Vector  16"

40

"Vector  17"

43 74

"Vector  18"

26

"Vector  19"

12 46 68

"Vector  20"

61

"Vector  21"

99

"Vector  22"

3 59

"Vector  23"

56

"Vector  24"

35 57 67 93 99

"Vector  25"

11 31 37 66

"Vector  26"

18 49 65 96

"Vector  27"

77

"Vector  28"

60

"Vector  29"

8

"Vector  30"

87

"Vector  31"

25

"Vector  32"

13 41 73

"Vector  33"

4 34

"Vector  34"

33 43 97 98

"Vector  35"

24 57

"Vector  36"

50 72

"Vector  37"

2 12 25 43 54 58 94

"Vector  38"

92

"Vector  39"

45

"Vector  40"

16 57

"Vector  41"

32

"Vector  42"

87 88

"Vector  43"

12 17 34 37 65 78

"Vector  44"

47 85

"Vector  45"

39 74

"Vector  46"

19 68

"Vector  47"

44

"Vector  48"

78

"Vector  49"

26 56

"Vector  50"

36 61 72 78

"Vector  51"

52 73

"Vector  52"

51

"Vector  53"

5 85

"Vector  54"

37 94

"Vector  55"

15 96

"Vector  56"

23 49

"Vector  57"

24 35 40

"Vector  58"

37

"Vector  59"

3  8 22 97

"Vector  60"

6 28 71

"Vector  61"

20 50 92 95

"Vector  62"

9

"Vector  63"

78 86

"Vector  64"

4

"Vector  65"

12 26 43 84

"Vector  66"

11 25

"Vector  67"

24 76

"Vector  68"

19 46 69 70

"Vector  69"

68 83

"Vector  70"

68

"Vector  71"

7  9 60

"Vector  72"

36 50

"Vector  73"

1 32 51 80 87 99

"Vector  74"

10 17 45 90

"Vector  75"

94

"Vector  76"

67

"Vector  77"

27 82 87

"Vector  78"

5  9 12 43 48 50 63 81

"Vector  79"

9

"Vector  80"

73 99

"Vector  81"

78 87

"Vector  82"

77

"Vector  83"

69

"Vector  84"

65

"Vector  85"

5 44 53

"Vector  86"

63 89

"Vector  87"

30 42 73 77 81

"Vector  88"

42

"Vector  89"

86

"Vector  90"

10 74

"Vector  91"

96

"Vector  92"

38 61

"Vector  93"

24 99

"Vector  94"

2 37 54 75

"Vector  95"

61

"Vector  96"

26 55 91

"Vector  97"

34 59

"Vector  98"

34

"Vector  99"

21 24 73 80 93

"Vector  100"

13

```

I then construct the list of parent-child relationship by going through all the leaf-nodes first, which are the ones with only 1 possible relationship (elements 1, 6, 7, etc. ). Those single-relationship vectors are obviously the children. I then attacked the elements with two relationships (elements 2, 3, 4, etc. ). If one of the two relationships in a known child, then the remaining relationship must be a parent. In cases where a vector has 2 possible parents, I compute the number of shared elements between the vector and each of the two parents, and pick the parent whose shared number N is closer to 25. Also, in general, vectors with more relationships are more likely to be a parent. I picked 78 to be the root node because it has the largest number of relationships: 8.

Edited by bushindo

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.