/sci/ - Science & Math

Some warm ups and pointers:
It's pretty easy to see that G(n,1) never has a winning strategy for Alice. (remember n >= 4)

You can then show that F(4) = 2 by finding the winning strategy of G(4,2).

I'd also recommend figuring out F(5) and F(6)

Given two natural numbers n >= 4, and k < n, consider the following two player game G(n,k):

Alice and Bob stand around a spinable table. Spaced evenly near the edges are n indistinguishable small boxes with a coin inside each box. The coin has face-up value H or T. The boxes are initially all closed meaning that the values of the coins are not visible.

On Alice's turn, she:
- opens any k boxes of her choosing
- sees the value of each coin
- sets them in any way she'd like (e.g. if k=2, she could set them as HH, TT, HT, or TH)
- closes those k boxes

On Bob's turn, he:
- has Alice leave the room so that she may not see what happens
- opens all of the boxes inspecting the coins, but doesn't touch anything.
- closes all the boxes
- spins the table to any new orientation of his choosing
- has Alice re-enter the room

They take turns in an alternating fashion, with Alice to start. The game ends and Alice wins if all coins are H or all coins are T at the start of Alice's turn. As such the game may never terminate.

Let F(n) be the smallest k such that Alice has a strategy to always win the game G(n,k). Find F(n) and prove that your solution is correct.

test

Is there a proof that the optimal string will never contain repeats of a permutation? Might be trivial, but I havent thought about it too much.


>>10104669
>>10104706
Maybe a different version is, after all you're basically trying to solve a special case of TSP on the permutation graph.

But I dont think you could reduce 3SAT to a problem with only one parameter, n.

>>10104856
Robin Houston actually used this in his 2014 paper to heurustic out a short solution for n=6. I wonder if theres any underlying structure to that solution that would yield insight. The thing I find interesting is how often it prematurely exits 1 cycles. In the standard algorithm, 1 cycles are always completed as a group, e.g. 123, 231, 312 are the first three permuations and they all belong to the element (1 2 3). So if you take a list of the 720 permutations in the order they appear in the standard solution and group them by 1 cycle, you get a list of 120 1 cycles. For Houston's solution you get 145.

>>10097526
that article is wrong, they meant the sci wikia which is run on Fandom wikia, which mainly is for anime, LNs, etc.

OP from the original 2011 thread. Is the poster !MnRMOBEIRw from the original thread here? Probably not, but just checking

>>3972979
oops didn't finish that though. You can use probability that way for large groups of people, as one persons assignment won't effect the rest of the population that much. But the probabilities are not independent at all

>>3972939
I think that's the right way to go about it for n very large. Sort of. But larger

>>3972946
n is the total number of students. In the one instance I gave the cycles are:
(1)
(2 4 5)
(3)
This makes up an element of the group <span class="math">S_5[/spoiler] (1)(2 4 5)(3)

Basically the idea behind these elements is that they determine a permutation. This particular permutation sends 1 to itself, sends 2 to 4, 4 to 5, 5 to 2, and 3 to itself.

(2 4 5) would be considered a cycle of length 3, because it has 3 elements in it

>>3972903
Do you think you could explain some of this?
In your interpretation of the problem, we look at a specific student, then find on average per student what the length of their cycle is. Does your method into account that sum(cycle lengths) = n ?

>>3972868
I cannot read latex unrendered. But I know if you look at all the m-cycles (cycle of length m for 1<=m<=n), There are n(n-1)...(n-m+1) / m such unique cycles possible

>>3972869
see the post below that for clarification. The cycle at it's largest can contain n people.

>>3972825
>repeat rooms
You cannot. If person 1 is sent to room 1 again, the cycle is of length 1. Have you done anything with symmetric groups? the idea is as follows for <span class="math">S_{10}[/spoiler] for example, one element of the group is (123)(456)(7)(8)(9 10).
person 1 is sent to room 2, 2 to room 3, 3 to room 1... 7 is sent to his old room etc.

At t-1, only one iteration takes place. So at worse, we have the element (1 2 3 4 5 6 7 8 9 10) which creates a cycle of length 10.

>>3972808
Why? Yes there are 1000! elements of <span class="math">S_{1000}[/spoiler]. But why a division by two

>>3972818
I'm trying to find the average of all such instances. In other words <span class="math"> \sum_{i=1}^{n!} \sum_{k=1}^{m} length of cycle_k[/spoiler]
where i is the i-th instance (there are n! of them in <span class="math">S_{1000}[/spoiler]) and k is the k-th cycle inside of a given i. (of which there are m of them)

