Tag Info

Hot answers tagged

57

There is a really elegant proof for this that requires virtually no math background at all. All computer programs are a finite sequence of bytes, which is just a number in base 256. So each computer program can be represented as a unique natural number. This statement is elaborated in detail below the divide. If a computer program prints its own number, ...


37

There are countably many programs but the number of subsets of $\mathbb{N}$ is uncountable.


14

You can ask, "If someone asked if the car is behind door 1, would the green light light up?" If green means yes and the car is behind door 1, then the green light will light up. If green means yes, but the car is behind another door, the red light will light up. If green means no and the car is behind door 1, the green light will light up for no. If green ...


14

For fixed $a$ and $b$, after $m$ steps, the frog will be at $a + mb$ if you haven't guessed right yet. The set of pairs $(a, b) \in \mathbb{N}\times \mathbb{N}$ is countable, so you can enumerate it, say as $(a_0, b_0), (a_1, b_1), \ldots$. Now guess $a_m + mb_m$ at step $m$ and you are bound to guess right eventually.


12

You definitely need $n\equiv 1\pmod {60}$ and $n\equiv 0\pmod 7$. So the trick is to apply the Chinese remainder theorem. Solve $60x+7y=1$ with $(x,y)=(2,-17)$. Then $n\equiv 1\cdot 7\cdot (-17)+0\cdot 60\cdot 2\pmod{420}$, or $n\equiv -119\pmod{420}$. The smallest such positive number is $420-119=301$.


10

If $u>v>w$ are the number of chickens that the three farmers sold at the higher price, then, by linearity, $(26-16)(u-v) = (16-10)(v-w)$, and so $u-v$ is divisible by $3$, and $v-w$ is divisible by $5$. It follows that $(u,v,w) \in \{(8,5,0),(9,6,1), (10,7,2)\}$. Only the middle solution gives prices that can be measured in USD (or most currencies), ...


7

Yes, the game will never finish. Consider the number of cards the even-numbered players have. At the start it's zero, and in the end it ought to be 1007. But we always pass an even number of cards between the even- and odd-numbered players. Hence it can never finish.


6

Let $c$ be the morning price and let $d$ be the difference between the morning and afternoon prices. Now we attempt to solve for how many did each seller sell at each of the two prices. Think of it this way: if the seller sold everything at $c$ after lunchtime, the total sales will be $kc$, where $k$ is the number of chickens. However, when he "switches" a ...


5

