l******i
发帖数: 1404 | 1 You have a circle with a number of ants
scattered around it at distinct points.
Each ant starts walking at the same speed
but in possibly diff erent directions, either clockwise or anticlockwise.
When two ants meet they immediately change directions,
and then continue with the same speed as before.
Let us ignore the collisions,
just think of the ants walking through each other.
Clearly there will then be a time at which
the ants are simultaneously in their starting positions.
But how to prove that the ants will be in their own starting positions,
meanwhile moving in the same direction they were to start with? | A**u
发帖数: 2458 | 2 这是绿皮书的题目
A---> B<----
=
A<---- B----->
=
B<---- A---->
所以meet没有影响
【在 l******i 的大作中提到】
: You have a circle with a number of ants
: scattered around it at distinct points.
: Each ant starts walking at the same speed
: but in possibly diff erent directions, either clockwise or anticlockwise.
: When two ants meet they immediately change directions,
: and then continue with the same speed as before.
: Let us ignore the collisions,
: just think of the ants walking through each other.
: Clearly there will then be a time at which
: the ants are simultaneously in their starting positions.
| E*******n
发帖数: 3 | 3 1. 假设蚂蚁能相互穿过,那么走的方向不会变.这也就是说,假如某蚂蚁起始位置为0,那
么当1个循环后,另一只蚂蚁代替它走回原来的位置时,移动方向和开始时一致.所以如果
第一问成立,第二问直接follow.
2. 现在考虑蚂蚁不能相互穿过,那么1个循环后可能每只蚂蚁都在另一只蚂蚁的起始位
置.但由于没有任何穿过,所有蚂蚁的位置必须是其实位置shift了几只蚂蚁的位置.譬如
1在4的位置上,2在5的位置上,...,n在3的位置上.
假设1次循环shift k只蚂蚁的位置,共n只蚂蚁,那么重复上述过程n次,所以蚂蚁都shift
了nk个位置,就回到起始位置了. | k*****y
发帖数: 744 | 4 假设速度是1，圆的长度也是1。
case 1: 如果都是同一方向
t=1时，会回到原来的状态。
case 2: 设有p个clockwise，q个counterclockwise，pq != 0。
画个图应该可以证明在t = p+q时，会经过2pq次碰撞，回到了原来的状态。
【在 l******i 的大作中提到】
: You have a circle with a number of ants
: scattered around it at distinct points.
: Each ant starts walking at the same speed
: but in possibly diff erent directions, either clockwise or anticlockwise.
: When two ants meet they immediately change directions,
: and then continue with the same speed as before.
: Let us ignore the collisions,
: just think of the ants walking through each other.
: Clearly there will then be a time at which
: the ants are simultaneously in their starting positions.
| l******i
发帖数: 1404 | 5 嗯，有道理。
shift
【在 E*******n 的大作中提到】
: 1. 假设蚂蚁能相互穿过,那么走的方向不会变.这也就是说,假如某蚂蚁起始位置为0,那
: 么当1个循环后,另一只蚂蚁代替它走回原来的位置时,移动方向和开始时一致.所以如果
: 第一问成立,第二问直接follow.
: 2. 现在考虑蚂蚁不能相互穿过,那么1个循环后可能每只蚂蚁都在另一只蚂蚁的起始位
: 置.但由于没有任何穿过,所有蚂蚁的位置必须是其实位置shift了几只蚂蚁的位置.譬如
: 1在4的位置上,2在5的位置上,...,n在3的位置上.
: 假设1次循环shift k只蚂蚁的位置,共n只蚂蚁,那么重复上述过程n次,所以蚂蚁都shift
: 了nk个位置,就回到起始位置了.
| s********r
发帖数: 529 | 6 那个shift的地方没有想明白，直觉似乎应该这样，但是没有很清晰的思路可以导出来，
不知道能否提点一下呢？多谢了
shift
【在 E*******n 的大作中提到】
: 1. 假设蚂蚁能相互穿过,那么走的方向不会变.这也就是说,假如某蚂蚁起始位置为0,那
: 么当1个循环后,另一只蚂蚁代替它走回原来的位置时,移动方向和开始时一致.所以如果
: 第一问成立,第二问直接follow.
: 2. 现在考虑蚂蚁不能相互穿过,那么1个循环后可能每只蚂蚁都在另一只蚂蚁的起始位
: 置.但由于没有任何穿过,所有蚂蚁的位置必须是其实位置shift了几只蚂蚁的位置.譬如
: 1在4的位置上,2在5的位置上,...,n在3的位置上.
: 假设1次循环shift k只蚂蚁的位置,共n只蚂蚁,那么重复上述过程n次,所以蚂蚁都shift
: 了nk个位置,就回到起始位置了.
| l******i
发帖数: 1404 | 7 咋个严格证明t = p+q时，会经过2pq次碰撞，并且回到了原来的状态？
【在 k*****y 的大作中提到】
: 假设速度是1，圆的长度也是1。
: case 1: 如果都是同一方向
: t=1时，会回到原来的状态。
: case 2: 设有p个clockwise，q个counterclockwise，pq != 0。
: 画个图应该可以证明在t = p+q时，会经过2pq次碰撞，回到了原来的状态。
| k*****y
发帖数: 744 | 8 好像还是t = p+q，但是经过了4pq次碰撞。
假设一个周期内有p根红线，q根蓝线，X轴是时间，ant将会沿着这样的zig-zag走。
假设碰撞了4pq次。那么，沿着红的方向走了2pq段，即经过了2p个周期(因为是45度，
所以每个红的周期投影到Y轴的长度是1/2)，Y的位移是p；同理沿着蓝的方向走了2pq段
，经过2q个周期，Y的位移是-q。于是Y的总位移是p-q，于是回到了原来的位置。因为
经过了偶次碰撞，方向还是原来的。
【在 l******i 的大作中提到】
: 咋个严格证明t = p+q时，会经过2pq次碰撞，并且回到了原来的状态？
| L******g
发帖数: 1371 | 9 curious, how many mins you figured that out?
【在 k*****y 的大作中提到】
: 假设速度是1，圆的长度也是1。
: case 1: 如果都是同一方向
: t=1时，会回到原来的状态。
: case 2: 设有p个clockwise，q个counterclockwise，pq != 0。
: 画个图应该可以证明在t = p+q时，会经过2pq次碰撞，回到了原来的状态。
| x*********i
发帖数: 55 | 10 This is my two cents: label the ants clockwise from 1 to n, after a time of
T = cycle length/speed, you get a permutation of the ants. Because every
permutation has a finite order (denoted by p), after a time of T*p, every ant is in its
original position as well as direction.
【在 l******i 的大作中提到】
: You have a circle with a number of ants
: scattered around it at distinct points.
: Each ant starts walking at the same speed
: but in possibly diff erent directions, either clockwise or anticlockwise.
: When two ants meet they immediately change directions,
: and then continue with the same speed as before.
: Let us ignore the collisions,
: just think of the ants walking through each other.
: Clearly there will then be a time at which
: the ants are simultaneously in their starting positions.
| k*****y
发帖数: 744 | 11 good one.
I was worried about the directions after T, but they are actually fixed at
each spot if you think about it. So the permutation of the spots from 0 to T
is the same as the permutation from T to 2T. It is just a cyclic action,
hence has a finite order.
of
ant is in its
【在 x*********i 的大作中提到】
: This is my two cents: label the ants clockwise from 1 to n, after a time of
: T = cycle length/speed, you get a permutation of the ants. Because every
: permutation has a finite order (denoted by p), after a time of T*p, every ant is in its
: original position as well as direction.
|
|
