Jump to content
BrainDen.com - Brain Teasers
  • 0

Find The Hidden List


nikolas
 Share

Question

Hello everyone,

i recently encountered a logic problem which is this:

There is a list(original) that contains all numbers from 1...n, without duplicates and not necessary in order. We dont know that list but we know

5 other lists which are the result of the original in that way: The first list came from moving one number from the original list to another position( be careful, move not exchange),

the second list came from moving another different number from the original list. What actions you must do to find the original list?

for example: 5 lists={[1,2,5,3,4],[1,5,3,4,2],[4,2,1,5,3],[2,3,1,5,4],[2,1,3,4,5]} and the original is Original=[2,1,5,3,4].

Link to comment
Share on other sites

20 answers to this question

Recommended Posts

  • 0

Line up the lists and inspect contiguous groups of three columns.

There should be one and only one element that appears in each line of that nx3 array.

That element occupies the middle column in the original array.

Exception: the element might appear on every line of the nx3 array except one:

that is the list in which it was the moved element.

Example: in the five lists above:

The element 1 appears in the 123 positions in every case. That places it in position 2.

The element 5 appears in the 234 positions in every case. That places it in position 3

The element 5 appears in the 345 position with one exception. That places it in position 4.

Link to comment
Share on other sites

  • 0

@bananova good thinking but here where you say


The element 5 appears in the 234 positions in every case. That places it in position 3


in positions 234 in line 5 element 5 is missing, and so does element 3 in line 4 in position 345.

and here:

The element 5 appears in the 345 position with one exception. That places it in position 4.

you should be meaning element 3(because 3 is in position 3) but in the 4th list in positions 123 there is no element 3

Link to comment
Share on other sites

  • 0

@fabpig the numer of elements each list contains is n(variable). In this case n=5, and n>=3 always because of the number of permutations. e.g. for n=2, n!=1*2=2<5, but 3!=1*2*3=6>5 and as a result we can have the 5 lists.

Not sure if that's what I'm asking :) . If there are eg. 9 elements, will there be 9 lists (that way, we know that each element has been moved once)?

Link to comment
Share on other sites

  • 0


The number in position 1 must always be in either position 1 or 2 in every list apart from the list in which it's moved. If this applies to only one number, then that must be pos 1.
Now, it's possible that more than one number meets this criterion (for example if list 3 was [2,1,4,5,3] and/or list 4 was [2,1,3,5,4] then both "2" and "1" fall into this category). In this case we need to check the order in which the two numbers occur more than once. Whichever occurs first (more than once) is pos 1.

Similarly, the number in position 5 must always be in position 4 or 5 apart from the list in which it's moved.

I suspect that the same procedure can be applied to positions 2 onwards (+-1 of actual position), but I've yet to try it exhaustively.
Link to comment
Share on other sites

  • 0

for example: 5 lists={[1,2,5,3,4],[1,5,3,4,2],[4,2,1,5,3],[2,3,1,5,4],[2,1,3,4,5]} and the original is Original=[2,1,5,3,4].

I understand that to go from [1,2,5,3,4] to [1,5,3,4,2] can be easily achieved by moving the 2 to the rear but how does one then go to [4,2,1,5,3]? Can we slide two numbers at once?

Link to comment
Share on other sites

  • 0

for example: 5 lists={[1,2,5,3,4],[1,5,3,4,2],[4,2,1,5,3],[2,3,1,5,4],[2,1,3,4,5]} and the original is Original=[2,1,5,3,4].

I understand that to go from [1,2,5,3,4] to [1,5,3,4,2] can be easily achieved by moving the 2 to the rear but how does one then go to [4,2,1,5,3]? Can we slide two numbers at once?

Think I can answer that.....

Each list has one number moved from the original list...not the previous list.

Link to comment
Share on other sites

  • 0

man look tough.

it seems to me though bonanova is on the right track.

take the five lists look at numbers either in the same position, or in the same order.

that will tell you the original order.

I'm not entirely sure why 5 is the magic number though.

lets say we have 9 numbers.

4 1 7 8 2 3 5 9 6

2 4 1 9 7 8 3 5 6

2 4 1 8 3 5 7 9 6

2 4 1 6 7 8 3 5 9

3 2 4 1 7 8 5 9 6

can you deduce my original sequence?

Link to comment
Share on other sites

  • 0

