PermutationGame problem

[frlosa]

Hi people

could you help me to understand this problem?

This is the problem statement

Alice and Bob are playing a game called "The Permutation Game". The game is parameterized with the int N. At the start of the game, Alice chooses a positive integer x, and Bob chooses a permutation of the first Npositive integers. Let p be Bob's permutation. Alice will start at 1, and apply the permutation to this value x times. More formally, let f(1) = p[1], and f(m) = p[f(m-1)] for all m >= 2. Alice's final value will be f(x). Alice wants to choose the smallest x such that f(x) = 1 for any permutation Bob can provide. Compute and return the value of such x modulo 1,000,000,007.

for N= 3 I found that we obtain this table:

	[FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT]​
[FONT=MathJax_Math-italic]f[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]3[/FONT]​	[FONT=MathJax_Main]3[/FONT]​
[FONT=MathJax_Math-italic]f[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]3[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]1[/FONT]​
[FONT=MathJax_Math-italic]f[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]3[/FONT]​
[FONT=MathJax_Math-italic]f[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]4[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]3[/FONT]​	[FONT=MathJax_Main]1[/FONT]​
[FONT=MathJax_Math-italic]f[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]5[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]3[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]3[/FONT]​
[FONT=MathJax_Math-italic]f[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]6[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​

but I don't know why we got this values

 

[Ishuda]

Hi people

could you help me to understand this problem?

This is the problem statement

Alice and Bob are playing a game called "The Permutation Game". The game is parameterized with the int N. At the start of the game, Alice chooses a positive integer x, and Bob chooses a permutation of the first Npositive integers. Let p be Bob's permutation. Alice will start at 1, and apply the permutation to this value x times. More formally, let f(1) = p[1], and f(m) = p[f(m-1)] for all m >= 2. Alice's final value will be f(x). Alice wants to choose the smallest x such that f(x) = 1 for any permutation Bob can provide. Compute and return the value of such x modulo 1,000,000,007.

for N= 3 I found that we obtain this table:

	[FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main],[/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT]​
[FONT=MathJax_Math-italic]f[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]1[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]3[/FONT]​	[FONT=MathJax_Main]3[/FONT]​
[FONT=MathJax_Math-italic]f[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]2[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]3[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]1[/FONT]​
[FONT=MathJax_Math-italic]f[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]3[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]3[/FONT]​
[FONT=MathJax_Math-italic]f[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]4[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]3[/FONT]​	[FONT=MathJax_Main]1[/FONT]​
[FONT=MathJax_Math-italic]f[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]5[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]3[/FONT]​	[FONT=MathJax_Main]2[/FONT]​	[FONT=MathJax_Main]3[/FONT]​
[FONT=MathJax_Math-italic]f[/FONT][FONT=MathJax_Main]([/FONT][FONT=MathJax_Main]6[/FONT][FONT=MathJax_Main])[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​	[FONT=MathJax_Main]1[/FONT]​

but I don't know why we got this values

If all permutations are considered, then there are N! permutations and there is always a permutation such that the minimum x value would be N:
Let N be given by N=2M if N is even or N=2M+1 if N is odd. Then let
f(j)=N+1-j; j = 1, 2, 3, ...,M
f(M+1)=1
f(j)= N+2-j; j= M+2, M+3, M+4, ..., N
So that the list [f(x), x=1, 2, 3, ...N] is N, 2, N-1, 3, N-2, 4, ..., M+2, M, M+1, 1

In a similar fashion you can construct a permutation such that the minimum x value would be j for any j between 1 and N inclusive. In fact there is (N-1)! ways to get a repeat length of 1. That is the number of ways f(1) can be one times the number of permutations of the other N-1 numbers. There are (N-1)*(N-2)! ways to get a repeat length of 2. That is the number of ways to chose one of the remaining numbers other than 1 to put in the first position and then put 1 in the position of that number times the number of permutations of the remaining N-2 numbers. And keep going.