1

Topic: Parameters

All greetings. Such etude. It is set N (<=500) parameters, each of which can accept value from 1 to 26. Is M (<=500) buttons, pushing each of which changes values of initial parameters (optionally all). Also some starting state of parameters S0 is set. It is required for  a dial-up of states S [1. K] (K <=100) to define, whether it is possible to come into fortune Si from state S0 by pushing of some sequence of buttons (buttons can be pushed arbitrary, each button the unlimited number of times can be used). There are ideas? Thanks.

2

Re: Parameters

Hello, Serge, you wrote: S> All greetings. Such etude. S> It is set N (<=500) parameters, each of which can accept value from 1 to 26. Is M (<=500) buttons, pushing each of which changes values of initial parameters (optionally all). Also some starting state of parameters S0 is set. S> it is required for  a dial-up of states S [1. K] (K <=100) to define, whether it is possible to come into fortune Si from state S0 by pushing of some sequence of buttons (buttons can be pushed arbitrary, each button the unlimited number of times can be used). S> There are ideas? Make system of equations on 26 S0 + m unit [i] *K [i] = S1 %26 m [i] - actually kol-in pushings button K [i]

3

Re: Parameters

Hello, kov_serg, you wrote: _> Make system of equations on 26 _ unit> S0 + m [i] *K [i] = S1 %26 _> m [i] - actually kol-in pushings button K [i] Probably, the system of equations approaches for a case, when each button  value of parameter. In the initial task, each button installs values of parameters. For example, for 2 parameters: the Button 1: (' a ', ' b '), the Button 2: (' x ', ' - ') where ' - ' means that value of parameter remains invariable, after pushing of the given button.

4

Re: Parameters

Hello, Serge, you wrote: S> Hello, kov_serg, you wrote: _>> Make system of equations on 26 _ unit>> S0 + m [i] *K [i] = S1 %26 _>> m [i] - actually kol-in pushings button K [i] S> Probably, the system of equations approaches for a case, when each button  value of parameter. In the initial task, each button installs values of parameters. For example, for 2 parameters: the Button 1: (' a ', ' b '), the Button 2: (' x ', ' - ') where ' - ' means that value of parameter remains invariable, after pushing of the given button. Then all is worse S [0] =S0... S [i+1] =S [i] *M [i] +K [i]... S [n] =S_fin For example M [i] = (0,1,1...) - mask K [i] = (' - ', 0,0...) - result of pushing

5

Re: Parameters

Hello, Serge, you wrote: S> All greetings. Such etude. S> It is set N (<=500) parameters, each of which can accept value from 1 to 26. Is M (<=500) buttons, pushing each of which changes values of initial parameters (optionally all). Also some starting state of parameters S0 is set. S> it is required for  a dial-up of states S [1. K] (K <=100) to define, whether it is possible to come into fortune Si from state S0 by pushing of some sequence of buttons (buttons can be pushed arbitrary, each button the unlimited number of times can be used). S> There are ideas? S> thanks. And initial a state can be not achievable (wrong)? If is not present, all is reduced to the proof of possibility of state Si. We compare to each parameter a dial-up of buttons by which it is controlled. If value of all parameters with an identical dial-up of buttons to equally value what or buttons from this dial-up the state is achievable. Like so.

6

Re: Parameters

Hello, Qulac, you wrote: Q> And initial a state can be not achievable (wrong)? If is not present, all is reduced to the proof of possibility of state Si. We compare to each parameter a dial-up of buttons by which it is controlled. If value of all parameters with an identical dial-up of buttons to equally value what or buttons from this dial-up the state is achievable. Like so. The Starting state can be any. Here an example: S0 = ' cc ' - Button starting state: ' a - ' '-b ' where ' - ' - the button does not change the given parameter. Then for the following the state the answer will be ' ab ' - it is possible ' ac ' - it is possible ' cb ' - it is possible ' ba ' - it is impossible

7

Re: Parameters

Hello, Serge, you wrote: S> Hello, Qulac, you wrote: Q>> And initial a state can be not achievable (wrong)? If is not present, all is reduced to the proof of possibility of state Si. We compare to each parameter a dial-up of buttons by which it is controlled. If value of all parameters with an identical dial-up of buttons to equally value what or buttons from this dial-up the state is achievable. Like so. S> the Starting state can be any. Here an example: S> S0 = ' cc ' - starting state S> Buttons: S> ' a - ' S> '-b ' S> where ' - ' - the button does not change the given parameter. S> then for the following the state the answer will be S> ' ab ' - it is possible S> ' ac ' - it is possible S> ' cb ' - it is possible S> ' ba ' - it is impossible Then so: If value of all parameters of a state si with an identical dial-up of buttons to equally value what or buttons from this dial-up or to value of similar parameter from a state s0 the state si is achievable.

8

Re: Parameters

All greetings. We fix state Si for which it is required to find the answer. Then the task can be shown to the following. Is N bulbs and M buttons. The starting state of bulbs (it is included - 1, is ungeared - 0) is known. Each of buttons includes/switches off some subset of bulbs. It is required to define, whether it is possible to ungear all bulbs. The given task differs from classical that button click does not change a bulb state (i.e. 1> 0, 0> 1), and installs a bulb state (for example, in 0 [0> 0, 1> 0] or in 1 [0> 1, 1> 1]). Probably, someone knows, whether given task NP is or not. Thanks.

9

Re: Parameters

Hello, Serge, you wrote: S> There are ideas? It would Seem. We have. States achievable from initial for one course, for two. For three and etc. the Natural estimation of distance to a target state - number of different parameters. We receive purposeful heuristic search of a way in the column, for example * S> Thanks. For "thanks" here there are buttons

10

Re: Parameters

Hello, Erop, you wrote: E> States achievable from initial for one course, for two. For three and etc. Aha, only 2^500 states. E> a natural estimation of distance to a target state - number of different parameters. It is not a lot of steps, it is a lot of peaks. E> purposeful heuristic search of a way in the column, for example * Well, and on an output the answer Is received: "not ". And why - it is not clear, whether the way is not present, whether it did not turn out to find. The task is Somehow not so similar to full, there should be something dynamic, like  an optimal way too is optimal.