[superprismatic]

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.

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.

[code]

 05E583CCD6A5C70A8231A4B8C704E411EEC501AA9D3B3DDAB4

 6A35544C487B9E2D5064334FDD98D6428CEA934902415293E6

 7D231BBCDAA5B0690EB9E7497AD275F1F9FEC0462045B341D9

 5277DD11C3B9B0864437EF2B58549EF478E73AD35F0A782E91

 D44CA796164A893AE525E838F7914848D0E6146BFA45EE418E

 E68DC342051778DC532EEB770770FFAB46C9FA162D0E7F549B

 BE3E6B1D9DB746614B2FDF5C7DBCA07E9B68C31C5D07B9BF8F

 6D39117FA08A1869093A37D028DD742140EFC13E304A7C4919

 AE4FB79B964637345BEBD370F790BC4BD9E61A1A3D8BC9402B

 1EC2AD991C520039790B398F91FC103705CDD69BF60E855F1C

 9091AB3FE87BC555DDA04C0D6887D94325ECE2C962F6597464

 C629F094C82A9A6DBA6BEBB442982C4DD9E6C24363215A028C

 4A05554C8F72E0F6DFEB443C670608A58A29BCEB9E165B6F16

 8D39BC1FAA2318E4093A35C428DA7421906F033BEB483C2869

 4BD728A391B49517F1D199CC91F07839F972CA3E03FC5D11D7

 9B36C963D6BE7595F48C2C6DD9FB8555A3E4C00386DA86E0FC

 BBC9FD9969AB00487ADB83034131B59CD9E6324A624E41461C

 93FC89A4687C488D9AB77427D239385D8BB7C03A73E40C111F

 C0241593CC44C345B66BEBBD52982C467BE6C943E5315792A8

 FF24F4D23C26A6CC9FDF88B6AA78758A33E747E71DBB8E3CCE

 61E9E36D661668D972A2E52087E20BF48B6601FF9D812AF1BA

 7D23A72CAAACB06605CAE339281E24FF7CEEC526A0C6754599

 386E744A8932517A692305F20FB357848D923983E3E1C44587

 66E4FCA3DF004B994262DC2C77C25B558F65CF1B329182CABE

 909BFB3FB87BC57FFDABE50DDD97444425EC52C9F2F66AE464

 E3F779AD681C488D6A17742D9215B57D99B2CD5AE3EC0C11EC

 9269B9D676E788AA330B67A0BAE1001821B2EEAB9E3535CDAD

 E2ABBDC9EE4778D3FB15BDA60750F9FB3EC0BABA00047FD714

 6F861160BF8A2265297848D9F83977114EEFCCBE31417CFEF9

 A494889B6626B57D75F9B4B3F8310C62C214AB269E3B65B7BA

 90954BBD4ABBB06FC5DC0881D22AC44F95EA571934662AD464

 64E583CC8D726C01D218F43C4703AC1581F9B07A9EB4506F19

 CA77D491C3B5B09A6A6AE8F84854A4F479E64F465288789E90

 CA77F799CA95B03D4A6AE880425EA4FD79E6D04A3341784494

 8634F7A3DFE84B944063DCAF6730BB521F6D0F153BE582CFBE

 0D54F0EB26F3AFC9D19BC6711A05A52ADEFCCA6760FDC71C8E

 B03FF095687BAE3DFA6BEC89D498D444D1E6C24962416A4467

 F97231D36984B675BDC4FBE9675CB1BF636C931F041F58B600

 6215CBEB21810EF86AE33D8A76C4B06DFF54C040659A574FC8

 983BC033DFEE7594EE6C0C6AEF9B9B55AB8AC40BE501863B41

 63E687CDDD186C613C18F4FCBD03AC152201087A9E645F4219

 9498F3A724DB6177B6F8C9FBB7EC309D2EF033A04E3BE5C6BA

 CB99F09968AAB03DEA6BE3804298BC4DD9E6C24A6341CA448C

 D52A9776961A89E9F5A8ED48F89136F71277A6FBE8E907489E

 9B17CD90B6800D086ADA368AE6F410FD0557ED406706174F73

 D2A415DCCC449325B46BEEBECDB82C077B16F93DE821F870A6

 D5F197A6961B9EE9CA083E4BF82016F5C277ABDBFA8902489E

 6492AA188C3AE7C408B2EEE0FD31B64FD9E34AE15D00301F83

 51C7794D691B568D6A6EE4FD92B5B5739962B655E3E8FC438C

 DD54F0EB262EAA32417746701A71B54DDEFD9A676DFBEC448E

 64E58BCCD384ACC4221193EB4B090CF9D3F638AA913E42DAB0

 23E586CCF3841CCAB91193EB4509B3E3DD26383AEE3E42D0B6

 DF4CA790167AB13AE525E85437114878806DAF6C2A424E413E

 B431AD45F87B90D4FA61ED39D47B8FE2D106D4D96A40EA4467

 EAF721AD41B4353B6D5C23C19852B83B12C2CAEA63FC0D11E7

 5FC174456912517A692EE4FDF2B5B58BE992A353E3E5CC4381

 98EBF033DFE045944E62DC0A7DCB5BF51F6ACF9BB59186ABBE

 209F50D59B2BAE2D4A6BF52394881041327046D909715A5478

 5D231B2CAAA5B069065AE7A928D724F109EEC54E304A734919

 EE8B13C29E2778D35826BB770770619B4EC8BA1B7D0B7F8593

 FF22FAD3DC27A6E5917A88791A71C5DD53FDE2E70DBB8041CE

 6D663FFB8A4E323B715B427065E3F2FB698F0A383B81CD4024

 8489E09CF64A473482BB60E03765BCEDF7E114684D603E4C4E

 E275D2D1E7B7B5167407D72B542E9EF4A9575A002F2A742ED1

 E3F9509D685A889DBA17194D9298B77DD996CD4A6361C6410C

 2094FE3FB87BCB0EEEAEB50DC4D2744625EC52F9B2166AED64

 89E81CA330C54B992262932C37F1CB558B35CF1B359132C80E

 40FA151CCC4A9045B60BE4EDD2282C6972E6294D6771079BA8

 40F8155CCC4A40E5B80B4FED6F27EC6572E627FD67711488A8

 44FA1C1C074390437606F483D2282269928D299D1771076BAC

 BE7FC3159E47386F5B2FD96C0764604B4B981A1B5D0B7F808B

 DDF4F7EBF626DA373FC706D01A079EBDA1F73A6765FBEC448E

 64E583CC86806C04821DF4BC87030C9585F631AA9E328ADABA

 9BC3AD991A52000978DB35854111103D05E6DD2B660E854F1C

 702FB0D34E7B9E24FE6C2637DDF8D10221E6A5A609F05AE3AA

 825804AA31E599997C62996C07F1CB558B35961B455DA2910E

 9F99E39BF687688353DDF7AB37E1021E21F4E0A09E3B85C40D

 D499F09B864AB734EBBBE3E0F791BC4DD9E61A6A6D4B3A448E

 E524A79DF640F73022A8D7401090BC4193E6111AAD80C9400B

 461283C3D6E662B972ADE5EC87C005550F3631079EF98ACA8B

 3499805BF625B47E3EB3CEEBF7410C5D2EE63CA06AFBF5468A

 EFC98C9B868A6886539BF7FB3E15321B9CFE2020EE3B8574B8

 10F8865EAA091DEFA80B4B7D6C272C2522E68FCD4721138AA8

 4879509DB87AB89D161C191D9028277C375BCD5A63E1CB4104

 DC2CA786361A89E9E425E338F59149F2D024B4BBFA4B33419E

 8605E0A0F6EA473682D9C0C2576E75A9F7E314638D60B24CDE

 9499839B66266477BEFDF4BBF7E10C9A2EF631A09E3B85C6BA

 4418150924FBB17796F8598587EA30916ED03B2A493F75C6BA

 8605106EB6EAF736221600BC3B1C65A0573314B38D10B9B3AD

 9E90AD991A5CB009225F3577A1113F330766DC9B5600850F11

 5AF7A3A646141D936DBE23399516BF889BC3055013D8E304E2

 F922F3D36024A665EDCAE8D91A7CB52D53FD337D0D1F804104

 66E4DDA3DF004BF96268DB2C7E895B558F9517F527988D9ABE

 603FB045487B9E2DFE6B093FDD98D68231E6A54902405A636A

 FF2AB5D3DC2CA625817FD8621871153DFCF2C1ED0FBB1AC1CE

 EAF723AD48B4D6366D5823299812BF7B98C2CD5AE3F80314E2

 C273CDB9CA95B0340F6AE6C92257AFF38902C04A3041784917

 1A2BF39E9AE7B07D406AEF804E5874CD28F940F63541788484

 66E2E3C3D6E06E9972A8E52C87E30C558F6631AB9E818ACABA

 B685557A677270BEDFAB44CC67E6B2F5772EBAECBE155B6F76

[witzar]

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.

Maybe asking about non-ordered tree would make the contest more interesting.

[superprismatic]

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.

Maybe asking about non-ordered tree would make the contest more interesting.

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.

[bushindo]

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 October 11, 2010 by bushindo

[superprismatic]

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.

[bushindo]

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

[superprismatic]

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?

[bushindo]

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 October 12, 2010 by bushindo