We came to think of this problem:
Ali is a good Muslim who happens to travel a lot. On one occasion when Ali is praying, properly oriented towards Mecca, he notices that he is also facing exactly east.
Where can Ali be?
The geographical coordinates of Mecca are $21.4^\circ\text{N}$ and $39.8^\circ\text{E}$ (you may switch to a coordinate system using Mecca's longitude as the zero meridian). You may assume the Earth is a perfect sphere, and Ali is on its surface.
We have realized that the solution consists of two "components". One is a curve with Mecca (where the correct orientation is not well-defined) as the southern endpoint and the North Pole (where east is "all directions") as the northern endpoint. The other component is obtained from the first by rigidly moving the curve along the surface of the Earth such that it connects the antipodal point of Mecca with the South Pole.
We do not know if each "component" is an arc of a small circle.
Instead of solving the problem ourselves (we are lazy), we thought some people would come up with some nice solutions on this forum. It would be interesting with both formulas and visual representations (such as globes with the solution curve plotted on them).
Extending the problem: What if, in the problem text, you change the direction "east" to "northeast"; you would get a new curve? Or "east-northeast" etc.? This gives a whole family of curves which could all be plotted on a globe.
Also, does anyone know if this is a well-known problem that has its own name or reference?
Wikipedia link: Qibla
I will give a simple solution using coordinates. This does not answer the question of "Is this a well-known problem that has its own name or reference?"
We have a sphere with two distinguished points: the North Pole, $N$, and Mecca, $M$. At any third point $A$, facing east means facing in the direction perpendicular to the geodesic from $A$ to $N$. Facing $M$ means facing in the direction of the geodesic $AM$. Therefore, we seek the locus of points $A$ such that the geodesics $AN$ and $AM$ are perpendicular.
Take the Earth to be a unit sphere centered at the origin $O$, with the coordinates of the points being $N=(0,0,1)$, $M=(\cos\theta,0,\sin\theta)$, and $A=(x,y,z)$. The angle between the great circles $AN$ and $AM$ is equal to the angle between the normals of the planes $AON$ and $AOM$ containing them. This gives the condition $(A\times N)\cdot(A\times M)=0$, which simplifies to $$(x^2+y^2)\sin\theta=xz\cos\theta.$$