A kind of TSP.

[Ernst]

There are 9 cities.

 

The ciities ar ordered from 1 to 9 and they are always visited in order from 1 to 9.

 

From city n to city n+1 there are 4 routes, let's call them 1, 2, 3 and 4 . The distances doesn't matter.

 

There are 4^8 possible routes from city 1 to city 9.

 

Is it possible to find out the minimum number of ways to go from city 1 to city 9, such that the route would differ at one and only one segment from the one considered to be the right route?

 

In other words:

 

Possible vectors:

(1,1,1,1,1,1,1,1)

(1,1,1,1,1,1,1,2)

(1,1,1,1,1,1,1,4)

(1,1,1,1,1,1,2,1)

(1,1,1,1,1,1,2,2)

.

.

.

(4,4,4,4,4,4,4,4)

 

Person A chooses any of those. What is the minimum number of vectors person B must choose, to be sure that there is a difference in one and only one place(at most) compared to person A:s vector?

[imatfaal]

There are 9 cities.

 

The ciities ar ordered from 1 to 9 and they are always visited in order from 1 to 9.

 

From city n to city n+1 there are 4 routes, let's call them 1, 2, 3 and 4 . The distances doesn't matter.

 

There are 4^8 possible routes from city 1 to city 9.

 

Is it possible to find out the minimum number of ways to go from city 1 to city 9, such that the route would differ at one and only one segment from the one considered to be the right route?

each decision has 4 options, you can take a wrong option only once ie there are 3 ways you can be wrong at decision 1 OR 3 ways at decision 2 OR 3 ways at decision 3. Surely you can just add the routes - 3 at each decision point, 8 decision points to make 24 "incorrect by one" routes

 

In other words:

 

Possible vectors:

(1,1,1,1,1,1,1,1)

(1,1,1,1,1,1,1,2)

(1,1,1,1,1,1,1,4)

what happened to 1 1 1 1 1 1 1 3?

 

(1,1,1,1,1,1,2,1)

(1,1,1,1,1,1,2,2)

Assuming 1 to be the best route - and you can do that without loss; then 1111122 is an invalid route as it takes the second best twice.

.

.

.

(4,4,4,4,4,4,4,4)

 

Person A chooses any of those. What is the minimum number of vectors person B must choose, to be sure that there is a difference in one and only one place(at most) compared to person A:s vector?

That is not the same question. there are 4 to the power 8 routes - 24 of those differ at one section from the ideal route. How many must you chose to be sure you are only one off from the desired route? to be SURE you need to choose (4^8 - 24) +1 routes

 

To guarantee an "off by one' you need to assume that your first n guesses will be wrong - if you have the maximum number of wrong guess possible +1 more try, only then are you guaranteed to get it right.

 

Oh and BTW - this is not travelling salesman.

[Ernst]

I was in a hurry when I wrote, so I missed the vector (1, 1, 1 ,1 ,1 ,1 ,1 , 3).

 

I know that this is not a TSP. Since roads and cities were involved I called it "a kind of TSP".

 

Compare my question to trying to do the pools on 4 soccer matches. Home win: 1, draw: X, away win: 2.

Number of possible results: 3 ^4 = 81

 

You can get away with only 9 of the 81 possible results and still have 3 out of 4 right. That's a reduction with 88.89 %.

 

E.g.

 

1X212X1X2

1X2X1221X

1X22X1X21

XXX222111

 

Now I think you understand my question.

 

I doubt that I have to chose as many as 65513 out of 65536 to "have" 7 "right". A reduction with only 0.035 %.

[imatfaal]

No I am still a little lost about your question. Using the football example - tell me where I am diverting from your question

 

1. Three results 1,2,3 - lets mark 1 as the correct result and 2 and 3 as incorrect

 

2. 81 possible results to the guesses

 

1111 1211 1311 2111 2211 2311 3111 3211 3211 3311

1112 1212 1312 2112 2212 2312 3112 3212 3212 3312

1113 1213 1313 2113 2213 2313 3113 3213 3213 3313

1121 1221 1321 2121 2221 2321 3121 3221 3221 3321

1122 1222 1322 2122 2222 2322 3122 3222 3222 3322

1123 1223 1323 2123 2223 2323 3123 3223 3223 3323

1131 1231 1331 2131 2231 2331 3131 3231 3231 3331

1132 1232 1332 2132 2232 2332 3132 3232 3232 3332

1133 1233 1333 2133 2233 2333 3133 3233 3233 3333

 

3. 1111 is all correct, there are 8 guesses (underlined) that are only one out (2 ways wrong for each match)

 

4. To guarantee that one of your set of guesses was one of those 8 - ie per the OP "What is the minimum number of vectors person B must choose, to be sure that there is a difference in one and only one place(at most) compared to person A:s vector?" You would need to take (81 -9)+1 guesses - that would include the being all correct as a valid guess. If you wanted to be different in one and only place (exactly) you would need (81-8)+1 guesses

[Ernst]

Since english isn't my native language, maybe I have expressed myself unclear. When you are doing the pools you want to have as many right as possible. I have probably stated my first question the wrong way.

 

Whichever of the 81 possible results for 4 matches, I will always have at least 3 matches right with e.g. the nine combinations:

 

1X212X1X2

1X2X1221X

1X22X1X21

XXX222111

 

That doesn't take long time to verify.

 

If my first question had concerned 8 soccer matches and there would have been 4 possible outcomes(very strange) but e.g. 1 = home win with more than 3 goals, 2=any other home win, 3=draw, 4=away win. Then the total number of possible combinatiions would have been 4^8 = 65536.

 

It seems unlikely that I must choose 65513 of those to be guaranteed to have 7 right, but maybe...

 

Maybe it's possible to use applied integer programming to solve my problem. I don't know enough.

 

Forget my first question and try to regard my problem as soccer matches in this strange way. Do you understand me now?