Here $x,y$ are the prices before and after lunch, $k,l,m$ are the number of sold chickens before lunch. And $x>y>0$. $ \left\{ \begin{array}{l} kx+(10-k)y=35 \\ lx+(16-l)y=35 \\ mx+(26-m)y=35 \end{array} \right. $ Subtract the second and the third from the first gives $\displaystyle \left\{ \begin{array}{l} (k-l)x-(6+(k-l))y=0 \\ ...


5

The paper by Develin and Payne referenced in the comments gives a very thorough treatment of this type of game, and in particular addresses the complicated nuances of breaking ties that arise during the bidding. However, in the Richman games they treat, the winning bid is given to the other player... this problem is slightly different. Glossing over the ...


5

Any known model of computing, and thus any computer we can make, is equivalent to a Turing machine. Since the number of different possible inputs and states of a Turing machine is finite, there are, as Jihad said, countably many possible programs. Since there are uncountably many subsets of the natural numbers, there must be some subsets that the computer ...


4

The left column's entries should be interpreted with padded zeroes on the right, so that e.g. the last summand is 100,000,000.


4

HINT: Let $P$ be the set of members. For $p,q\in P$ I’ll write $p\sim q$ to indicate that $p$ and $q$ are friends, and $p\not\sim q$ to indicate that they are not. Suppose first that there are three people, $p,q$, and $r$, such that $p\not\sim q$ and $p\not\sim r$. Show that if $s\in P\setminus\{p,q,r\}$, then $s\sim p$, $s\sim q$, and $s\sim r$. Then ...


4

There does not seem to be a unique solution to this problem: there are two $5$-tuples $(x,y,z,p,q)$ satisfying the given conditions, namely $$(x,y,z,p,q) \in \left\{\left(8,5,0,\tfrac{105}{26},\tfrac{35}{26}\right), \left(9,6,1,\tfrac{15}{4},\tfrac{5}{4}\right)\right\}.$$ It is not stated that all farmers sold at least one chicken prior to lunchtime, and ...


3

Hint: You are trying to find a point which minimises the maximum distance to the given points / people. In general, this would be the centre of the smallest "covering circle" for the points. In the case of three points, this would then be either the circumcentre or the midpoint of the longest side... For more, you may want to search for "minimax ...


3

Jihad's answer proves that some such $A$ exists. For an explicit example, let $A$ be the set of Godel numbers of true statements about arithmetic (after fixing your favorite encoding).


2

I believe the spaces represent zeros, i.e. it is actually comparing: 123456789 1 123456780 21 123456700 321 123456000 4321 123450000 54321 123400000 654321 123000000 7654321 120000000 87654321 100000000 987654321


2

Here's another way to tackle it. You already figured out that you're looking for $60k+1$. When you multiply $60$ by $k$ you want a predecessor to a multiplication of $7$. $60 \equiv 4 \pmod 7$ and $5 \times 4 = 20$ which is a predecessor to a multiplication of $7$. So $k=5$.


2

Consider $60k+1,$ $$60(7n)+1=420n+1$$ $$60(7n+1)+1=420n+61$$ $$60(7n+2)+1=420n+121$$ $$60(7n+3)+1=420n+181$$ $$60(7n+4)+1=420n+241$$ $$60(7n+5)+1=420n+301$$ $$60(7n+6)+1=420n+361.$$ Now by divisibility test for 7, among $1, 61, 121, 181, 241, 301, 361$, only $301$ is divisible by $7.$ Therefore any number of the form $420n+301$ satisfies the given ...


2

This isn't so much a geometric problem about a hexagonal grid, this is very much a topological problem, specially a graph theory problem, involving an (infinite) graph, where the nodes are the vertices of the hexagonal grid and the edges are the edges. The problem you present reminds me very much of edge colouring ...


2

$x + y + z$ is $x{\cdot}z$, then $y{\cdot}z$ then $x{\cdot}z+y{\cdot}z-y$


2



2

Denote by $x_k$ the number of victories for player $P_k$, and assume $x_1\leq x_2\leq\ldots\leq x_8$. If $x_8<7$ then $P_8$ has lost at least one game against a player $P_k$ with $k<8$. Since $$(x_8+1)^2+(x_k-1)^2=x_8^2+x_k^2+2(x_8-x_k)+2\geq x_8^2+x_k^2+2\ ,$$ the total payout would have been greater when $P_8$ would have won this game as well. It ...


2

I did it with the above diagram, now of course drawn to scale. The two red rectangles (over) $QH$ & $HC$, green rectangles $AH$ & $HD$, blue rectangles $BH$ & $HE$ represent the three farmers' revenue. The horizontal axis represents the number of chicken sold, and the height is the price at which the farmer sold the chicken. Naturally, $H$ ...


2

Here is a practical solution based on elementary group theory that can be used to solve many permutation puzzles. In many puzzles, there are two properties for each piece. It has a position and it has an orientation. A piece may be in the right position but wrong orientation. Later when I refer to permutations such as cycles, it refers to the permutations ...


1

May I add that if anyone wondered about the maximum number of 3-cycles required to solve/generate any even permutation of any nxnxn Rubik's cube orbit of pieces (ignoring corner and middle edge orientations), I get that it takes a maximum of: 12 3-cycles to solve every non-fixed center and wing edge orbit (one at a time). The exact average number of ...


1

It is not possible, in the general case. For example, let $a_1, b_1, a_2, b_2$ be prime. Then neither of the bars can be divided in half or in thirds, while still leaving integer diimensions.


1

The first thing you have to realize is that the only thing that matters is the areas of each of the bars. So let $A$ and $B$ be those areas. Now let $A$ have canonical prime factorization $2^{a_2}\cdot3^{a_3}\dots \cdot p_n^{a_n}$ and let $B$ have canonical factorization $2^{b_2}\cdot3^{b_3}\dots p_n^{b_n}$ . A necessary condition for being able to pass ...


1

So the Grand Master scores highly, of course, getting $5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 = 37182145$ The remaining disciples, in order round the table, get: $$\begin{array}{|c|c|} \hline \text{Disciple} & \text{Score} & \text{Composition} \\ \hline 1 & 14872858 & 2 \times 7 \times 11 \times 13 \times 17 \times 19 ...


1

Such puzzles typically are related mainly with knot theory.



Only top voted, non community-wiki answers of a minimum length are eligible