1

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:

**

<table>
  <tr>
    <th></th>
    <th>1,2,3</th>
    <th>1,3,2</th>
    <th>2,1,3</th>
    <th>2,3,1</th>
    <th>3,1,2</th>
    <th>3,2,1</th>
  </tr>
  <tr>
    <td>f(1)</td>
    <td>1</td>
    <td>1</td>
    <td>2</td>
    <td>2</td>
    <td>3</td>
    <td>4</td>
  </tr>
  <tr>
    <td>f(2)</td>
    <td>1</td>
    <td>1</td>
    <td>1</td>
    <td>3</td>
    <td>2</td>
    <td>1</td>
  </tr>
  <tr>
    <td>f(3)</td>
    <td>1</td>
    <td>1</td>
    <td>2</td>
    <td>1</td>
    <td>1</td>
    <td>3</td>
  </tr>
  <tr>
    <td>f(4)</td>
    <td>1</td>
    <td>1</td>
    <td>1</td>
    <td>2</td>
    <td>3</td>
    <td>1</td>
  </tr>
  <tr>
    <td>f(5)</td>
    <td>1</td>
    <td>1</td>
    <td>2</td>
    <td>3</td>
    <td>2</td>
    <td>3</td>
  </tr>
  <tr>
    <td>f(6)</td>
    <td>1</td>
    <td>1</td>
    <td>1</td>
    <td>1</td>
    <td>1</td>
    <td>1</td>
  </tr>
</table>

**

but I don't know why we got this values

could somebody explain why we get this values for N = 3

user2487467
  • 11
  • It's hard to really answer without understanding what your particular confusion is about, but the short version is that what you're looking for is the least common multiple of the possible orders of all elements in a permutation group. – Steven Stadnicki Mar 29 '15 at 18:04
  • but how can I get the values of the table in a piece of paper I am trying to understand the specific case when N= 3 – user2487467 Mar 29 '15 at 18:08

1 Answers1

0

Take the third line of the tables. The permutation, in the first table, is 2,1,3. That means: Replace 1 by 2; Replace 2 by 1; Replace 3 by 3. So you are swapping 1 and 2 at each stage.
$f(1)=p(1)=2, f(2)=p(f(1))=p(2)=1,f(3)=p(f(2))=p(1)=2$. In this permutation, you are stepping back and forth; f(odd numbers)=2, f(even numbers)=1.
Is this a Project Euler question?

Empy2
  • 50,853