Background:
This actually happens every year to the frosh class at my school. However our school has singles and doubles and Triples. I want to try and solve the easy case, and see if I can use it's solution to help with the harder one. I'm going to try to make a python program to statistically get an answer, so we how average_cycle_length grows with n.

>>3972768
saved. you point?

>>3972742
Notes:
This question, like my previous, can be brought into the world of groups, namely symmetric groups. <span class="math">S_{1000}[/spoiler] contains all the possible permutations of the problem. So the question can be redefined as: given a random element of <span class="math">S_{1000}[/spoiler] what is the average cycle length?

Ok /sci/, you're a university of 1000 students, which 1000 singles. At time 0, Student 1 is in Room 1, Student 2 is in room 2, etc. At time 1, all the students pack up and randomly reassigned to a room. What is the average cycle length created? and given a random permutation, what most likely is the number of cycles.
For example if there where 5 rooms, you could have the permutation
S1 -> R1
S2 -> R4
S4 -> R5
S5 -> R2
S3 -> R3
There are 3 cycles and the average length is 5/3.

>pic unrelated

>>3879783
I just got this problem from something that actually happens at my school. Housing gave the freshman 3 days to switch rooms. the cycles were a mess, so I wanted to find out how large the problem actually is.

So far I've been trying to use strictly CS, to attack the problem, But I'd like to see probability and/or abstract alegebra applied.
The real problem involves n singles, m doubles, and o triples. That complicates things a lot, there are multiple potential cycles for any given person, depending on which roomate they kick out

Here's an example of one such permutation for n=10


__Student{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Final room{9, 2, 6, 3,10, 8, 7, 5, 1, 4}

It's fairly straightforward: the student from room 1 switches to room 9, the student from room 2 stays, etc.
Here are the cycles that are created from this mapping:

Length/Cycle
2 (1 9)
1 (2)
6 (3 6 8 5 10 4)
1 (7)

So in this execution, the average length of cycles per student is: 2*.2+1*.2+6*.6= 4.2

Note that this is a weighted average, as it is per student.

Ok, /sci/. Permutationfag here. I have a new problem. It has a long backstory. It's fairly hard, and has several levels to it, the final of which is a model of a real life scenario that I'm trying to figure out. But before I figure that out, I want to solve the simpler versions, with your help.


-------------------The Problem (easymode)----------------
There are n, with n=100 singles at a college. Each student is given a temporary room at the start of term. Two weeks later, the reassignment process starts: One by one students are randomly assigned to a room that noone has been reassigned to yet.

The chain of room switching is cyclic in nature; there can be at most a cycle of 1 (only 1 person involved/no switching) and a cycle of n (everyone involved).

Per student, what is the average cycle length of room switching?

-Novice Mode-
Find an implicit function C(n) for the average cycle per student as a function of n students

>pic unrelated

Example for n=10
__Student{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Final room{9, 2, 6, 3,10, 8, 7, 5, 1, 4}

Length/Cycle
2 (1 9)
1 (2)
6 (3 6 8 5 10 4)
1 (7)

So in this execution, the average length of cycles per student is: 2*.2+1*.2+6*.6= 4.2

Note that this is a weighted average, as it is per student.

Ok, /sci/. Permutation fag here. I have a new problem:

-Easy Version-
There are n, with n=100 singles at a college. Each student, <span class="math">S_1, S_2[/spoiler]...<span class="math">S_n[/spoiler] corresponds to their room <span class="math">R_1, R_2[/spoiler]...<span class="math">R_n[/spoiler]. One by one they are randomly assigned to a remaining room.
The chain of room switching is cyclic in nature; there can be at most a cycle of 1 (only 1 person involved/no switching) and a cycle of n (everyone involved).

Per student, what is the average cycle length of room switching?

-Novice Mode-
Find an implicit function C(n) for the cycles based on n.

>pic unrelared

>Implying that the cost to do business wouldn't outway the slight profit
>Implying that you buy and sell gold based on

http://www.wolframalpha.com/input/?i=gravity+in+new+york+city

http://www.wolframalpha.com/input/?i=gravity+in+mexico+city

>>3751953
I think I understand your point, that sometimes the amount of overlap will be 1,2..n. The only case I've looked at extensively is n=4. In that case, you'd have 0-iterations (obviously) as well as 1-iterations and 2-iterations (maximum). I wonder if for case n, if you must have a non-zero number of 0,1,2...n-2 iterations in the efficient process.