Trying to find or similar problems (objects travelling across slots)

  • Context: Undergrad 
  • Thread starter Thread starter aRiver
  • Start date Start date
Click For Summary
SUMMARY

This discussion revolves around a combinatorial problem involving the movement of objects across 18 slots, where no two objects can occupy the same slot. The objects can move 1, 2, or 3 slots per period, and the user seeks to analyze the problem using mathematical concepts such as matrix representation and state transitions. The conversation highlights the need for a clear mathematical objective and the importance of defining the problem's parameters to receive effective guidance.

PREREQUISITES
  • Understanding of combinatorial mathematics
  • Familiarity with matrix algebra and state transition matrices
  • Knowledge of modular arithmetic
  • Basic principles of graph theory
NEXT STEPS
  • Research "Matrix representation of state transitions" in combinatorial problems
  • Explore "Graph theory applications in combinatorial optimization"
  • Study "Modular arithmetic in combinatorial contexts"
  • Investigate "Dynamic programming approaches to slot allocation problems"
USEFUL FOR

Mathematicians, computer scientists, and anyone interested in combinatorial optimization and state transition analysis in complex systems.

aRiver
Messages
1
Reaction score
0
I'm trying to find a way to approach a problem:

No two objects can occupy the same slot.
Objects can travel 1, 2, or 3 slots per period.
There are 18 slots.

That is really a very trivial case of a more complex problem. My question is does this sound like similar to any existing problems in mathematics? I'm trying to find a way to analyze the problem (matrix ? modulo arithmetic ?)

a simple case follows

three objects released at the same time, with rate 1, 2, 3.
step1 : 1,2,3 occupied
step2 : 2,4,6 occupied
step3 : 3,6,9
step4 : 4,8,12
step5 : 5,10,15
step6 : 6,12,18
step7 : 7,14
...
...
...

Eventually I want to analyze a way to, say, maximize objects of any type which traverse the slots over a given number of steps, or how changing number of slots effect the problem. Rather than ask for a solution or analysis, I was wondering if anyone could point me to a similar problem, because I feel like this is a more complex version of a solved problem.
 
Mathematics news on Phys.org
aRiver said:
Eventually I want to analyze a way to, say, maximize objects of any type which traverse the slots over a given number of steps, or how changing number of slots effect the problem.

You haven't defined a mathematical objective yet. It isn't clear what "traverse the slots" means. It isn't clear whether the objects are each to be treated as distinct from each other.

One way of looking at this is that there are a set of possible "states", each state being a set of 3 numbers that tell which cells are occupied ( e.g. (1,2,3), (2,4,6),(1,7,9) .. etc.) You can define a matrix A by setting [itex]A_{i,j} = 1[/itex] iff it is possible for the system to change from state [itex]i[/itex] to state [itex]j[/itex] and [itex]A_{i,j} = 0[/itex] otherwise. The possible changes the system can make in [itex]n[/itex] steps is given by [itex]A^n[/itex]. The matrix [itex]A[/itex] specifies the edges in a graph..

You'll probably get better advice if you explain the actual problem that you are dealing with. Asking how to apply mathematics to a problem is an interesting challenge. On the one hand, if you write a long post filled with details, you risk making it so tedious that nobody will respond. On the other hand, if you attempt to extract the essential details and summarize them, you are exercising your own judgment about which facts are the mathematical essentials, so you are removing that function from any of your advisors.
 

Similar threads

  • · Replies 58 ·
2
Replies
58
Views
8K
  • · Replies 25 ·
Replies
25
Views
6K
  • · Replies 26 ·
Replies
26
Views
7K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 1 ·
Replies
1
Views
4K
  • · Replies 5 ·
Replies
5
Views
5K
  • · Replies 8 ·
Replies
8
Views
5K