man look tough.

it seems to me though bonanova is on the right track.

take the five lists look at numbers either in the same position, or in the same order.

that will tell you the original order.

I'm not entirely sure why 5 is the magic number though.

lets say we have 9 numbers.

4 1 7 8 2 3 5 9 6

2 4 1 9 7 8 3 5 6

2 4 1 8 3 5 7 9 6

2 4 1 6 7 8 3 5 9

3 2 4 1 7 8 5 9 6

can you deduce my original sequence?

Looks like whatever the mode of each value behind another assigned value

@phill 2,4,1,3,7,8,5,9,6

since 4 most commonly followed 2; 4 is behind 2. since 1 is most commonly behind 4, 1 is behind 4. and so on.

Link to comment
Share on other sites

  • 0

Bad wording... I said that whichever number came first in the lists, when I meant whichever number came to the left of the other one - not necessarily immediately left of - (more than once)



But even the "more than once" is wrong. EG. take original list 1,2,3,4,5 for simplicity's sake. It is possible for the following 5 lists:

2,1,3,4,5 /* Here "1" has moved to column 2 */
2,1,3,4,5 /* And "2" has moved to column 1! */
1,2,3,5,4
1,2,4,3,5
1,3,2,4,5

In the above, the occupant of column 1 in the original must occupy columns 1 or 2 in the 5 lists on at least 4 occasions. That applies to "1" and "2". 2 comes left of 1 twice, vs 1 left of 2, 3 times. So it's whichever is the leftmost more often that determines that number 1 has column 1 (in this example). This could be nikolas's reference to the number 5 (majority 3 to 2).

So. Lets move on to column 2. It's possible for the inmate to occupy columns 1,2, or 3 in the 5 lists on >= (n - 1) occasions in the 3 columns. Any occurence of number "1" can be ignored as it has already been allocated to column 1. There are 5 occurences of "2" , and 4 occurences of "3" in the 3 columns. As 2 precedes 3 in the 5 lists on more occasions, it can be allocated to column 2.

Same applies to each subsequent column, ignoring numbers that have already been allocated.

Think That about covers it.

I'm going to try to write a program to see if it works for lists with more elements (you have been warned :) )

This could get (even) ugli(er)!
Link to comment
Share on other sites

  • 0

You are given five lists. For any two numbers in the series, call them A and B, you will know that in one of those lists A has been moved, in one other list B has been moved, and in three lists neither A nor B was the number that was moved -- meaning that in those three lists A will be to the left of B only if it's to the left of B in the original list, and to the right of B only if it's to the right of B in the original list.

So if you find three (or more) lists where A is to the left of B, then you know that A is to the left of B in the original list. If you find three (or more) where A is to the right of B, then A must be to the right of B in the original list.

Repeat that for all pairs of numbers (or howevermany you need to figure out the list's order).

This would be the reason why having (at least) five lists, regardless of how long the list of numbers is, is important.

Edited by plasmid
Link to comment
Share on other sites

  • 0

You are given five lists. For any two numbers in the series, call them A and B, you will know that in one of those lists A has been moved, in one other list B has been moved, and in three lists neither A nor B was the number that was moved -- meaning that in those three lists A will be to the left of B only if it's to the left of B in the original list, and to the right of B only if it's to the right of B in the original list.

So if you find three (or more) lists where A is to the left of B, then you know that A is to the left of B in the original list. If you find three (or more) where A is to the right of B, then A must be to the right of B in the original list.

Repeat that for all pairs of numbers (or howevermany you need to figure out the list's order).

This would be the reason why having (at least) five lists, regardless of how long the list of numbers is, is important.

That's what I thought I was saying. :unsure:

Damn my northern accent!

Link to comment
Share on other sites

  • 0

man look tough.

it seems to me though bonanova is on the right track.

take the five lists look at numbers either in the same position, or in the same order.

that will tell you the original order.

I'm not entirely sure why 5 is the magic number though.

lets say we have 9 numbers.

4 1 7 8 2 3 5 9 6

2 4 1 9 7 8 3 5 6

2 4 1 8 3 5 7 9 6

2 4 1 6 7 8 3 5 9

3 2 4 1 7 8 5 9 6

can you deduce my original sequence?

2,4,1,7,8,3,5,9,6

woohoo

Link to comment
Share on other sites

Join the conversation

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

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

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

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...