The Ant and the Checkerboard – Probability on a 100×100 Grid

Το μυρμήγκι και το σακί με την άμμο – Πιθανότητα σε σκακιέρα 100×100

Εκφώνηση

Ένα μυρμήγκι που κουβαλάει ένα σακί με άμμο περπατάει στα τετραγωνάκια ενός πλέγματος 100×100, το οποίο είναι βαμμένο σαν σκακιέρα (σκούρα και ανοιχτά τετράγωνα εναλλάξ). Το μυρμήγκι κινείται με μια ζιγκ-ζαγκ διαδρομή, όπως στο σχήμα: σε κάθε γραμμή πηγαίνει οριζόντια, μετά κατεβαίνει ένα τετράγωνο και γυρίζει στην αντίθετη κατεύθυνση, μέχρι να περάσει από όλα τα τετράγωνα ακριβώς μία φορά.

Στο 1ο τετράγωνο που επισκέπτεται αφήνει 1 κόκκο άμμου, στο 2ο τετράγωνο αφήνει 2 κόκκους, στο 3ο αφήνει 3 κόκκους, κ.ο.κ., μέχρι να αφήσει 10000 κόκκους στο τελευταίο τετράγωνο. Ύστερα επιλέγεται τυχαία ένας κόκκος άμμου, έτσι ώστε κάθε ένας από τους \(1+2+\dots+10000\) κόκκους να είναι εξίσου πιθανός.

Ποια είναι η πιθανότητα ο επιλεγμένος κόκκος να βρίσκεται σε σκούρο τετράγωνο;

(A) 5001/10000    (B) 4999/10000    (C) 4999/9999    (D) 5001/10001    (E) 5000/10001

Λύση

Το μυρμήγκι κινείται κάθε φορά ένα βήμα οριζόντια ή κατακόρυφα. Σε σκακιέρα, κάθε τέτοιο βήμα αλλάζει χρώμα τετραγώνου (από σκούρο σε ανοιχτό ή ανάποδα). Άρα τα χρώματα κατά μήκος της διαδρομής εναλλάσσονται.

Ας υποθέσουμε ότι το πρώτο τετράγωνο είναι σκούρο (όπως στο σχήμα). Τότε:

• το 1ο τετράγωνο (με 1 κόκκο) είναι σκούρο,
• το 2ο τετράγωνο (με 2 κόκκους) είναι ανοιχτό,
• το 3ο τετράγωνο (με 3 κόκκους) είναι σκούρο,
• το 4ο τετράγωνο είναι ανοιχτό, κ.ο.κ.

Άρα τα τετράγωνα με μονό αριθμό επίσκεψης είναι σκούρα, και με ζυγό αριθμό επίσκεψης είναι ανοιχτά.

Κάθε τετράγωνο με αριθμό επίσκεψης \(k\) παίρνει \(k\) κόκκους. Άρα ο συνολικός αριθμός κόκκων σε σκούρα τετράγωνα είναι:

άθροισμα όλων των μονών αριθμών από 1 έως 9999.

Υπάρχουν 5000 μονά μεταξύ 1 και 10000 (1,3,5,…,9999) και ο μέσος όρος τους είναι \(\dfrac{1+9999}{2} = 5000\), οπότε:

Αριθμός κόκκων σε σκούρα τετράγωνα = \(5000 \cdot 5000 = 25\,000\,000.\)

Ο συνολικός αριθμός κόκκων είναι:

\(1+2+\dots+10000 = \dfrac{10000\cdot10001}{2} = 50\,005\,000.\)

Επομένως η ζητούμενη πιθανότητα είναι:

\(\displaystyle P(\text{σκούρο}) = \frac{25\,000\,000}{50\,005\,000}.\)

Διαιρούμε αριθμητή και παρονομαστή με 5000:

\(\displaystyle P(\text{σκούρο}) = \frac{5000}{10001}.\)

Σωστή απάντηση: (E) 5000/10001.

The Ant and the Checkerboard – Probability on a 100×100 Grid

Problem

An ant carrying a sack of sand walks through the cells of a 100 by 100 grid, colored in a checkerboard pattern. The ant zigzags as in the diagram: in each row it walks horizontally, then drops down one cell and walks in the opposite direction, eventually visiting every square exactly once.

The ant deposits 1 grain of sand in the first square it visits, 2 grains in the second, 3 grains in the third, and so on, leaving 10000 grains of sand in the last square. Then one grain of sand is randomly chosen, each of the \(1+2+\dots+10000\) grains being equally likely.

What is the probability that the chosen grain lies on a dark-colored square?

(A) 5001/10000    (B) 4999/10000    (C) 4999/9999    (D) 5001/10001    (E) 5000/10001

Solution

Each step of the ant is one square horizontally or vertically. On a checkerboard, every such step changes color: dark → light or light → dark. Thus the colors along the ant’s path alternate.

Assume the first square is dark (as in the diagram). Then:

• the 1st visited square (1 grain) is dark,
• the 2nd (2 grains) is light,
• the 3rd (3 grains) is dark,
• the 4th is light, and so on.

So squares with odd visit numbers are dark, and those with even visit numbers are light. A square visited at step \(k\) gets \(k\) grains, so the total number of grains on dark squares is

the sum of all odd numbers from 1 to 9999.

There are 5000 odd numbers between 1 and 10000 (1,3,5,…,9999), with average \(\dfrac{1 + 9999}{2} = 5000\), so:

Grains on dark squares = \(5000 \cdot 5000 = 25\,000\,000.\)

The total number of grains is:

\(1 + 2 + \dots + 10000 = \dfrac{10000 \cdot 10001}{2} = 50\,005\,000.\)

Therefore,

\(\displaystyle P(\text{dark square}) = \frac{25\,000\,000}{50\,005\,000}.\)

Divide numerator and denominator by 5000:

\(\displaystyle P(\text{dark square}) = \frac{5000}{10001}.\)

Correct answer: (E) 5000/10001.