sabercpp's blog

By sabercpp, history, 7 weeks ago, In English

So I was thinking of making some div2B/C level CP problems for my school contest and thought of this....

Here it goes....

Find the maximum number of squares of side length 'a' that can completely be inscribed in a circle of radius 'r' such that exactly one of the vertices of the square touches the circle and no 2 squares overlap each other. Note that all the squares have to be completely inside the circle.

I cant figure this out..ended up taking too many variables which I cant eliminate...any thoughts or hints ?

The figure will look something like this :

Screenshot-106
No way am using geogebra for this

Apologize for the sketchy figure though.

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess you read the problem wrong...I dont want to "pack" them, I want to count how many of them can have exactly one vertice lying on circumference without overlapping each other.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by sabercpp (previous revision, new revision, compare).

»
7 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I thought of an approach but I am not sure whether it is the Maximum number of squares or not. Let all the squares be oriented in such a way that their diagonals (lets call it the main diagonal) point directly towards the centre. Let L1 and L2 be two lines tangent to the sides of the square (which do not contain the main diagonal ) from the centre of circle. Now extend L1 and L2 until they touch the circumference of circle. Let the Angle subtended by L1 and L2 from the centre be 2*x (in radians ) . By using simple geometry we can prove that 2*x = tan-1 ( a / (sqrt(2)*r — a) ) , where tan-1 (k) = tan inverse of k. So total number of squares of such orientation would be (2*pi)/2*x = pi / x , where pi = 3.14 . What about this ?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes that seems to work but idk about optimality. Also you found the half angle x..whereas it should have been 2x. So answer would be pi/x.